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.
[Math] Mathematical induction with binomial coefficients
induction
Best Answer
$$\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$$