1
$\begingroup$

I started a new course and I'm expected to know this stuff, and I'm having trouble learning some on my own. I'm stuck with this problem: Prove $1 + 2^3 + 3^3 + ... + n^3 = \frac{((n^2)(n+1)^2)}4$ using induction (the $1+2^3...$ is written in sum notation, although I don't know how to enter that here, sorry). I started substituting $n \rightarrow n+1$ but I don't know what to do next. Any help would be extremely appreciated.

$\endgroup$
  • $\begingroup$ Whenever you have a recursive sum like this that results in a polynomial instead of exponential growth, you can use telescoping. $\endgroup$ – DanielV Mar 18 '15 at 21:18
6
$\begingroup$

$$1+2^3+...+n^3+(n+1)^3\underset{Hyp.}{=}\frac{n^2(n+1)^2}{4}+(n+1)^3=\frac{n^2(n+1)^2+4(n+1)^3}{4}=\frac{(n+1)^2(n^2+4n+4)}{4}=\frac{(n+1)^2(n+2)^2}{4}.$$

$\endgroup$
  • $\begingroup$ Oh, you were faster, I was about to send the answer too. :) $\endgroup$ – Atvin Mar 18 '15 at 21:05
  • $\begingroup$ I don't understand how that result proves the expression, could you explain a bit? $\endgroup$ – YoTengoUnLCD Mar 18 '15 at 21:06
  • 1
    $\begingroup$ Do you know proof by induction ? $\endgroup$ – Surb Mar 18 '15 at 21:06
  • $\begingroup$ @Surb oh yes, it was my bad, I failed to see the last expression was my original "P(n)" evaluated at "P(n+1)". Thank you so much! $\endgroup$ – YoTengoUnLCD Mar 18 '15 at 21:08
5
$\begingroup$

First, show that this is true for $n=1$:

$\sum\limits_{k=1}^{1}k^3=\frac{1^2(1+1)^2}{4}$

Second, assume that this is true for $n$:

$\sum\limits_{k=1}^{n}k^3=\frac{n^2(n+1)^2}{4}$

Third, prove that this is true for $n+1$:

$\sum\limits_{k=1}^{n+1}k^3=\color{red}{\sum\limits_{k=1}^{n}k^3}+(n+1)^3=\color{red}{\frac{n^2(n+1)^2}{4}}+(n+1)^3=\frac{(n+1)^2(n+2)^2}{4}$


Please note that the assumption is used only in the part marked red.

$\endgroup$
3
$\begingroup$

This question often causes a lot of confusion simply because of the cumbersome factoring.

Let $P(n)$ be the proposition that $$\sum_{i=1}^n i^3 = \frac{(n^2)(n+1)^2}{4}.$$

Base Case, $P(1)$: $\sum_{i=1}^1 i^3 = 1$ and $\frac{(1^2)(1+1)^2}{4} = \frac{4}{4} = 1$ so $P(1)$ is true.

Inductive Hypothesis: Assume that $P(k)$ is true: $1^3 + \cdots + k^3 = \frac{(k^2)(k+1)^2}{4}$

Now it remains to show that $P(k) \implies P(k+1)$. Start with the left side of the equation:

$$\sum_{i=1}^{k+1} i^3 = \left( \sum_{i=1}^k i^3 \right) + (k+1)^3 = \frac{(k^2)(k+1)^2}{4} + (k+1)^3$$ (by the IH above). Now we factor out a $(k+1)^2$: $$= (k+1)^2 \cdot (\frac{k^2}{4} + k + 1) = \frac{(k+1)^2(k^2+4k+4)}{4} = \frac{(k+1)^2((k+1)+1)^2}{4}$$ Which is equal to the desired result.

$\endgroup$
3
$\begingroup$

If you don't really understand the steps of induction, here is how it's done:

First we show that the statement is true for $n=1$:

$1=\frac{1*2^2}4$, $1 = 1$, the statement is true.

Assume, that the statement is true until $n$, let us prove for $n+1$ too:

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

You can see that on the left side, I just wrote the statement until $n+1$, and on the right side, I wrote what we need to prove, for $n+1$.

From our induction hypotesis, we know that $1+2^3+...+n^3 = \frac{n^2(n+1)^2}4$, so we write the left side in the form:

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

From this, you can see above, that they are equal.

I hope you understood the steps, if not, feel free to comment.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.