Mathematical induction with binomial coefficients

Question

I am trying to prove the following equation using mathematical induction: $$\sum \binom{n}{k}2^k = 3^n.$$ I am able to prove a similar induction without the $2^k$ on the left side and with $ 2^n $ on the right side, but I think this is probably a bit more complicated. Any ideas to start with? Thank you very much, I appreciate it.

Answer 1

To prove this you'll need to use the following identity

$$ {n+1\choose k}={n\choose k}+{n\choose k-1} $$

The base case is $n=1$ and here the left hand side gives

$$ \sum_{k=0}^1 {1\choose k}2^k=1+2=3 $$

and so the base case is sorted. Now for the induction hypothesis we assume

$$ \sum_{k=0}^n {n\choose k}2^k=3^n $$

Then using the identity at the start of the answer we get

\begin{align*} \sum_{k=0}^{n+1}{n+1\choose k}2^k&=\sum_{k=0}^{n+1}{n\choose k}2^k+\sum_{k=0}^{n+1}{n\choose k-1}2^k \\ &=\sum_{k=0}^n {n\choose k}2^k+\sum_{k=0}^{n+1}{n\choose k-1}2^k \hspace{10pt}\text{since ${n\choose n+1}=0$} \\ &=3^n+\sum_{k=-1}^n {n\choose k} 2^{k+1} \\ &=3^n+2\sum_{k=0}^n {n\choose k}2^k \hspace{10pt}\text{since ${n\choose -1}=0$} \\ &=3^n+2\cdot 3^n \\ &=(1+2)3^n \\ &=3^{n+1} \end{align*} and the induction step is complete. A proof of the identity at the start is not too hard and can be seen here Prove that $\binom{n+1}k = \binom nk + \binom n {k-1}$

Answer 2

$$\sum\binom{n+1}k2^k=\sum(\binom{n}{k-1}+\binom{n}{k})2^k=2\sum\binom{n}{k-1}2^{k-1}+\sum\binom{n}{k}2^k$$$$=2.3^n+3^n=3^{n+1}$$

Here $\binom{n}{k}:=0$ if $k\notin\{0,1,\dots,n\}$ and $\sum$ must be read as $\sum_{k\in\mathbb Z}$

Under this definition:$$\sum_{k\in\mathbb Z}\binom{n}{k}2^k=\sum_{k=0}^n\binom{n}{k}2^k$$