Can anyone help me prove (k(k-1)/2)^2 by mathematical induction

Printable View

- Nov 24th 2007, 11:24 PMhats_06Anyone a pro at proof by mathematical induction?
Can anyone help me prove (k(k-1)/2)^2 by mathematical induction

- Nov 24th 2007, 11:31 PMkalagota
- Nov 25th 2007, 05:48 AMSoroban
Hello, hats_06!

Quote:

Can anyone help me prove (k(k-1)/2)^2 by mathematical induction?

What you're asking is: "Can anyone prove $\displaystyle 36$?"

I recognize the expression.

It may have come from: .$\displaystyle 1^3 + 2^3 + 3^3 + \cdots + (k-1)^3 \;=\;\left[\frac{k(k-1)}{2}\right]^2 $

- Nov 25th 2007, 09:43 AMhats_06
yes thats it thanks, would you be able to prove that (by mathematical induction)?

- Nov 25th 2007, 09:58 AMtopsquark
You wish to prove

$\displaystyle \sum_{i = 1}^{k - 1}i^3 = \frac{k^2(k - 1)^2}{4}$

The base case is k = 2:

$\displaystyle \sum_{i = 1}^{1}i^3 = \frac{2^2(2 - 1)^2}{4} = 1$ (check!)

Now assume theorem is true for some value of k, say n. So we are assuming

$\displaystyle \sum_{i = 1}^{n - 1}i^3 = \frac{n^2(n - 1)^2}{4}$

Now we need to show that

$\displaystyle \sum_{i = 1}^{(n + 1) - 1}i^3 = \frac{(n + 1)^2((n + 1) - 1)^2}{4}$

or

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

The LHS is:

$\displaystyle \sum_{i = 1}^{n}i^3 = \sum_{i = 1}^{n - 1} + n^3$

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

by assumption.

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

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

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

$\displaystyle = \frac{n^4 - 2n^3 + n^2 + 4n^3}{4}$

$\displaystyle = \frac{n^4 + 2n^3 + n^2}{4}$

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

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

which is your RHS.

Thus it is true for k = 2, so it true for k = 3, etc.

-Dan - Nov 25th 2007, 10:01 AMhats_06
Thanks heaps for that!

- Nov 25th 2007, 10:05 AMtopsquark
- Nov 25th 2007, 10:31 AMSoroban
Hello again, hats_06!

I must assume you know the routine for an inductive proof.

Quote:

Prove by induction: .$\displaystyle 0^3 + 1^3 + 2^3 + 3^3 + \cdots + (n-1)^3 \;=\;\left[\frac{n(n-1)}{2}\right]^2$

Assume $\displaystyle S(k)$ is true: .$\displaystyle 0^3 + 1^3 + 2^3 + 3^3 + \cdots + (k-1)^3 \:=\:\left[\frac{k(k-1)}{2}\right]^2$

Add $\displaystyle k^3$ to both sides:

. . $\displaystyle \underbrace{1^3 + 2^3 + 3^3 + \cdots + (k-1)^3 + k^3}_{\text{This is the left side of }S(k+1)} \;=\;\left[\frac{k(k-1)}{2}\right]^2 +k^3$

The right side is: .$\displaystyle \frac{k^2(k-1)^2}{4} + k^3$

Factor: .$\displaystyle \frac{k^2}{4}\left[(k-1)^2 + 4k\right] \;=\;\frac{k^2}{4}\left[k^2-2k+1+4k\right] \;=\;\frac{k^2}{4}\left(k^2 + 2k + 1\right] $

. . . $\displaystyle = \;\frac{k^2}{4}(k+1)^2 \;=\;\underbrace{\left[\frac{k(k+1)}{2}\right]^2}_{\text{Right side of }S(k+1)} $

We have proved $\displaystyle S(k+1)\!:\;\;0^3 + 1^3 + 2^3 + \cdots + k^3 \;=\;\left[\frac{k(k+1)}{2}\right]^2$

. . The inductive proof is complete.

Ha! . . . Dan beat me to it (again) . . .

.