# summing this binomial series

I found a really interesting question which is as follows: Prove that the value of $$\sum^{7}_{k=0}[({7\choose k}/{14\choose k})*\sum^{14}_{r=k}{r\choose k}{14\choose r}] = 6^7$$

my approach:

I tried to simplify the innermost sigma as well as trying to simplify by using $${n\choose k}=n!/k!(n-k)!$$ however I am can't get hold of this one.

My guess is that the summation simplifies into a standard series but I can't say for sure. Kindly help me out.

• yes ,corrected the bounds Sep 21 '20 at 16:38

First off I don't think your sum is quite right. The bounds on the outer sum should be $$k=0$$ to $$7$$, I believe, otherwise the value isn't $$6^7$$. (Question now corrected)

You are on the right track that rewriting the binomial coefficients in terms of factorials will help. Though the factors inside the sum over $$r$$ won't simplify much by themselves. The solution is to bring the factor $$1/\binom{14}{k}$$ into the second sum. This gives us $$\left.\frac{r!}{k!(r-k)!}\frac{14!}{r!(14-r)!}\right/\frac{14!}{k!(14-k)!} = \frac{(14-k)!}{(r-k)!(14-k)!}\ .$$ This can be recognized as $$\binom{14-k}{r-k}$$. Note that the inner sum is from $$r = k$$ to $$14$$, we can let $$t = r-k$$, and change the bounds to $$0$$ and $$14-k$$. This turns the inner sum into $$\sum_{t=0}^{14-k} \binom{14-k}{t} = 2^{14-k}\ .$$ The outer sum can now be evaluated, $$\sum_{k=0}^7 \binom{7}{k} 2^{14-k} = 2^7\sum_{k=0}^{7}\binom{7}{k} 2^{7-k} = 2^7(1+2)^7 = 6^7\ .$$

Using $${14 \choose r}{r \choose k} = {14 \choose k}{14-k \choose r-k}$$ given reduces to

\begin{align*} & \sum_{k=0}^7 {7 \choose k} \bigg\{\sum^{14}_{r=k} {14-k \choose r-k} \bigg\} \\ & = \sum_{k=0}^7 {7 \choose k} \{2^{14-k}\} \\ & = 2^{7} \times \sum_{k=0}^7 {7 \choose k} 2^{7-k} \\ & = 2^{7}\times(2+1)^{7} \\ & = 6^7 \end{align*}

Edit : As pointed by @ElliotYu, outer bound should be from $$0$$ to $$7$$.

• thanks @cosmo5 ,got it! Sep 21 '20 at 16:54

Setting $$n=7$$ we obtain \begin{align*} \color{blue}{\sum_{k=0}^n}&\color{blue}{\binom{n}{k}\binom{2n}{k}^{-1}\sum_{r=k}^{2n}\binom{r}{k}\binom{2n}{r}}\\ &=\sum_{k=0}^n\binom{n}{k}\frac{k!(2n-k)!}{(2n)!}\sum_{r=k}^{2n}\frac{r!}{k!(r-k)!}\,\frac{(2n)!}{r!(2n-r)!}\\ &=\sum_{k=0}^n\binom{n}{k}\sum_{r=k}^{2n}\binom{2n-k}{r-k}\\ &=\sum_{k=0}^n\binom{n }{k}\sum_{r=0}^{2n-k}\binom{2n-k}{r}\\ &=\sum_{k=0}^n\binom{n}{k}2^{2n-k}\\ &=2^{2n}\sum_{k=0}^n\binom{n}{k}\frac{1}{2^k}\\ &=2^{2n}\left(1+\frac{1}{2}\right)^n\\ &\,\,\color{blue}{=6^n} \end{align*} and the claim follows.

• thanks understood ! Sep 21 '20 at 16:55
• @Gingerbread: You're welcome. :-) Sep 21 '20 at 16:59