Take the 2-minute tour ×
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.

Here is an interesting series I ran across.

It is a binomial-type identity.

$\displaystyle \sum_{k=0}^{n}\frac{(2n-k)!\cdot 2^{k}}{(n-k)!}=4^{n}\cdot n!$

I tried all sorts of playing around, but could not get it to work out.

This works out the same as $\displaystyle 2^{n}\prod_{k=1}^{n}2k=2^{n}\cdot 2^{n}\cdot n!=4^{n}\cdot n!$

I tried equating these somehow, but I could not get it. I even wrote out the series.

There were cancellations, but it did not look like the product of the even numbers.

$\displaystyle \frac{(2n)!}{n!}+\frac{(2n-1)!\cdot 2}{(n-1)!}+\frac{(2n-2)!2^{2}}{(n-2)!}+\cdot\cdot\cdot +n!\cdot 2^{n}=4^{n}\cdot n!$.

How can the closed form be derived from this?. I bet I am just being thick. I see the last term is nearly the result except for being multiplied by $2^{n}$. I see if the factorials are written out, $2n(2n-1)(2n-2)(2n-3)\dots$ for example, then 2's factor out of $2n, \;\ 2n-2$ (even terms) in the numerator.

There is even a general form I ran through Maple. It actually gave a closed from for it as well, but I would have no idea how to derive it.

$\displaystyle \sum_{k=0}^{n}\frac{(2n-k)!\cdot 2^{k}\cdot (k+m)!}{(n-k)!\cdot k!}$.

In the above case, m=0. But, apparently there is a closed form for $m\in \mathbb{N}$ as well.

Maple gave the solution in terms of Gamma: $\displaystyle \frac{\Gamma(1+m)4^{n}\Gamma(n+1+\frac{m}{2})}{\Gamma(1+\frac{m}{2})}$

Would anyone have an idea how to proceed with this?. Perhaps writing it in terms of Gamma and using some identities?. Thanks very much.

share|improve this question
    
Your "general form" doesn't make sense if $m$ is a positive integer, because you'll get factorials of negative integers: $(k-m)!$. Perhaps you mean $(m-k)!$ instead? –  Robert Israel Dec 30 '11 at 18:25
1  
If you flip the summation order of your first sum, it becomes $$2^n n!\sum\limits_{k=0}^n \binom{n+k}{k}\frac1{2^k}$$ –  J. M. Dec 30 '11 at 18:47

4 Answers 4

up vote 5 down vote accepted

$$ \begin{align} \sum_{k=0}^{n}\frac{(2n-k)!}{(n-k)!}2^k\tag{1} &=n!\sum_{k=0}^n\binom{2n-k}{n-k}\sum_{j=0}^k\binom{k}{j}\\\tag{2} &=n!\sum_{k=0}^n\sum_{j=0}^{n-k}\binom{n+k}{k}\binom{n-k}{j}\\\tag{3} &=n!\sum_{j=0}^n\sum_{k=0}^{n-j}\binom{n+k}{n}\binom{n-k}{j}\\\tag{4} &=n!\sum_{j=0}^n\binom{2n+1}{n+j+1}\\\tag{5} &=n!\;2^{2n} \end{align} $$

  1. rewrite $2^k$

  2. $k\mapsto n-k$

  3. change order of summation and $\binom{n}{k}=\binom{n}{n-k}$

  4. $\sum_k\binom{n-k}{i}\binom{m+k}{j}=\binom{n+m+1}{i+j+1}$

  5. Split $\sum_j\binom{2n+1}{j}=2^{2n+1}$ in half

share|improve this answer
1  
A virtuoso use of binomial coefficient identities! –  Mike Spivey Dec 31 '11 at 3:54

Here's a combinatorial proof for J.M.'s reformulation (after dividing out $n!$):

$$\sum\limits_{k=0}^n \binom{n+k}{k} 2^{n-k}= 4^n.$$

