Anyone a pro at proof by mathematical induction?

**hats_06** · November 24th 2007, 11:24 PM

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

**kalagota** · November 24th 2007, 11:31 PM

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 = ?$

**Soroban** · November 25th 2007, 05:48 AM

Hello, hats_06!

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$

**hats_06** · November 25th 2007, 09:43 AM

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

**topsquark** · November 25th 2007, 09:58 AM

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

**hats_06** · November 25th 2007, 10:01 AM

Thanks heaps for that!

**topsquark** · November 25th 2007, 10:05 AM

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

**Soroban** · November 25th 2007, 10:31 AM

Hello again, hats_06!

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

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

Thread: Anyone a pro at proof by mathematical induction?

LinkBack

Thread Tools

Display

Anyone a pro at proof by mathematical induction?

Similar Math Help Forum Discussions

Proof by Mathematical Induction

Proof by mathematical induction.

Mathematical Induction Proof

Mathematical Induction Proof

proof and mathematical induction

Search Tags