# Proof by Induction question

1. Jun 12, 2006

### EbolaPox

I'm new to Proof by Induction. I've gotten a few so far, but this one has eluded me for some reason.

" Prove that $$1^3 + 2^3 + 3^3.....k^3 = (1 +2 + 3....k)^2$$"

I checked for n =1 and , yes it does work. So, I assumed A(k) is true, so I'll try for A(k+1)

I started assuming A(k) and added $$(k+1)^3$$ to both sides (as this would be the next term

$$1^3 + 2^3 .... k^3 + (k+1)^3 = (1 + 2.... k)^2 + (k+1)^3 = (1 + 2....k + (k + 1) )^2$$

So, I must now show that

$$(1 +2 + .... k + (k+1))^2 = (1 + 2 + ....k)^2 + (k+1)^3$$
Does this look right so far?

Unfortunately, I haven't thought of a way to demonstrate this yet. If I prove that statement true, I prove the original assertion. Should I try proving that statement with induction or something...?

2. Jun 12, 2006

### StatusX

There was a thread about this not too long ago, but I can't find it. I think you'll have to use the explicit expression for the sum 1+2+...+k. Do you know what this is? If not, you can find it by thinking about the following figures:

#0

#00
$0 #000$00
###0

...

Last edited: Jun 12, 2006
3. Jun 12, 2006

### EbolaPox

Oh! Are you suggesting express
$$1 + 2 + 3 .... k = k(k+1)/2$$. I'll prove that at the end, but I'll assume that fact is true and use it. (I proved that one earlier, but I'll post a proof of that at the end to make sure it is right also.) . I didn't even think to use that! Well, using that
$$(1 +2 + .... k + (k+1))^2 = (1 + 2 + ....k)^2 + (k+1)^3$$

goes down to
$$((k+1)(k+2) /2 )^2 = ((k+1)k/2)^2 + (k+1)^3$$

Now, expanding these lovely algebraic nightmares leads me to

$$(1/4) (k^4 + 6k^3 + 13k^2 + 8k + 4) = (1/4) (k^4 + 2k^3 + k^2) + (k+1)^3$$

Multiplying through by four, and then subtracting like terms leads me to

$$4k^3 + 12k^2 + 12k+4 = 4(k+1)^3$$
$$k^3 +3k^2 + 3k +1 = (k+1)^3$$
Which is true! Thank you very much!

Now, I should prove the statement I used above $$\sum_1^k i = k(k+1)/2$$

So, I start about by Checking A(1) (True). I assume A(k) is true. And go to show k+1 is true. Adding k+1 to both sides leads to

$$1 +2 + 3 ... k + (k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2) /2$$
Working with the middle and right hand side, I can show those are equal and I will prove it.