induction - Proving that two summations are equivalent: $sum_{i=1}^n i^3 = (sum_{i=1}^n i)^2$

Give a constructive proof to show that for all $n \geq 1$ ,

$\sum\limits_{i=1}^n i^3 = (\sum\limits_{i=1}^n i)^2$

Observe that $(n+1)^4 - n^4 = 4n^3 + 6n^2 + 4n + 1$ .

---

Now, the two following equalities are obvious:

$\sum\limits_{i=1}^n i^3 = 1^3 + 2^3 + 3^3 + ... + n^3$

$(\sum\limits_{i=1}^n i)^2 = (1 + 2 + 3 + ... + n)^2$

And they are both obviously equivalent given the first few test cases:

$\sum\limits_{i=1}^n i^3 = A(n)$

• $A(1) = 1^3 = 1$


• $A(2) = 1^3 + 2^3 = 1 + 8 = 9$


• $A(3) = 1^3 + 2^3 + 3^3 = 9 + 27 = 36$

$(\sum\limits_{i=1}^n i)^2 = B(n)$

• $B(1) = (1)^2 = 1$


• $B(2) = (1 + 2)^2 =9 $


• $B(3) = (1 + 2 + 3)^2 = 36$

Now, I am thinking of finding the closed-forms for both functions in the hopes that they are indeed the same. Then I would prove those closed forms to work by induction. But:

1. I don't know if that would be a sound way to do it.



2. I don't know if this would even qualify as constructive, as the question requests.

As you may tell, I am no math major. I am a Computer Science major, though. This is a computing fundamentals class. I took discrete 1.5 years ago, so my knowledge is about as fresh as a litter box. I've been in quite a rut for a few hours over this.

Answer

Your goal is to prove the statement $S(n)$ for all $n\geq 1$ where
$$
S(n) : 1^3 + 2^3 +3^3 +\cdots + n^3 = \left[\frac{n(n+1)}{2}\right]^2.
$$
Using $\Sigma$-notation, we may rewrite $S(n)$ as follows:

$$
S(n) : \sum_{r=1}^n r^3 = \left[\frac{n(n+1)}{2}\right]^2.
$$
Base step: The statement $S(1)$ says that $(1)^3 = (1)^2$ which is true because $1=1$.

Inductive step [$S(k)\to S(k+1)$]: Fix some $k\geq 1$, where $k\in\mathbb{N}$. Assume that
$$
S(k) : \sum_{r=1}^k r^3 = \left[\frac{k(k+1)}{2}\right]^2
$$
holds. To be proved is that

$$
S(k+1) : \sum_{r=1}^{k+1} r^3 = \left[\frac{(k+1)((k+1)+1)}{2}\right]^2
$$
follows. Beginning with the left side of $S(k+1)$,
\begin{align}
\sum_{r=1}^{k+1}r^3 &= \sum_{r=1}^k r^3 + (k+1)^3\tag{evaluate sum for $i=k+1$}\\[1em]
&= \left[\frac{k(k+1)}{2}\right]^2+(k+1)^3\tag{by $S(k)$}\\[1em]
&= \frac{(k+1)^2}{4}[k^2+4(k+1)]\tag{factor out $\frac{(k+1)^2}{4}$}\\[1em]
&= \frac{(k+1)^2}{4}[(k+2)(k+2)]\tag{factor quadratic}\\[1em]
&= \frac{(k+1)^2(k+2)^2}{4}\tag{multiply and rearrange}\\[1em]

&= \left[\frac{(k+1)(k+2)}{2}\right]^2\tag{rearrange}\\[1em]
&= \left[\frac{(k+1)((k+1)+1)}{2}\right]^2,\tag{rearrange}
\end{align}
one arrives at the right side of $S(k+1)$, thereby showing that $S(k+1)$ is also true, completing the inductive step.

By mathematical induction, it is proved that for all $n\geq 1$, where $n\in\mathbb{N}$, that the statement $S(n)$ is true.

Note: The step where $\dfrac{(k+1)^2}{4}$ is factored out is an important one. If we do not factor this out and, instead, choose to expand $(k+1)^3$, the problem becomes much more messy than it needs to be.