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.

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.
