<s>[INST] How to compute $\sum\limits_{k=0}^n (-1)^k{2n-k\choose k}$? I got stuck at the computation of the sum 
$$
\sum\limits_{k=0}^n (-1)^k{2n-k\choose k}.
$$
I think there is no purely combinatorial proof here since the sum can achieve negative values. Could you give me solution, it seems to involve generating functions.
 [/INST] Let
$$
a_n=\sum_{k=0}^n(-1)^k\binom{n-k}{k}
$$
Noting that
$$
\sum_{n=k}^\infty\binom{n}{k}x^n=\frac{x^k}{(1-x)^{k+1}}\tag{1}
$$
we can compute the generating function of $a_n$:
$$
\newcommand{\cis}{\operatorname{cis}}
\begin{align}
\sum_{n=0}^\infty a_nx^n
&=\sum_{n=0}^\infty x^n\sum_{k=0}^n(-1)^k\binom{n-k}{k}\\
&=\sum_{k=0}^\infty\sum_{n=k}^\infty(-1)^kx^n\binom{n-k}{k}\\
&=\sum_{k=0}^\infty\sum_{n=0}^\infty(-1)^kx^{n+k}\binom{n}{k}\\
&=\sum_{k=0}^\infty(-1)^kx^k\frac{x^k}{(1-x)^{k+1}}\\
&=\frac{1}{1-x}\sum_{k=0}^\infty(-1)^k\left(\frac{x^2}{1-x}\right)^k\\
&=\frac{1}{1-x}\frac{1}{1+\frac{x^2}{1-x}}\\
&=\frac{1}{1-x+x^2}\\
&=\frac{1}{\alpha-\beta}\left(\frac{1}{x-\alpha}-\frac{1}{x-\beta}\right)\tag{2}
\end{align}
$$
where $\alpha$ and $\beta$ are the roots of $1-x+x^2=0$; $\alpha=\cis(\pi/3)$ and $\beta=\cis(-\pi/3)$.
Thus, the series for $(2)$ is
$$
\begin{align}
&\frac{1}{\cis(\pi/3)-\cis(-\pi/3)}\left(\frac{\cis(\pi/3)}{1-\cis(\pi/3)x}-\frac{\cis(-\pi/3)}{1-\cis(-\pi/3)x}\right)\\
&=\frac{2}{\sqrt{3}}\Im\left(\frac{\cis(\pi/3)}{1-\cis(\pi/3)x}\right)\\
&=\frac{2}{\sqrt{3}}\Im\left(\sum_{n=0}^\infty\cis((n+1)\pi/3)x^n\right)\tag{3}
\end{align}
$$
Therefore,
$$
a_n=\frac{2}{\sqrt{3}}\sin\left(\frac{n+1}{3}\pi\right)\tag{4}
$$
and the sequence requested above is
$$
a_{2n}=\frac{2}{\sqrt{3}}\sin\left(\frac{2n+1}{3}\pi\right)\tag{4}
$$
</s>