How to compute $\sum\limits_{k=0}^n (-1)^k{2n-k\choose k}$?

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.

This is not going to be a nice answer. Rather, it will illustrate how one might attack the problem from scratch, without using anything especially sophisticated.

Let $$a_n=\sum_{k=0}^n(-1)^n\binom{2n-k}k\;.$$

From Pascal’s triangle we have

$$\begin{align*} \binom{2(n+1)-k}k&=\binom{2n+1-k}{k-1}+\binom{2n+1-k}k\\ &=\binom{2n-k}{k-2}+2\binom{2n-k}{k-1}+\binom{2n-k}k\;, \end{align*}$$

so $$\begin{align*} \sum_{k=0}^{n+1}(-1)^k\binom{2(n+1)-k}k&=\sum_{k=0}^{n+1}(-1)^k\left(\binom{2n-k}{k-2}+2\binom{2n-k}{k-1}+\binom{2n-k}k\right)\\ &=\sum_{k=0}^{n+1}(-1)^k\binom{2n-k}{k-2}+2\sum_{k=0}^{n+1}(-1)^k\binom{2n-k}{k-1}+\\ &\qquad\qquad+\sum_{k=0}^{n+1}(-1)^k\binom{2n-k}k\\ &=\sum_{k=0}^{n-1}(-1)^k\binom{2(n-1)-k}k-2\sum_{k=0}^{n-1}(-1)^k\binom{2n-1-k}k+\\ &\qquad\qquad+\sum_{k=0}^n(-1)^k\binom{2n-k}k\;, \end{align*}$$

or $$a_{n+1}=a_{n-1}+a_n-2\sum_{k=0}^{n-1}(-1)^k\binom{2n-1-k}k\;.\tag{0}$$

If we could get a handle on the summation on the righthand side, we’d be in business. Now

$$\begin{align*} \sum_{k=0}^{n-1}(-1)^k\binom{2n-1-k}k&=\sum_{k=0}^{n-1}(-1)^k\left(\binom{2(n-1)-k}k+\binom{2(n-1)-k}{k-1}\right)\\ &=\sum_{k=0}^{n-1}(-1)^k\binom{2(n-1)-k}k-\sum_{k=0}^{n-2}(-1)^k\binom{2(n-1)-1-k}k\\ &=a_{n-1}-\sum_{k=0}^{n-2}(-1)^k\binom{2(n-1)-1-k}k\;,\tag{1} \end{align*}$$

where the summation on the righthand side is just like the one on the lefthand side, but with $n$ replaced by $n-1$. That suggests that we should let $$b_n=\sum_{k=0}^{n-1}(-1)^k\binom{2n-1-k}k$$ and write $(1)$ as $$b_n=a_{n-1}-b_{n-1}\;.$$ Since $b_0=0$, this boils down to $$b_n=\sum_{k=0}^{n-1}(-1)^{n-1-k}a_k\;,$$ while $(0)$ can be rewritten as $$a_{n+1}=a_n+a_{n-1}-2b_n=a_n-a_{n-1}+2\sum_{k=0}^{n-2}(-1)^{n-k}a_k\;.$$

In particular, $$a_{n+3}=a_{n+2}-a_{n+1}+2\sum_{k=0}^n(-1)^{n-k}a_k\;,\tag{2}$$ and you know that $a_0=1,a_1=0,a_2=-1$, and the sequence seems to repeat with a period of $3$. Can you now use $(2)$ to show by induction that this is actually the case?

Specifically, you’ll want to show by simultaneous induction that

$$a_n=\begin{cases} 1,&\text{if }n\equiv 0\pmod 3\\ 0,&\text{if }n\equiv 1\pmod 3\\ -1,&\text{if }n\equiv 2\pmod 3\;, \end{cases}$$ and $$b_n=\begin{cases} 1,&\text{if }n\equiv 0\pmod 3\\ -1,&\text{if }n\equiv 1\pmod 3\\ 0,&\text{if }n\equiv 2\pmod 3\;. \end{cases}$$

There is a combinatorial proof.

First, $\binom{2n-k}{k}$ is the number of ways to tile a line board of $2n$ cells with $k$ dominoes and $2n-2k$ squares. (Dominoes take up two cells, and squares take up one.) This is because you have $2n-k$ total tiles in such a tiling, and there are $\binom{2n-k}{k}$ ways to choose which ones are dominoes.

Thus $$\sum_{k=0}^n \binom{2n-k}{k} (-1)^k$$ is the difference in the number of tilings of a $2n$-board that use an even number of dominoes and the number of tilings that use an odd number of dominoes.

We'll say that a tiling is unbreakable at cell $k$ if a domino occupies cells $k$ and $k+1$.

From here, we'll proceed in cases. Suppose $2n\equiv 2\pmod 3$. Given a tiling of the $2n$-board, find the first breakable cell of the form $3j+2$. There must be such a cell because the last cell is of this form. For there to be no breakable cells of the form $3i+2$ for $i < j$ the tiling must be of the form square, domino, square, domino, etc., up through cell $3j$. If cells $3j+1$ and $3j+2$ are covered by a domino, break it into two squares. If cells $3j+1$ and $3j+2$ are covered by two squares, replace them with a domino. This mapping is reversible, and it changes the parity of the number of dominoes. Thus, when $2n\equiv 2\pmod 3$ there are as many even tilings of the $2n$-board as there are odd tilings, as every tiling in this case must have at least one breakable cell of the form $3j+2$.

If $2n \not\equiv 2 \pmod 3$, then there is exactly one tiling that is unbreakable at all cells of the form $3j+2$. If $2n \equiv 0 \pmod 3$, then this is the tiling that consists of square, domino, square, domino, etc., for the entire length of the board, ending in a domino. Thus in this tiling there are $d$ dominoes and $s$ squares such that $2n = 2d+s = 3d$, since $d=s$ in this case. But if $3d = 2n$, then $2|d$, and so the leftover tiling has even parity.

If $2n \equiv 1 \pmod 3$, then the leftover tiling consists of square, domino, square, domino, etc., for the entire length of the board, ending in a square. Thus in this tiling $d+1 = s$, and so we get $2n = 2d+s = 3d+1$. This means means that $d$ cannot be divisible by $2$, and so the leftover tiling has odd parity.

Putting all three cases together we get $$ \sum_{k=0}^n \binom{2n-k}{k} (-1)^k =\begin{cases} 1,&\text{if }2n\equiv 0\pmod 3;\\ -1,&\text{if }2n\equiv 1\pmod 3;\\ 0,&\text{if }2n\equiv 2\pmod 3. \end{cases}$$

(Reference: Identity 172, pages 85-86, in Benjamin and Quinn's Proofs that Really Count.)