How does one use induction to prove that $\displaystyle\sum\limits_{k=1}^{n}k2^{n-k+1} = 2^{n+2}-2(n+2)$

Question

I am unsure how to use induction to prove this expression. I am not even sure how to begin. My textbook says to start with a "left hand sum" and "right hand sum" but I don't know what this means. Can someone with more experience in discrete mathematics explain how to do this?

$\displaystyle\sum\limits_{k=1}^{n}k2^{n-k+1} = 2^{n+2}-2(n+2)$

Answer 1

Begin with the base case. Is it true for $n=0$ (or $n=1$)?

Then assume it's true for $m$: $$\sum\limits_{k=1}^m k2^{m-k+1}=2^{m+2}-2(m+2).\tag1$$

Now show it's true for $m+1$:

$$\sum\limits_{k=1}^{m+1} k2^{m+1-k+1}=2^{m+1+2}-2(m+1+2).\tag2$$

Note that from taking $(2)-2\times(1)$, you need to show

$$(m+1)2=2m+2,$$

which is easy.

Answer 2

We start with the base step. For $n=1$ the LHS becomes $$1 \cdot 2^{1-1+1}=2=8-6=2^{1+2}-2(1+2)$$ So, it is true for $n=1$.

For the inductive step, assume that it is true for $n=m$, that is $$\sum_{k=1}^m k2^{m-k+1}=2^{m+2}-2(m+2)$$

We must show that it is true for $n=m+1$. Note that \begin{aligned} \sum_{k=1}^{m+1} k2^{(m+1)-k+1} &= \sum_{k=1}^m k2^{(m+1)-k+1} + (m+1)2^{(m+1)-(m+1)+1} \\ &= 2\sum_{k=1}^{m} k2^{m-k+1} + 2(m+1) \end{aligned}

By our inductive hypotesis, we get \begin{aligned} \sum_{k=1}^{m+1} k2^{(m+1)-k+1} &= 2(2^{m+2}-2(m+2)) + 2(m+1) \\ &= 2^{m+3}-4m-8+2m+2 \\ &= 2^{m+3}-2(m+3) \end{aligned}

So, it is also true for $n=m+1$.