# Question #81d37

Mar 16, 2015

This is a classical case in which you can prove something by induction. The idea is the following: think of a river with very strong current that you must cross. You can't swim, but there are several stones, and you can jump from one to the other. If you find a first (solid!) stone, and you learn how to jump from a stone to the next, then you can cross the river!

In formulas, a proof by induction works as follows:

1. First of all, you must prove that the formula holds for a basic case (which is usually $n = 0$ or $n = 1$)
2. You must prove that, if the formula holds for a generic value $n$, then it also works for $n + 1$.

By doing so, you can work -indeed- by induction, and step from a number to its successor, and so cover the entire range of natural numbers: the statement it's true for $n = 1$. Then, it's true for $n = 2$. Applying the same logic, we can step from $n = 2$ to $n = 3$, and so on.

So, let's begin with the basic case $n = 1$. Is it true that

$\setminus {\sum}_{i = 1}^{1} {i}^{3} = \frac{{1}^{2} \cdot {\left(1 + 1\right)}^{2}}{4}$?

Of course it is, since the sum means simply 1^3, which is one, and the fraction on the right side is also 1.

So now, let's assume that the sum of the first $n$ cubes is $\frac{{n}^{2} \cdot {\left(n + 1\right)}^{2}}{4}$, and we must prove that the sum of the first $n + 1$ cubes is $\frac{{\left(n + 1\right)}^{2} \cdot {\left[\left(n + 1\right) + 1\right]}^{2}}{4}$, which is the previous formula in which I substituted $n \setminus \rightarrow n + 1$. We have:

$\setminus {\sum}_{i = 1}^{n + 1} {i}^{3} = \setminus {\sum}_{i = 1}^{n} {i}^{3} + {\left(n + 1\right)}^{3}$, and we are assuming that the sum up to $n$ equals $\frac{{n}^{2} \cdot {\left(n + 1\right)}^{2}}{4}$. We simply need to add ${\left(n + 1\right)}^{3}$ and check the result:

$\frac{{n}^{2} \cdot {\left(n + 1\right)}^{2}}{4} + {\left(n + 1\right)}^{3} =$
$\frac{{n}^{2} \left({n}^{2} + 2 n + 1\right) + 4 \left({n}^{3} + 3 {n}^{2} + 3 n + 1\right)}{4} =$
$\frac{{n}^{4} + 2 {n}^{3} + {n}^{2} + 4 {n}^{3} + 12 {n}^{2} + 12 n + 4}{4} =$
$\frac{{n}^{4} + 6 {n}^{3} + 13 {n}^{2} + 12 n + 4}{4}$

We want this to be equal to $\frac{{\left(n + 1\right)}^{2} \cdot {\left[\left(n + 1\right) + 1\right]}^{2}}{4}$, which is true if and only if the numerators are equal. Let's expand this last numerator:
${\left(n + 1\right)}^{2} \cdot {\left[\left(n + 1\right) + 1\right]}^{2} =$
$\left({n}^{2} + 2 n + 1\right) {\left(n + 2\right)}^{2} =$
$\left({n}^{2} + 2 n + 1\right) \left({n}^{2} + 4 n + 4\right) =$
${n}^{4} + 4 {n}^{3} + 4 {n}^{2} + 2 {n}^{3} + 8 {n}^{2} + 8 n + {n}^{2} + 4 n + 4 =$
${n}^{4} + 6 {n}^{3} + 13 {n}^{2} + 12 n + 4$

which is exactly what we wanted.

Mar 16, 2015

First of all let's try to understand why it works.

We know that ${\sum}_{i = 1}^{n} i = \frac{n \left(n + 1\right)}{2}$,

and this is because we have $\frac{n}{2}$ sums of the value $n + 1$ (that is because the first added to the last, the second added to the second-last, and so on... have all value $n + 1$).

Now we can see our sum:

${\sum}_{i = 1}^{n} {i}^{3} = 1 + 8 + 27 + 64 + 125 + \ldots + {n}^{3}$

Let's proceed step by step:

${S}_{1} = {\sum}_{i = 1}^{1} {i}^{3} = 1$,

${S}_{1}^{'} = {\sum}_{i = 1}^{1} i = 1$,

so ${S}_{1} = {\left({S}_{1}^{'}\right)}^{2}$.

${S}_{2} = {\sum}_{i = 1}^{2} {i}^{3} = 1 + 8 = 9$,

${S}_{2}^{'} = {\sum}_{i = 1}^{2} i = 1 + 2 = 3$,

so ${S}_{2} = {\left({S}_{2}^{'}\right)}^{2}$.

${S}_{3} = {\sum}_{i = 1}^{3} {i}^{3} = 1 + 8 + 27 = 36$,

${S}_{3}^{'} = {\sum}_{i = 1}^{3} i = 1 + 2 + 3 = 6$,

so ${S}_{3} = {\left({S}_{3}^{'}\right)}^{2}$.

...

${S}_{n} = {\sum}_{i = 1}^{n} {i}^{3} = 1 + 8 + 27 + 64 + 125 + \ldots + {n}^{3}$,

${S}_{n}^{'} = {\sum}_{i = 1}^{1} i = 1 + 2 + 3 + 4 + 5 + \ldots + n = \frac{n \left(n + 1\right)}{2}$,

so ${S}_{n}$ has to be ${\left({S}_{n}^{'}\right)}^{2}$ and so:

${S}_{n} = {\left(\frac{n \left(n + 1\right)}{2}\right)}^{2} = \frac{{n}^{2} {\left(n + 1\right)}^{2}}{4}$.

But this is not a demonstration.

This is only an idea.

We have to demonstrate it with the induction rule, that says:

If a property is true for the first value, we can assume that it is true for the $n$th term and we have to demonstrate that it is true for the $\left(n + 1\right)$th term.

So:

Is the property true for the first term?

${\sum}_{i = 1}^{1} {i}^{3} = 1$ and $\frac{{1}^{2} {\left(1 + 1\right)}^{2}}{4} = 1$: YES

Let's assume that it is true for $n$:

${\sum}_{i = 1}^{n} {i}^{3} = \frac{{n}^{2} {\left(n + 1\right)}^{2}}{4}$ and this is our hypotesis.

Let's demonstrate that it is true also for $n + 1$:

${\sum}_{i = 1}^{n + 1} {i}^{3} = {\sum}_{i = 1}^{n} {i}^{3} + {\left(n + 1\right)}^{3} =$

$= \frac{{n}^{2} {\left(n + 1\right)}^{2}}{4} + {\left(n + 1\right)}^{3} = \frac{{n}^{2} {\left(n + 1\right)}^{2} + 4 {\left(n + 1\right)}^{3}}{4} =$

$= \frac{{\left(n + 1\right)}^{2} \left({n}^{2} + 4 n + 4\right)}{4} = \frac{{\left(n + 1\right)}^{2} {\left(n + 2\right)}^{2}}{4}$

that is perfectly the formula that we have to demonstrate in which at the place of $n$ there is $n + 1$!