6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ yes ,corrected the bounds $\endgroup$ Sep 21 '20 at 16:38
4
$\begingroup$

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\ . $$

$\endgroup$
6
$\begingroup$

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$.

$\endgroup$
1
  • 1
    $\begingroup$ thanks @cosmo5 ,got it! $\endgroup$ Sep 21 '20 at 16:54
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ thanks understood ! $\endgroup$ Sep 21 '20 at 16:55
  • $\begingroup$ @Gingerbread: You're welcome. :-) $\endgroup$
    – epi163sqrt
    Sep 21 '20 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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