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.
 A: 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}$$
A: 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.)
A: 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}
$$
A: Consider the more general number $C_n$ defined as
$$
C_n = \sum_{k = 0}^{\infty} (-1)^k{n-k \choose k}
$$
where ${m \choose k} = 0$ if $k > m$.  Then your numbers are $C_{2n}$ for $n = 0, 1, 2, \dots$.  These numbers satisfy
$$
\begin{eqnarray}
C_n &=& \sum_{k = 0}^{\infty}(-1)^k\left( {n-1-k \choose k} + {n-1-k \choose k-1} \right)\\
 &=& C_{n-1} - \sum_{k = 0}^{\infty} (-1)^k {n - 2 - k \choose k}\\
 &=& C_{n-1} - C_{n-2}
\end{eqnarray} 
$$
The sequence $C_0, C_1, C_2, \dotsc$ is therefore
$$
1, 1, 0, -1, -1, 0, 1, 1, 0, -1, \dotsc
$$
and taking out the even terms $C_0, C_2, C_4, \dotsc$ gives your sequence
$$
1, 0, -1, 1, 0, -1, \dotsc
$$
In other words $C_{2n} = (2 - n \mod 3) - 1$.
A: If you want only the result, CAS says
$$
\frac{2\sqrt{3}}{3}(\cos\left( \frac{(4n-1)\pi}{6}\right).
$$
A: 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.
