Prove the identity: $\sum_{k=0}^{\frac{n}{2}}(-1)^k\binom{n-k}{k}2^{n-2k}=n+1$ 
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?
 A: 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.
