Prove that $\left(\sum_{k=1}^{n}k\right)^2=\sum_{k=1}^{n}k^3$ holds true for $n ≥ 1$ I've been trying to figure out this proof for way too long now, I'm just not sure where to begin for the inductive step. Any guidance would be greatly appreciated.
 A: Suppose it holds for some $n \geq 1$.
Claim: It holds for $n+1$, too.
Proof: We have
\begin{align*}
\left(1+ 2 + \ldots + n + (n+1) \right)^2 & = \left(1 + 2 + \ldots + n \right)^2 + 2 \left(1 + 2 + \ldots + n \right) (n+1) + (n+1)^2 \\
& = (1^3 + 2^3 + \ldots + n^3) + 2\frac{n(n+1)}{2} (n+1) + (n+1)^2 \\
& = (1^3 + 2^3 + \ldots + n^3) + n(n+1) ^2 + (n+1)^2 \\
& = 1^3 + 2^3 + \ldots + n^3 + (n+1)^3
\end{align*}
(I have made use of Gauss's addition forumla)
The assertion holds trivially for $n = 1$, it follows from induction that it holds for all $n \geq 1$.
A: Hint:
$$
(1+2+\dots+n + (n+1))^2 - (1+2+\dots+n )^2
\\= (n+1)(2\times 1+2\times2+\dots+2\times n + (n+1))
$$
now remember that
$$
1+2+\dots+n = \frac12 n(n+1)
$$
A: $$
(1+\ldots+n+n+1)^2 = (1+\ldots+n)^2+2(n+1)(1+\ldots+n)+(n+1)^2 \\
=(1+\ldots+n)^2 + (n+1)(2(1+\ldots+n)+n+1) \\
=(1+\ldots+n)^2 + (n+1)(2(\frac{n(n+1)}{2})+n+1) \\
=(1+\ldots+n)^2 + (n+1)(n+1)(n+1)
$$
A: To make this proof easier to follow, let's define the following:  $$\begin{align*} A_n &= \sum_{k=1}^n k, \\ B_n &= A_n^2 = \biggl(\sum_{k=1}^n k\biggr)^2, \\ C_n &= \sum_{k=1}^n k^3. \end{align*}$$  Then the claim to be proven is that $B_n = C_n$ for all positive integers $n$.  Here, we focus on the inductive step:  that is, we wish to establish that if there exists a positive integer $n$ such that $B_n = C_n$, this implies that $B_{n+1} = C_{n+1}$.  To this end, we first observe $A_{n+1} = (n+1) + A_n$:  hence $$\begin{align*} B_{n+1} &= A_{n+1}^2 = ((n+1) + A_n)^2 \\ &= (n+1)((n+1) + 2A_n) + A_n^2 \\ &= (n+1)(A_n + (n+1) + A_n) + B_n \\ &= (n+1)(A_{n+1} + A_n) + C_n. \end{align*}$$  But note $$A_{n+1} + A_n = (n+1) + \sum_{k=1}^n k + \sum_{k=n}^1 ((n+1)-k) = (n+1) + \sum_{k=1}^n (n+1) = (n+1)^2,$$ thus $$B_{n+1} = (n+1)^3 + C_n = C_{n+1},$$ which completes the inductive step.
A: Hint: We know that $\sum_{k=1}^nk={n(n+1)\over 2}$.
