# Induction Proofs

1. May 25, 2006

Prove that $$1^{3} + 2^{3} + 3^{3} + ... + n^{3} = (1 + 2 + 3 + ... + n)^{2}$$. So for $$n =1$$ $$1^{3} = 1^{2}$$. For $$n = k$$, $$1^{3} + 2^{3} + 3^{3} + ...+ k^{3} = (1+2+3+...+ k )^{2}$$. For $$n = k+1$$,$$1^{3} + 2^{3} + 3^{3} +...+ k^{3} + (k+1)^{3} = (1+2+3+..+ (k+1))^{2}$$. So do I then do this:

$$1^{3} + 2^{3} + 3^{3} + ... + k^{3} + (k+1)^{3} = (1+2+3+...+ k)^{2} + (k+1)^{3}$$ to show that it is equal to $$n = k+1$$?

Thanks

Last edited: May 25, 2006
2. May 25, 2006

### VietDao29

You must use your induction hypothesis, i.e:
$$1 ^ 3 + 2 ^ 3 + ... + k ^ 3 = (1 + 2 + ... + k) ^ 2$$ (1)
To prove that:
$$1 ^ 3 + 2 ^ 3 + ... + k ^ 3 + (k + 1) ^ 3 = (1 + 2 + ... + k + (k + 1)) ^ 2$$. (2)
i.e if the equation is true for n = k, it also holds when n = k + 1.
------------------
So let's go from what we have:
$$1 ^ 3 + 2 ^ 3 + ... + k ^ 3 = (1 + 2 + ... + k) ^ 2$$
the LHS of the equation (2) has an extra term (k + 1)3. So let's add (k + 1)3 to both sides of the above equation:
$$\Leftrightarrow 1 ^ 3 + 2 ^ 3 + ... + k ^ 3 + (k + 1) ^ 3 = (1 + 2 + ... + k) ^ 2 + (k + 1) ^ 3$$ (3)
You have to prove that
$$1 ^ 3 + 2 ^ 3 + ... + k ^ 3 + (k + 1) ^ 3 = (1 + 2 + ... + k + (k + 1)) ^ 2$$, right?
Or in other words, you have to prove:
$$(1 + 2 + ... + k) ^ 2 + (k + 1) ^ 3 = (1 + 2 + ... + k + (k + 1)) ^ 2$$
Can you go from here? :)

Last edited: May 25, 2006
3. May 25, 2006

yes. thank you

4. May 26, 2006

### Curious3141

Hint, an easy way to do it is to use $$1 + 2 + ... + k = \frac{1}{2}k(k+1)$$

5. May 26, 2006

### arunbg

Indeed , and $$1^3 + 2^3 + ... + k^3 = (\frac{1}{2}k(k+1))^2$$

But that is what the question is asking us to prove, by induction.
So the direct formulae are not applicable (only the assumed tautology can be used) and VietDao's method is the probably the only straightforward method to do this problem .

Arun

6. May 26, 2006

How can you show that $$(-1)^{k+1} (1+2+...+k)k^{2} + (-1)^{k+2}(k+1)^{2} = (-1)^{k+2}(1+2+...+ k + (k+1))$$?

7. May 26, 2006

### matt grime

You can sum 1+2+3+...+r so why don't you? You can also divide everything by (-1)^{k+1} to remove any doubts about signs. Of course it looks false: the LHS is (the same as) a poly in k^3 and the RHS in k^2

Last edited: May 26, 2006
8. May 26, 2006

The original problem was: Prove that $$1-4+9-16 + ... + (-1)^{n+1} n^{2} = (-1)^{n+1} (1+2+... + n)$$. For $$n =1$$ $$1 =1$$. For $$n = k$$, $$1-4+9-16+...+(-1)^{k+1} k^{2} = (-1)^{k+1} ( 1+2+...+n)$$. For $$n = k+1$$, $$1-4+9-16 + ...+ (-1)^{k+2}(k+1)^{2} = (-1)^{k+2}(1+2+...+k+(k+1))$$. So I want to show that: $$1-4+9-16+...+ (-1)^{k+1}k^{2} + (-1)^{k+2}(k+1)^{2} = (-1)^{k+1}(1+2+...+k)+(-1)^{k+2}(k+1)^{2}$$ or $$(-1)^{k+1}(1+2+...+k)k^{2}+(-1)^{k+2}(k+1)^{2} = (-1)^{k+2}(1+2+...+ k + (k+1))$$. When I divide through I get: $$(1+2+...+k)k^{2} - (k+1)^{2} = - (1+2+...+k+(k+1))$$ or $$\frac{1}{2}k(k+1)k^{2} - (k+1)^{2} = -(\frac{1}{2}(k+1)(k+2))$$

Isn't this correct?

Last edited: May 26, 2006
9. May 26, 2006

### Curious3141

The question is asking one to prove $$(1 + 2 + ... + k)^2 = 1^3 + 2^3 + ... + k^3$$ not that $$1 + 2 + ... + k = \frac{1}{2}k(k+1)$$. It's a pretty safe bet that the latter result can be assumed, if not, proof of that by AP sum or induction is trivial.

And, in fact, VietDao hadn't given an explicit method to prove what needs to be proved viz. $$(1 + 2 + ... + k) ^ 2 + (k + 1) ^ 3 = (1 + 2 + ... + k + (k + 1)) ^ 2$$ He merely stated it at something that needs to be proved, how is up to the individual. I'm merely suggesting a valid way to go about proving that proposition.

Last edited: May 26, 2006
10. May 26, 2006

### matt grime

Something is wrong in your algebra, and general presentation.

You *cannot* write the thing you wish to prove as if it is true:

$$1-4+9-16 + ...+ (-1)^{k+2}(k+1)^{2} = (-1)^{k+2}(1+2+...+k+(k+1))$$

should under no circumstances be the first thing you write down.

I have no idea how you came to the last line from the one immediately preceding it.

$$1-4+9-16 + ...+ (-1)^{k+2}(k+1)^{2} = \ldots$$

and put in something that the inductive hypothesis allows you to do (which is the only valid thing you can do, by the way), namely sum the first k terms using the formula you are assuming and then add the last term on, now rearrange and the answer drops out.

11. May 26, 2006

So $$1-4+9-16 + ...+ (-1)^{k+2}(k+1)^{2} = 1-4+9-16+...+(-1)^{k+1}k^{2} + (-1)^{k+2}(k+1)^{2}$$

12. May 26, 2006

### Curious3141

Right. Now apply the inductive hypothesis.

13. May 26, 2006

$$1-4+9-16 + ...+ (-1)^{k+2}(k+1)^{2} = 1-4+9-16+...+(-1)^{k+1}k^{2} + (-1)^{k+2}(k+1)^{2}= 1-4+9-16+...+(-1)^{k+1} k^{2} = (-1)^{k+1}( 1+2+...+n)+(-1)^{k+2}(k+1)^{2}$$

Last edited: May 26, 2006
14. May 26, 2006

### Curious3141

Don't mix up the n with the k (n has no place in the expressions).

There's still something wrong with the algebra. You seem to have dropped a term here :

$$1-4+9-16+...+(-1)^{k+1}k^{2} + (-1)^{k+2}(k+1)^{2}= 1-4+9-16+...+(-1)^{k+1} k^{2}$$

Anyway, how would you proceed?

15. May 26, 2006