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