# Proving a combinatorial identity “directly”

This is a homework problem. In the first part of the problem, I managed to use a combinatorial problem to prove the following identity:

$\Sigma_{k=0}^{n}(-1)^k {2n-k \choose k} 2^{2n-2k} = 2n+1$

But I actually have problem with the second part of the problem which asked me to prove this identity "directly", probably using some form of generating functions/algebra method.

There was a hint given but I got stuck: The hint says to calculate

$\Sigma_{n=0}^\infty\Sigma_{k=0}^{n}(-1)^k {2n-k \choose k} 2^{2n-2k} x^{2n}$

and that it would be useful to consider the fact that $\Sigma(2n+1)x^{2n}= \frac{d}{dx}\frac{x}{1-x^2}$ and $(1-x)^{-a-1}=\Sigma_{j=0}^\infty {a+j \choose j}x^j$.

I am able to prove both these "possibly useful facts" in the hint, but I don't see how to calculate the suggested double sum or prove the identity. [I would have thought that the combinatorial proof is harder to find!] [You may assume that I am familiar with the formal treatment of power series.]

Any help would be greatly appreciated.

-
How did you prove it combinatorially? I am interested. –  chubakueno Apr 9 at 18:59
Consider colouring the integers {1,...,2n} either red or blue. How many ways are there to colour them such that if i is red, then so is i-1? Obviously direct counting gives 2n+1. Use Principle of Inclusion and Exclusion for the other side. –  suncup224 Apr 9 at 20:15
Can you elaborate on how you use inclusion-exclusion? For example, what does the k=1 term count? –  ShreevatsaR Apr 10 at 2:11
–  SpamIAm Apr 10 at 5:07
Maxima's implementation of the Gosper-Zeilberger algorithm (see Petkovsek, Wilf and Zeilberger's A = B) tells me this isn't Gosper-summable. Weird. –  vonbrand Apr 10 at 11:42

We want to prove that $$\sum_{k=0}^{n}(-1)^k {2n-k \choose k} 2^{2n-2k} = 2n+1$$

Let's work backwards. The approach via generating functions is to prove it at once for all $n$ instead of a specific $n$; we are done if we can prove that $$\sum_{n=0}^{\infty} \sum_{k=0}^{n}(-1)^k {2n-k \choose k} 2^{2n-2k} x^{2n} = \sum_{n=0}^{\infty} (2n+1) x^{2n} = \frac{d}{dx} \frac{x}{1-x^2}$$

Now obviously to sum the above as written, we need to solve the original problem, so that's no help. Instead, let's interchange the sums, to sum over $k$ instead (and also write $\binom{2n-k}{k}$ as $\binom{2n-k}{2n-2k}$ to get a nicer expression): we want to prove that $$\sum_{k=0}^\infty (-1)^k \sum_{n=k}^{\infty} \binom{2n-k}{2n-2k} 2^{2n-2k} x^{2n} = \frac{d}{dx} \frac{x}{1-x^2}$$

Now let $j = n - k$, so that $n = k + j$, then our inner sum above is $$\sum_{j=0}^{\infty} \binom{k+2j}{2j}2^{2j}x^{2k+2j} = x^{2k}\sum_{j=0}^{\infty} \binom{k+2j}{2j}(2x)^{2j}$$

This sum has only the even-power terms of a sum of the form in the second hint, and picking out only the even-power terms from a power series $f(x)$ gives $\frac{f(x)+f(-x)}{2}$. Thus, the above sum is

$$x^{2k}\left(\frac{(1-2x)^{-k-1} + (1+2x)^{-k-1}}{2} \right)$$

And the whole sum becomes

$$\sum_{k=0}^{\infty} (-1)^k x^{2k} \left(\frac{(1-2x)^{-k-1} + (1+2x)^{-k-1}}{2} \right)$$ $$= \frac12\left(\frac{1}{1-2x}\sum_{k=0}^\infty\left(\frac{-x^2}{1-2x}\right)^k + \frac{1}{1+2x}\sum_{k=0}^\infty \left(\frac{-x^2}{1+2x}\right)^k\right)$$ $$= \frac12\left(\frac{1}{1-2x}\frac{1}{1-\frac{-x^2}{1-2x}} + \frac{1}{1+2x}\frac{1}{1-\frac{-x^2}{1+2x}}\right)$$ $$= \frac12\left( \frac{1}{1-2x+x^2} + \frac{1}{1+2x+x^2}\right)$$ $$= \frac12\left( \frac{1}{(1-x)^2} + \frac{1}{(1+x)^2}\right) \tag 1$$

It remains only to prove that this is the same as $\dfrac{d}{dx} \dfrac{x}{1-x^2}$, which is a simple calculus exercise.

-