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.

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}$$
