Mathematical Induction Proof

**MissMousey** · August 27th 2010, 07:55 PM

Question: Prove 1^3 + 2^3 + ... + n^3 = (1 + 2 + ... n)^2

The basis step is satisfied but the induction step is troubling me. So I assume P(k) is true where P(k) is 1^3 + 2^3 + ... + k^3 = (1 + 2 + ... k)^2 and I want to show that P(k + 1) holds as well but I have no idea how to even begin the proof.

Can anyone provide a hint for me as to how I should start? Thanks in advance.

**Soroban** · August 27th 2010, 09:27 PM

Hello, MissMousey!

We are expected to know that:

. . $1 + 2 + 3 + \hdots + n \;=\;\dfrac{n(n+1)}{2}$

$\text{Prove: }\;1^3 + 2^3+ 3^3 + \hdots + n^3 = (1 + 2 + \hdots + n)^2$

Re-write the right side: . $1^3 + 2^3 + 3^3 + \hdots \;=\;\left[\dfrac{n(n+1)}{2}\right]^2$

$\text{Verify }S(1)\!:\;\;1^3 \:=\:\left[\dfrac{(1)(2)}{2}\right]^2\quad\hdots\text{ True!}$

$\text{Assume }S(k)\!:\;\;1^3 + 2^3 + 3^3 + \hdots + k^3 \;=\;\left[\dfrac{k(k+1)}{2}\right]^2$

$\text{Add }(k+1)^3\text{ to both sides:}$

. . $1^3 + 2^3 + 3^3 + \hdots + k^3 + (k+1)^3 \;=\;\left[\dfrac{k(k+1)}{2}\right]^2 + (k+1)^3$ . [1]

The right side is: . $\dfrac{k^2(k+1)^2}{4} + (k+1)^3<br />$

. . . . . . Factor: . $\dfrac{(k+1)^2}{4}\bigg[k^2 + 4(k+1)\bigg]$

. . . . . . . . . . $=\;\dfrac{(k+1)^2}{4}\bigg[k^2 + 4k + 4\bigg]$

. . . . . . . . . . $=\;\dfrac{(k+1)^2(k+2)^2}{4}$

Hence. [1] becomes:

. . $1^3 + 2^3 + 3^3 + \hdots + (k+1)^3 \;=\;\left[\dfrac{(k+1)(k+2)}{2}\right]^2$

We have proved $S(k+1).$
. . The inductive proof is complete.

**MissMousey** · August 28th 2010, 07:10 AM

Wow, that looks much simplier.
However, I've managed to come up w/ a solution but I would like for you to see if it's reasonable.

Basis Step: Verify that P(1) is true.
(1)^3 = 1 = (1)^2
So, P(1) is true

Induction Hypothesis: We know from the Binomial Theorem that (x + y)^2 = x^2 + 2xy + y^2. Assuming P(k) is true where P(k): 1^3 + 2^3 + ... k^3 = (1 + 2 ... + k)^2, we'll work w/ the right side of the equation w/ "n + 1" in place of "n". So we get
(1 + 2 ... + k + (k + 1))^2 = (1 + 2 .. + k)^2 + 2(1 + 2 + ... + k)(k + 1) + (k + 1)^2

If I show that 2(1 + 2 + ... + k)(k + 1) + (k + 1)^2 = (k + 1)^3, I can then rewrite the expression as (1 + 2 .. + k)^2 + (k + 1)^3 and since I assumed that P(K) was true, I can write 1^3 + 2^3 + ... k^3 + (k + 1)^3 which implies that 1^3 + 2^3 + ... k^3 + (k + 1)^3 = (1 + 2 + ... + k + (k + 1))^2 and thus the proof is completed.

Since we know that 1 + 2 + ... + k = k(k + 1)/2, we write
2(1 + 2 + ... + k)(k + 1) + (k + 1)^2
2(k(k + 1)/2)(k + 1) + (k + 1)^2
(k)(k + 1)(k + 1) + (k + 1)^2
k^3 + 3k^2 + 3k + 1
(k + 1)^3

So we now have
(1 + 2 + ... + k)^2 + (k + 1)^3 and by substitution, we get
1^3 + 2^3 + ... k^3 + (k + 1)^3
1^3 + 2^3 + ... k^3 + (k + 1)^3 = (1 + 2 + ... + k + (k + 1))^2

Since the statement P(k + 1) is proven to be true, by Induction, the proof is complete.

Thread: Mathematical Induction Proof

LinkBack

Thread Tools

Display