Prove by induction

**Diligo** · November 21st 2012, 08:04 AM

I'm stuck on this exercise, I know I'm getting close, but I just can't see it

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

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

My right hand side simplifies to $(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

**Plato** · November 21st 2012, 08:15 AM

Originally Posted by Diligo

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

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

Then note that $\sum_{i=0}^{N+1} i2^{i - 1} =\sum_{i=0}^n i2^{i - 1} + (n )2^{n+1}$

**Diligo** · November 21st 2012, 08:56 AM

Sorry, I'm not getting the hint.

But, yes, I've checked for the base case, just omitted it for brevity.

**Plato** · November 21st 2012, 09:14 AM

Originally Posted by Diligo

Sorry, I'm not getting the hint.

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

Then $\sum_{i=0}^{N+1} i2^{i - 1} = (N)2^{N} + 1+(N )2^{N}$ .

**Diligo** · November 21st 2012, 09:30 AM

Hmm, ok, I thought it had to be: $\sum_{i=0}^{N+1}i2^{i-1}=(N - 1)2^{N}+1+(N + 1)2^{N}$

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

Now we need to show that $2^{k + 2} - 1 = 2^{k+ 1} - 1 + 2^{k + 1}$ , which of course is true.
I thought $\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

**MarkFL** · November 21st 2012, 09:57 AM

If I were to prove this by induction, after having demonstrated the base case is true, I would state the induction hypothesis $P_k$ :

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

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

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

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

Now, we are left to try to show:

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

**Diligo** · November 21st 2012, 10:10 AM

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 $3^k + 2(3^k) = 3^{k + 1}$ and in this case, why $(2k)2^k = 2k^{k +1}$

Ah, I understand the latter one, could you please provide a pointer to $3^k + 2(3^k) = 3^{k + 1}$ ?

**Plato** · November 21st 2012, 10:16 AM

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 $3^k + 2(3^k) = 3^{k + 1}$

It is simple factoring.
$3^k + 2(3^k) = 3^{k }(1+2)=3^{k }(3)=3^{k+1 }$

**Diligo** · November 21st 2012, 10:19 AM

Doh... Thanks

Thread: Prove by induction

LinkBack

Thread Tools

Display

Prove by induction

Re: Prove by induction

Re: Prove by induction

Re: Prove by induction

Re: Prove by induction

Re: Prove by induction

Re: Prove by induction

Re: Prove by induction

Re: Prove by induction

Similar Math Help Forum Discussions

Rigorously prove the principle of complete induction from mathematical induction??

prove by induction

Prove by induction

Induction to prove

Prove by Induction

Search Tags