Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
How did you prove it combinatorially? I am interested. – chubakueno Apr 9 '14 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 '14 at 20:15
Can you elaborate on how you use inclusion-exclusion? For example, what does the k=1 term count? – ShreevatsaR Apr 10 '14 at 2:11
Duplicate. – SpamIAm Apr 10 '14 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 '14 at 11:42
up vote 1 down vote accepted

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.

share|cite|improve this answer

Suppose we are trying to evaluate $$\sum_{k=0}^n {2n-k\choose k} (-1)^k 4^{n-k}.$$

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

This gives for the sum the integral $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z} \sum_{k=0}^n \frac{(-1)^k 4^{n-k}}{z^k (1+z)^k} \; dz \\ = \frac{4^n}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z} \frac{1-(-1)^{n+1}/4^{n+1}/z^{n+1}/(1+z)^{n+1}} {1+1/4/z/(1+z)} \; dz \\ = \frac{4^n}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z} \frac{4z+4z^2-(-1)^{n+1}/4^n/z^n/(1+z)^n} {1+4z+4z^2} \; dz.$$

Now this has two components. The first component is $$\frac{4^n}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z} \frac{4z+4z^2}{(1+2z)^2} \; dz = \frac{4^{n+1}}{2\pi i} \int_{|z|=\epsilon} (1+z)^{2n+1} \frac{1}{(1+2z)^2} \; dz,$$ which is easily seen to be zero.

The second component is $$\frac{4^n}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z} \frac{(-1)^n/4^n/z^n/(1+z)^n} {(1+2z)^2} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z} \frac{(-1)^n/z^n/(1+z)^n} {(1+2z)^2} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n+1}} \frac{(-1)^n} {(1+2z)^2} \; dz.$$

Extracting coeffcients from this we obtain $$(-1)^n \sum_{q=0}^n {n\choose q} (-1)^{n-q} 2^{n-q} (n-q+1).$$ This becomes $$(-1)^n (n+1) \sum_{q=0}^n {n\choose q} (-1)^{n-q} 2^{n-q} - (-1)^n \sum_{q=0}^n {n\choose q} (-1)^{n-q} 2^{n-q} q.$$ or $$(n+1)- (-1)^n \sum_{q=1}^n {n\choose q} (-1)^{n-q} 2^{n-q} q \\ = (n+1)- (-1)^n \times n\times \sum_{q=1}^n {n-1\choose q-1} (-1)^{n-q} 2^{n-q} \\ = (n+1)- (-1)^n \times n\times \sum_{q=1}^n {n-1\choose q-1} (-1)^{(n-1)-(q-1)} 2^{(n-1)-(q-1)} \\ = (n+1)- (-1)^n \times n\times (-1)^{n-1} = 2n+1.$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.