# How prove this $\sum_{k=0}^{n} \frac{\binom{2n-k}{n}}{2^{2n-k}}=1$

Show that $$\sum_{k=0}^{n}\dfrac{\binom{2n-k}{n}}{2^{2n-k}}=1$$

I think this problem can be solved with nice methods, such as algebraic ones. Or can I use probability methods? Thank you

Things may be more clear if we let $k=n-i$. Then our sum (reversed) is $$\sum_{i=0}^n \frac{\binom{n+i}{n}}{2^{n+i}}.$$ Imagine tossing a fair coin until we get $n+1$ heads or $n+1$ tails.

The number of tosses is $n+i+1$ if (i) we get exactly $n$ heads in the first $n+i$ tosses, and then a head, or (ii) we get $n$ tails in the first $n+i$ tosses and then a tail.

The probability of (i) is $\frac{\binom{n+i}{n}}{2^{n+i}}\cdot \frac{1}{2}$, and the probability of (ii) is the same. For sure the number of tosses will be one of $n+1$ to $2n+1$.

• It's very nice! Thank you, +1 – user94270 Sep 29 '13 at 16:26
• You are welcome. One can produce an "algebraic" version, but it is I believe less informative. – André Nicolas Sep 29 '13 at 16:34

Take the set of paths from $0$ to $2n$, and break it up by the smallest $k$ where the path hits $|y|=2n-x$. This gives $$\sum_{k=0}^n {2n-k\choose n-k} 2^k=4^n,$$ which is the same as your formula.

• Thank you ,It's nice, +1, I hope this problem have Algebra? – user94270 Sep 29 '13 at 16:24
• Look at (5.20) in "Concrete Mathematics" by Graham, Knuth, and Patashnik. – user940 Sep 29 '13 at 17:07
• @ByronSchmuland Beautiful! (+1) It has real elegance. I prefer it highly above my solution. – drhab Sep 30 '13 at 17:18

It is to be shown that:

$\sum_{k=0}^{n}\left({2n-k\atop n}\right)2^{-k}=2^{2n}$.

Here $\sum_{k=0}^{n}\left({2n-k\atop n}\right)2^{-k}=\sum_{k=0}^{n}\left({2n-k\atop n-k}\right)2^{-k}=2^{n}\sum_{k=0}^{n}\left({n+k\atop k}\right)2^{-k}$.

(the last equality by 'counting backwards')

So it is enough to prove that:

$s_{n}:=\sum_{k=0}^{n}\left({n+k\atop k}\right)2^{-k}=2^{n}$.

This can be done by induction on $n$. Clearly $s_{0}=1$, and the summation of $s_{n+1}$ worked out with the relation $\left({n+k+1\atop k+1}\right)=\left({n+k\atop k}\right)+\left({n+k\atop k+1}\right)$ leads to: $s_{n+1}=2^{-1}s_{n+1}+s_{n}$, i.e.

$s_{n+1}=2s_{n}$.

Suppose we seek to show that $$\sum_{k=0}^{n} {2n-k\choose n} 2^k = 2^{2n}.$$

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

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

The difference here yields two pieces, the first is $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^{n+1}} \frac{2^{n+1}/(1+z)^{n}}{1-z} \; dz \\ = \frac{2^{n+1}}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n}}{z^{n+1}} \frac{1}{1-z} \; dz.$$

This yields $$2^{n+1} \sum_{q=0}^n {n\choose q} = 2^{2n+1}.$$

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

This is $$-\sum_{q=0}^{n} {2n+1\choose q} = -\frac{1}{2} 2^{2n+1} = - 2^{2n}.$$

Combining the two pieces we have $$2^{2n+1} - 2^{2n} = 2^{2n}$$ as claimed.