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.

Solutions Collecting From Web of "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.)

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

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

If you want only the result, CAS says
$$
\frac{2\sqrt{3}}{3}(\cos\left( \frac{(4n-1)\pi}{6}\right).
$$