Prove by induction

• Nov 21st 2012, 08:04 AM
Diligo
Prove by induction
I'm stuck on this exercise, I know I'm getting close, but I just can't see it :(

Prove by induction that $\displaystyle \sum_{i=0}^n i2^{i - 1} = (n -1)2^n + 1$.

Basically this boils down to showing that $\displaystyle ((k + 1) - 1)2^{k + 1} + 1 = (k - 1)2^k + 1 + (k + 1)2^{(k + 1) - 1$, simplified: $\displaystyle 2k^{k + 1} + 1 = (k - 1)2^k + 1 + (k + 1)2^k$

My right hand side simplifies to $\displaystyle (k - 1)2^k + 1 + (k + 1)2^k = 2k^k - 2^k + 1 + 2k^k + 2^k = 4k^k + 1 \ne 2k^{k + 1} + 1$
So obviously I'm missing something and I'm afraid it's as trivial as possible, but I just don't see it at the moment :(
• Nov 21st 2012, 08:15 AM
Plato
Re: Prove by induction
Quote:

Originally Posted by Diligo
Prove by induction that $\displaystyle \sum_{i=0}^n i2^{i - 1} = (n -1)2^n + 1$.

Have you shown the base case $\displaystyle n=0$ is true.

Then note that $\displaystyle \sum_{i=0}^{N+1} i2^{i - 1} =\sum_{i=0}^n i2^{i - 1} + (n )2^{n+1}$
• Nov 21st 2012, 08:56 AM
Diligo
Re: Prove by induction
Sorry, I'm not getting the hint.

But, yes, I've checked for the base case, just omitted it for brevity.
• Nov 21st 2012, 09:14 AM
Plato
Re: Prove by induction
Quote:

Originally Posted by Diligo
Sorry, I'm not getting the hint.

If you assume that $\displaystyle \sum_{i=0}^{N} i2^{i - 1} = (N-1 )2^{N} + 1$

Then $\displaystyle \sum_{i=0}^{N+1} i2^{i - 1} = (N)2^{N} + 1+(N )2^{N}$.
• Nov 21st 2012, 09:30 AM
Diligo
Re: Prove by induction
Hmm, ok, I thought it had to be: $\displaystyle \sum_{i=0}^{N+1}i2^{i-1}=(N - 1)2^{N}+1+(N + 1)2^{N}$

Take for example $\displaystyle \sum_{i = 0}^n 2^i = 2^{n + 1} - 1$

Now we need to show that $\displaystyle 2^{k + 2} - 1 = 2^{k+ 1} - 1 + 2^{k + 1}$, which of course is true.
I thought $\displaystyle \sum_{i=0}^{N+1}i2^{i-1}=(N - 1)2^{N}+1+(N + 1)2^{N}$ was analog to that? I fill in k + 1 in the LHS and add that to the RHS.

Is it possible you explain your answer a bit further? Would help me tremendously, apparently I don't understand it quite as good as I'm supposed to :)
• Nov 21st 2012, 09:57 AM
MarkFL
Re: Prove by induction
If I were to prove this by induction, after having demonstrated the base case is true, I would state the induction hypothesis $\displaystyle P_k$:

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

Next, add $\displaystyle (k+1)2^k$ to both sides:

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

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

Now, we are left to try to show:

$\displaystyle ((k-1)+(k+1))2^k=((k+1)-1)2^{k+1}$
• Nov 21st 2012, 10:10 AM
Diligo
Re: Prove by induction
Thats exactly what I was trying. I've identified what's going wrong by working trough another example. And it's actually very basic...

I fail to understand why, for example $\displaystyle 3^k + 2(3^k) = 3^{k + 1}$ and in this case, why $\displaystyle (2k)2^k = 2k^{k +1}$ (Doh)
Ah, I understand the latter one, could you please provide a pointer to$\displaystyle 3^k + 2(3^k) = 3^{k + 1}$?
• Nov 21st 2012, 10:16 AM
Plato
Re: Prove by induction
Quote:

Originally Posted by Diligo
Thats exactly what I was trying. I've identified what's going wrong by working trough another example. And it's actually very basic...

I fail to understand why, for example $\displaystyle 3^k + 2(3^k) = 3^{k + 1}$

It is simple factoring.
$\displaystyle 3^k + 2(3^k) = 3^{k }(1+2)=3^{k }(3)=3^{k+1 }$
• Nov 21st 2012, 10:19 AM
Diligo
Re: Prove by induction
Doh... Thanks :)