1
$\begingroup$

Prove the identity $\sum_{k=0}^{n}\sum_{r=0}^{k} \binom{k}{r} \binom{n}{k} = 3^n$. I believe I need to use the binomial theorem here, but I don't know how to deal with the double summations.

$\endgroup$
2
$\begingroup$

We will use the identity $$ \binom{n}{k}\binom{k}{r}=\binom{n}{r}\binom{n-r}{k-r}\quad (n\geq k\geq r\geq 0). $$ Interchange the order of summation and use the identity above to get that $$ \sum_{k=0}^{n}\sum_{r=0}^{k} \binom{k}{r} \binom{n}{k} =\sum_{r=0}^{n}\binom{n}{r}\sum_{k=r}^{n}\binom{n-r}{k-r}=\sum_{r=0}^n\binom{n}{r}2^{n-r}=(1+2)^n=3^n $$ where we used the fact that $$ \sum_{k=r}^{n}\binom{n-r}{k-r}=\sum_{u=0}^{n-r}\binom{n-r}{u}=2^{n-r}. $$

$\endgroup$
  • $\begingroup$ Do you know a combinatorial proof of the statement? $\endgroup$ – mathpadawan Dec 8 '18 at 20:33
  • 1
    $\begingroup$ @mathnoob I think I have a combinatorial argument, see my answer below. $\endgroup$ – Ned Dec 8 '18 at 21:18
  • $\begingroup$ That's cool! Thanks! $\endgroup$ – mathpadawan Dec 8 '18 at 21:22
2
$\begingroup$

Let $|X|=n$, so $3^n$ is the number of functions from $X$ to {$1,2,3$}.

Each such function corresponds uniquely to a pair of subsets $(A,B)$ with $A$ a subset of $B$ and $B$ a subset of $X$ by taking $B$ = {$x$ | $f(x)=2$ or $f(x)=3$} and $A$ = {$x$ | $f(x)=2$}.

The number of such pairs of nested subsets of $X$ is the double sum on the right hand side of the formula (where $k$ = $|B|$ and $r$ = $|A|$).

$\endgroup$
1
$\begingroup$

You know that $\displaystyle(1+x)^n=\sum_{k=0}^n\binom nkx^k$

$\displaystyle\sum_{k=0}^{n}\sum_{r=0}^{k} \binom{k}{r} \binom{n}{k} =\sum_{k=0}^{n}\binom{n}{k}\sum_{r=0}^{k} \binom{k}{r}=\sum_{k=0}^{n}\binom{n}{k}\sum_{r=0}^{k} \binom{k}{r}1^r$

Since $\displaystyle\sum_{r=0}^{k} \binom{k}{r}1^r=(1+1)^k=2^k$, we have

$\displaystyle\implies\sum_{k=0}^{n} \binom nk2^k=(1+2)^n=3^n$

$\endgroup$
0
$\begingroup$

A convenient aspect is the index of the inner sum affects only one binomial coefficient. Setting parenthesis we might observe

\begin{align*} \color{blue}{\sum_{k=0}^{n}\sum_{r=0}^{k} \binom{k}{r}\binom{n}{k}} &=\sum_{k=0}^{n}\left(\sum_{r=0}^{k} \binom{k}{r} \right)\binom{n}{k}\\ &=\sum_{k=0}^{n}2^k \binom{n}{k}\\ &\,\,\color{blue}{=3^n} \end{align*}

$\endgroup$

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.