# Mathematical Induction problem

• Apr 6th 2011, 07:31 AM
Evan.Kimia
Mathematical Induction problem
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 $\displaystyle \left( k+1 \right)2^{\left( k+1 \right)+2}+2$

with $\displaystyle \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.
• Apr 6th 2011, 07:45 AM
TheEmptySet
Quote:

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 $\displaystyle \left( k+1 \right)2^{\left( k+1 \right)+2}+2$

with $\displaystyle \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 $\displaystyle n=k$ this gives

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

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

$\displaystyle \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 \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 \displaystyle (k+2)2^{k+2} +k2^{k+2}+2=[(k+2)+k]2^{k+2}+2=$
$\displaystyle \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$
• Apr 6th 2011, 07:49 AM
Evan.Kimia
perfect explanation, thanks!
• Apr 6th 2011, 11:52 AM
Quote:

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 $\displaystyle \left( k+1 \right)2^{\left( k+1 \right)+2}+2$

with $\displaystyle \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 \displaystyle\sum_{i=0}^{k+1}i2^i=k2^{k+2}+2$

Then P(k+1) is

$\displaystyle \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 \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

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

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

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

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