Anyone a pro at proof by mathematical induction?

Printable View

November 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
November 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?

$\left( {\frac{k(k-1)}{2}} \right)^2 = ?$
November 25th 2007, 05:48 AM
Soroban

Hello, hats_06!

Quote:

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

Please state the original equation.

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

I recognize the expression.
It may have come from: . $1^3 + 2^3 + 3^3 + \cdots + (k-1)^3 \;=\;\left[\frac{k(k-1)}{2}\right]^2$
November 25th 2007, 09:43 AM
hats_06

yes thats it thanks, would you be able to prove that (by mathematical induction)?
November 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
$\sum_{i = 1}^{k - 1}i^3 = \frac{k^2(k - 1)^2}{4}$

The base case is k = 2:
$\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
$\sum_{i = 1}^{n - 1}i^3 = \frac{n^2(n - 1)^2}{4}$

Now we need to show that
$\sum_{i = 1}^{(n + 1) - 1}i^3 = \frac{(n + 1)^2((n + 1) - 1)^2}{4}$

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

The LHS is:
$\sum_{i = 1}^{n}i^3 = \sum_{i = 1}^{n - 1} + n^3$

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

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

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

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

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

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

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

$= \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
November 25th 2007, 10:01 AM
hats_06

Thanks heaps for that!
November 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
November 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: . $0^3 + 1^3 + 2^3 + 3^3 + \cdots + (n-1)^3 \;=\;\left[\frac{n(n-1)}{2}\right]^2$

Verify $S(1)\!:\;\;0^3 \:=\:\left[\frac{1(0)}{2}\right]^2 \:=\:0$ . . . True!

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

Add $k^3$ to both sides:
. . $\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: . $\frac{k^2(k-1)^2}{4} + k^3$

Factor: . $\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]$

. . . $= \;\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 $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) . . .
.