1. ## 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 $\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

2. ## Re: Prove by induction

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}$

3. ## 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.

4. ## Re: Prove by induction

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}$.

5. ## Re: Prove by induction

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

6. ## 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 $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}$

7. ## 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 $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}$?

8. ## Re: Prove by induction

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 }$

9. ## Re: Prove by induction

Doh... Thanks