Prove the identity: $\sum_{k=0}^{\frac{n}{2}}(-1)^k\binom{n-k}{k}2^{n-2k}=n+1$

Question

Prove the identity: $$\sum_{k=0}^{\frac{n}{2}}(-1)^k\binom{n-k}{k}2^{n-2k}=n+1$$

To prove this by induction is useless. I guess the best one solution would be to prove this by generating functions. Does anybody know how can I prove this equation?

Answer 1

P.S. One more proof (different from what you can find here: Proving combinatorial identity $\sum_{k=0}^{n}(-1)^k \binom{2n-k}k 2^{2n-2k} = 2n+1$ "directly" , and Another combinatorics problem: $\sum\limits_{k = 0}^n (-1)^k \binom{2n-k}k2^{2n-2k}=2n+1$).

Let $$S(n)=\sum_{k\geq 0}(-1)^k\binom{n-k}{k}2^{n-2k}$$ (note by convention, $\binom{m}{k}=0$ when $k<0$ or $k>m>0$). Then for $n\geq 1$, $$ \begin{align} S(n+1)&=\sum_{k\geq 0}(-1)^k\binom{n+1-k}{k}2^{n+1-2k}\\&= \sum_{k\geq 0}(-1)^k\left(\binom{n-k}{k-1}+\binom{n-k}{k}\right)2^{n+1-2k}\\ &= \sum_{k\geq 1}(-1)^k\binom{n-k}{k-1} 2^{n+1-2k}+\sum_{k\geq 0}(-1)^k\binom{n-k}{k}2^{n+1-2k}\\ &= -\sum_{j\geq 0}(-1)^j\binom{n-1-j}{j} 2^{n-1-2j}+2\sum_{k\geq 0}(-1)^k\binom{n-k}{k}2^{n-2k}\\ &=-S(n-1)+2S(n). \end{align}$$ The above recurrence could be useful for the inductive step of a proof by induction.

For a generating function approach, let $F(x)=\sum_{n\geq 0}S(n)x^n$. Hence $$\sum_{n\geq 1}S(n+1)x^{n+1}=-x^2\sum_{n\geq 1}S(n-1)x^{n-1}+2x\sum_{n\geq 1}S(n)x^{n},$$ that is $$F(x)-S(0)-S(1)x=-x^2F(x)+2x(F(x)-S(0))\implies F(x)=\frac{1}{(x-1)^2}$$ and we are done.