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.
How to compute $\sum\limits_{k=0}^n (-1)^k{2n-k\choose k}$?
-
0@Matt: So you did; I honestly didn’t see the last line. (And of course the actual values behave rather differently!) – 2012-03-17
6 Answers
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.
-
1Take it easy${{}}{}{}$ – 2012-03-17
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}$
-
0I've tried this way but I thought that this is a road to perdition. Anyway you solution is well fit for my needs – 2012-03-17
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). $