Compute $\sum\limits_{k=0}^n\left(-1\right)^k\binom{2n-k}k$

Question

$$S_n=\sum _{k=0}^n\left(-1\right)^k\binom{2n-k}k=\begin{cases} 1 & n\equiv0\pmod3 \\ 0 & n\equiv1\pmod3\\ -1 & n\equiv-1\pmod3 \end{cases} $$

I can show that $S_1 = 0$, $S_2 = -1$, and $S_3 = 1$. But how to show it for $S_n$?

Answer 1

The easiest way, perhaps, is to prove a bit more. Define

$$s_n=\sum_k(-1)^k\binom{n-k}k\;,$$

so that $S_n=s_{2n}$. (Note that there is no need to specify limits on $k$: only finitely many terms are non-zero, since $\binom{n}k=0$ if $k>n$ or $k<0$, and those are the ones that we want.) Then

$$\begin{align*} s_{n+1}&=\sum_k(-1)^k\binom{n+1-k}k\\ &=\sum_k(-1)^k\left(\binom{n-k}k+\binom{n-k}{k-1}\right)\\ &=\sum_k(-1)^k\binom{n-k}k+\sum_k(-1)^{k+1}\binom{n-1-k}k\\ &=s_n-\sum_k(-1)^k\binom{n-1-k}k\\ &=s_n-s_{n-1}\;. \end{align*}$$

Now $s_0=1=s_1$, and an easy induction establishes the result that

$$s_n=\begin{cases} 1,&\text{if }n\equiv0\pmod6\\ 1,&\text{if }n\equiv1\pmod6\\ 0,&\text{if }n\equiv2\pmod6\\ -1,&\text{if }n\equiv3\pmod6\\ -1,&\text{if }n\equiv4\pmod6\\ 0,&\text{if }n\equiv5\pmod6\;, \end{cases}$$

from which the desired result for $S_n$ follows at once.

Answer 2

Suppose we seek to evaluate

$$Q_n = \sum_{k=0}^n (-1)^k {2n-k\choose k} = \sum_{k=0}^n (-1)^k {2n-k\choose 2n-2k}.$$

Introduce

$${2n-k\choose 2n-2k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2n-2k+1}} (1+z)^{2n-k} \; dz.$$

Observe that this vanishes for $k\gt n$ so we may extend the range of $k$ in the sum to infinity, getting

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2n+1}} (1+z)^{2n} \sum_{k\ge 0} (-1)^k \frac{z^{2k}}{(1+z)^{k}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2n+1}} (1+z)^{2n} \frac{1}{1+z^2/(1+z)} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2n+1}} (1+z)^{2n+1} \frac{1}{1+z+z^2} \; dz.$$

Now put $w = z/(1+z)$ so that $z=w/(1-w)$ and $dz = 1/(1-w)^2 dw$ which takes $z=0$ to $w=0$ to get

$$\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{2n+1}} \frac{1}{1+w/(1-w)+w^2/(1-w)^2} \frac{1}{(1-w)^2} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{2n+1}} \frac{1}{1-2w+w^2+w(1-w)+w^2} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{2n+1}} \frac{1}{1-w+w^2} \; dw.$$

Solving $1-w+w^2=0$ we obtain the two roots

$$\rho_{0,1} = -\exp(\pm 2\pi i/3)$$

which yield

$$\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{2n+1}} \frac{1}{(w-\rho_0)(w-\rho_1)} \; dw.$$

The residues sum to zero so we get from the four poles at $0$, $\rho_0$, $\rho_1$ and infinity

$$Q_n + \frac{1}{\rho_0-\rho_1} \rho_0^{-2n-1} + \frac{1}{\rho_1-\rho_0} \rho_1^{-2n-1} + \mathrm{Res}_{w=\infty} \frac{1}{w^{2n+1}} \frac{1}{1-w+w^2} = 0.$$

The last term is

$$-\mathrm{Res}_{w=0} \frac{1}{w^2} w^{2n+1} \frac{1}{1-1/w+1/w^2} = -\mathrm{Res}_{w=0} w^{2n+1} \frac{1}{w^2-w+1} = 0.$$

We thus obtain the closed form

$$Q_n + \frac{1}{\rho_0-\rho_1} \rho_0^{-2n-1} - \frac{1}{\rho_0-\rho_1} \rho_1^{-2n-1} = 0$$

or $$Q_n = \frac{1}{\rho_0-\rho_1} (\rho_1^{-2n-1} - \rho_0^{-2n-1}) \\ = \frac{1}{\rho_1-\rho_0} (\exp(-2\pi i(-2n-1)/3)-\exp(2\pi i(-2n-1)/3)) \\ = \frac{2i}{\rho_1-\rho_0} \sin(-2\pi(-2n-1)/3) \\ = \frac{2}{3}\sqrt{3} \sin(2\pi(2n+1)/3).$$

Now observe that

$$Q_{n+3} = \frac{2}{3}\sqrt{3} \sin(2\pi(2n+1)/3+4\pi) = Q_n$$

hence the sequence is periodic with period three. Furthermore

$$Q_0 = \frac{2}{3}\sqrt{3}\sin(2\pi/3) = 1,\; Q_1 = \frac{2}{3}\sqrt{3} \sin(2\pi) = 0, \\ \text{and}\quad Q_2 = \frac{2}{3}\sqrt{3}\sin(10\pi/3) = -1.$$

Therefore the sequence $Q_n$ is

$$1, 0, -1, 1, 0, -1, 1, 0, -1, \ldots$$

as claimed.