<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] Indeed, generating function method works. Let $c_n$ denoe the given sum. Then we have
$$\begin{align*}
\sum_{n=0}^{\infty} c_n y^{2n}
&= \sum_{n=0}^{\infty} \sum_{k=0}^{n} \frac{(-1)^k y^{2n}}{(2n-2k)!k!} \int_{0}^{\infty} x^{2n-k} e^{-x} \; dx \\
&= \int_{0}^{\infty} \sum_{k=0}^{n} \sum_{n=0}^{\infty} \frac{(yx)^{2n-2k}}{(2n-2k)!} \frac{(-y^2 x)^k}{k!} e^{-x} \; dx \\
&= \int_{0}^{\infty} \cosh(yx) e^{-(y^2+1)x} \; dx \\
&= \int_{0}^{\infty} \frac{1}{2} \left( e^{-(y^2-y+1)x} + e^{-(y^2+y+1)x} \right) \; dx \\
&= \frac{1}{2} \left( \frac{1}{y^2 - y + 1} + \frac{1}{y^2 + y + 1} \right) \\
&= \frac{1 - y^4}{1 - y^6} \\
&= 1 - y^4 + y^6 - y^{10} + \cdots.
\end{align*}$$
Thus by comparing the coefficients, we have
$$ c_n = \begin{cases}
1 & n \equiv 0 \ (\mathrm{mod} \ 3) \\ 
0 & n \equiv 1 \ (\mathrm{mod} \ 3) \\ 
-1 & n \equiv 2 \ (\mathrm{mod} \ 3)
\end{cases}.$$
Similar calculation also shows that
$$ \sum_{k=0}^{n} \binom{2n-k}{k} = F_{2n+1},$$
where $F_0 = 0, F_1 = 1$ and $F_{n+2} = F_{n+1} + F_n$ is the Fibonacci sequence.

Okay, here is a direct approach, motivated by Brain M. Scott's illuminating answer. By Pascal's triangle,
$$\begin{align*}
c_{n+1}
&= \sum_{k=0}^{n+1}(-1)^k \binom{2n+2-k}{k} \\
&= \sum_{k=0}^{n+1}(-1)^k \binom{2n+1-k}{k-1} + \sum_{k=0}^{n+1}(-1)^k \binom{2n+1-k}{k} \\
&= - \sum_{k=0}^{n+1}(-1)^k \binom{2n-k}{k} + \sum_{k=0}^{n+1}(-1)^k \binom{2n+1-k}{k} \\
&= - c_n + \sum_{k=0}^{n+1}(-1)^k \binom{2n+1-k}{k}.
\end{align*}$$
But applying exactly the same technique to the last sum, we have
$$\begin{align*}
\sum_{k=0}^{n+1}(-1)^k \binom{2n+1-k}{k}
&= \sum_{k=0}^{n+1}(-1)^k \binom{2n-k}{k-1} + \sum_{k=0}^{n+1}(-1)^k \binom{2n-k}{k} \\
&= - \sum_{k=0}^{n}(-1)^k \binom{2n-1-k}{k} + \sum_{k=0}^{n}(-1)^k \binom{2n-k}{k} \\
&= - \sum_{k=0}^{n}(-1)^k \binom{2n-1-k}{k} + c_n.
\end{align*}$$
Plugging back, we obtain
$$ c_{n+1} = - \sum_{k=0}^{n}(-1)^k \binom{2n-1-k}{k}.$$
Thus we have
$$c_{n+1}
= - c_n + \sum_{k=0}^{n+1}(-1)^k \binom{2n+1-k}{k}
= - c_n - c_{n+2},$$
or equivalently
$$c_{n+2} + c_{n+1} + c_n = 0.$$
So we have $c_{n+3} = c_n$ and the proof is complete.
</s>