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

-
Have you tried computing this for the first few values of $n$? – Brian M. Scott Mar 17 '12 at 18:03
It looks like the Fibonacci numbers $$\sum_{k=0}^{\lfloor \frac{n}{2} \rfloor} {n - k \choose k} = F(n+1)$$ but with alternating signs. – Rudy the Reindeer Mar 17 '12 at 18:14
@BrianM.Scott Yes I have – Norbert Mar 17 '12 at 18:19
@Matt: You forgot the alternating sign. – Brian M. Scott Mar 17 '12 at 19:08
@Norbert: Then you know that it could also be approachable by induction. – Brian M. Scott Mar 17 '12 at 19:08

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.

-
Looks like sledgehammer, may be there is something more simple? – Norbert Mar 17 '12 at 18:51
@Norbert, Maybe the appearance of integral sign led you to think that this is an advanced proof, but actually it's not. Like logarithm is a convenient tool that transforms multiplication into addition, the gamma function integral is a convenient tool that transform factorial into power. But if you are uncomfortable with the analytic flavor in this proof, Brian M. Scott's guiding and intuitive proof will be helpful. – Sangchul Lee Mar 17 '12 at 19:21
So think how you will explain this to the first year student. And please explain interchange of summation and integration – Norbert Mar 17 '12 at 19:37
@Norbert, but 'A proof for freshmen' is not what you asked in the first time, so it's unfair to blame me for that point. You could have required such an additional condition before you post a question. Anyway, I slightly simplified Brian's answer to obtain a recurrence relation. Hope this will suffice you. – Sangchul Lee Mar 17 '12 at 19:54
Take it easy${{}}{}{}$ – Norbert Mar 17 '12 at 20:08

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

-

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

-

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

-

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

-

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

-
I've tried this way but I thought that this is a road to perdition. Anyway you solution is well fit for my needs – Norbert Mar 17 '12 at 19:39