Suppose you flip coins until you obtain either $n+1$ heads or $n+1$ tails. After either heads or tails "wins" you keep flipping until you have a total of $2n+1$ coin flips. The two sides count the number of ways for heads to win.

For the left side: Condition on the number of tails $k$ obtained before head $n+1$. There are $\binom{n+k}{k}$ ways to choose the positions at which these $k$ tails occurred from the $n+k$ total options, and then $2^{n-k}$ possibilities for the remaining flips after head $n+1$. Summing up yields the left side.

For the right side: Heads wins on half of the total number of sequences; i.e., $\frac{1}{2}(2^{2n+1}) = 4^n$.

share|improve this answer
1  
Nice! More direct than my detour through Concrete Mathematics. –  Byron Schmuland Dec 30 '11 at 20:05

Dividing out $2^n\cdot n!$ and changing variables, your equation follows from (5.20) on page 167 of Concrete Mathematics by Graham, Knuth, and Patashnik. If you don't have this reference, I can add more details later.

$$\sum_{k\leq m}{m+k\choose k}2^{-k}=2^m\qquad\text{integer}\quad m\geq 0.\qquad\qquad (5.20)$$


Just for fun, here is a probabilistic proof of (5.20). Suppose we toss a fair coin until we see either $m+1$ heads or $m+1$ tails. Let $J$ be the number of trials prior to the final toss, and consider $\mathbb{P}(J=j)$ for $m\leq j\leq 2m$. We get $J=j$ by either $m$ heads in the first $j$ tosses followed by a head, or $m$ tails in the first $j$ tosses followed by a tail. By symmetry, we find $$\mathbb{P}(J=j)=2{j\choose m}\left({1\over 2}\right)^j\left({1\over 2}\right) ={j\choose m}\left({1\over 2}\right)^j.$$

Since the total probability adds to one, we get $$\sum_{m\leq j\leq 2m} {j\choose m}\left({1\over 2}\right)^j=1.$$ Putting $k=j-m$ in this sum and multiplying by $2^m$ gives (5.20).

share|improve this answer
1  
Interesting reference (GKP) thanks! Page 247 they propose to prove that $\sum_{k\gt m}{m+k\choose k}2^{-k}=2^m$ using the additional fact that $(1-x)^{-1-n} = \sum^{\infty}_{k=0} \binom{k+n}{n} x^k$ (see (mathoverflow.net/questions/84523/an-asymptotic-question)) –  Raymond Manzoni Dec 30 '11 at 19:21
    
@Raymond Thanks for the link! –  Byron Schmuland Dec 30 '11 at 19:59
    
I am so sorry. I had a typo in the original post. I even looked it over to make sure and still missed it. That should have been $(k+m)!$. I made some edits. Of course, that changed the closed form which can be written with factorials instead of Gamma: $\displaystyle \frac{m!4^{n}(n+\frac{m}{2})!}{(\frac{m}{2})!}$. Again, my apologies and thanks for all the responses. No, I do not have Concrete Mathematics, but I think I can obtain it. I will look into it. Thanks –  Cody Dec 30 '11 at 22:22
2  
@Cody: you definitely should; it's a nice book to have! –  J. M. Dec 31 '11 at 0:35

This identity can be re-written as $$\sum_{k=0}^n {2n-k \choose n-k} 2^k = 4^n.$$

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

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

We can extend the sum to infinity because when $n-k+1 \le 0$ or $k \ge n+1$ the integrand of the defining integral of the binomial coefficient is an entire function and the integral is zero. This yields

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

Thus the value of the integral is given by $$[z^n] \frac{1}{1-z} (1+z)^{2n+1} = \sum_{q=0}^n {2n+1\choose q} = \frac{1}{2} 2^{2n+1} = 4^n.$$

A trace as to when this method appeared on MSE and by whom starts at this MSE link.

share|improve this answer

Your Answer

 
discard

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.