Mathematical Induction problem

**Evan.Kimia** · April 6th 2011, 07:31 AM

problem #14 on here:

This is what ive done so far:
1.) prove that the 2 equations are equal by testing P(n) at 0. They are, so i proceed to the inductive step and rewrite the equation in terms of k.

2.) I then try nd show for all integers > or equal to k if P9K) is true then P(k+1) is also true.

I do this by equating $\left( k+1 \right)2^{\left( k+1 \right)+2}+2$

with $\sum_{i=0}^{k+1}{k2^{k}}+k^{k+1}$

then attempt to turn it into what got for P(k+1), but im pretty sure i messed up making the last term explicit.

**TheEmptySet** · April 6th 2011, 07:45 AM

Originally Posted by Evan.Kimia

problem #14 on here:

This is what ive done so far:
1.) prove that the 2 equations are equal by testing P(n) at 0. They are, so i proceed to the inductive step and rewrite the equation in terms of k.

2.) I then try nd show for all integers > or equal to k if P9K) is true then P(k+1) is also true.

I do this by equating $\left( k+1 \right)2^{\left( k+1 \right)+2}+2$

with $\sum_{i=0}^{k+1}{k2^{k}}+k^{k+1}$

then attempt to turn it into what got for P(k+1), but im pretty sure i messed up making the last term explicit.

So just to be clear after checking the bases case
we assume the induction hypothesis for $n=k$ this gives

$\displaystyle \sum_{i=1}^{k+1}i2^i=k2^{k+2}+2$

Now we need to use this to show $k+1$ starting with the left hand side we get

$\displaystyle \sum_{i=1}^{(k+1)+1}i2^i=\displaystyle \sum_{i=1}^{k+2}i2^i$

Now lets pull the last term out of the sum to get

$\displaystyle (k+2)2^{k+2} +\sum_{i=1}^{k+1}i2^i$

Now the sum is the induction hypothesis so we replace it with

$\displaystyle (k+2)2^{k+2} +k2^{k+2}+2=[(k+2)+k]2^{k+2}+2=$
$\displaystyle [2k+2]2^{k+2}+2=2(k+1)2^{k+2}+2=(k+1)2^{k+3}+2 =(k+1)2^{(k+1)+2}+2$

**Evan.Kimia** · April 6th 2011, 07:49 AM

perfect explanation, thanks!

**Archie Meade** · April 6th 2011, 11:52 AM

Originally Posted by Evan.Kimia

problem #14 on here:

This is what ive done so far:
1.) prove that the 2 equations are equal by testing P(n) at 0. They are, so i proceed to the inductive step and rewrite the equation in terms of k.

2.) I then try nd show for all integers > or equal to k if P9K) is true then P(k+1) is also true.

I do this by equating $\left( k+1 \right)2^{\left( k+1 \right)+2}+2$

with $\sum_{i=0}^{k+1}{k2^{k}}+k^{k+1}$ this part is incorrect

then attempt to turn it into what got for P(k+1), but im pretty sure i messed up making the last term explicit.

P(k) is

$\displaystyle\sum_{i=0}^{k+1}i2^i=k2^{k+2}+2$

Then P(k+1) is

$\displaystyle\sum_{i=0}^{k+2}i2^i=(k+1)2^{k+3}+2$

To prove that the Domino-effect exists
true for n=0 implies true for n=1
true for n=1 implies true for n=2
true for n=2 implies true for n=3
true for n=3 implies true for n=4
to infinity.

Hence we try to show that P(k) being true forces P(k+1) to be true..

$\displaystyle\sum_{i=0}^{k+2}i2^i=\sum_{i=0}^{k+1} i2^i+(k+2)2^{k+2}$

and "if" P(k) is true, this will be

$k2^{k+2}+2+(k+2)2^{k+2}$

$=k2^{k+2}+2+k2^{k+2}+2^{k+3}$

$=2k2^{k+2}+2^{k+3}+2=k2^{k+3}+2^{k+3}+2$

$=(k+1)2^{k+3}+2$

Thread: Mathematical Induction problem

LinkBack

Thread Tools

Display

Mathematical Induction problem

Similar Math Help Forum Discussions

[SOLVED] mathematical induction problem

Mathematical Induction Problem

mathematical induction problem

mathematical induction problem no.2

mathematical induction problem

Search Tags