# Anyone a pro at proof by mathematical induction?

• Nov 24th 2007, 11:24 PM
hats_06
Anyone 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 PM
kalagota
Quote:

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

where is it equal to or what?

$\displaystyle \left( {\frac{k(k-1)}{2}} \right)^2 = ?$
• Nov 25th 2007, 05:48 AM
Soroban
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 AM
hats_06
yes thats it thanks, would you be able to prove that (by mathematical induction)?
• Nov 25th 2007, 09:58 AM
topsquark
Quote:

Originally Posted by hats_06
yes thats it thanks, would you be able to prove that (by mathematical induction)?

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}$

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

-Dan
• Nov 25th 2007, 10:01 AM
hats_06
Thanks heaps for that!
• Nov 25th 2007, 10:05 AM
topsquark
Quote:

Originally Posted by hats_06
Thanks heaps for that!

Induction proofs usually all follow the same pattern in that they use the assumption case (k = n) to simplify the LHS of the equation to make it easier to get it into the form on the RHS.

-Dan
• Nov 25th 2007, 10:31 AM
Soroban
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$
Verify $\displaystyle S(1)\!:\;\;0^3 \:=\:\left[\frac{1(0)}{2}\right]^2 \:=\:0$ . . . True!

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) . . .
.