2
$\begingroup$

Prove by induction that $\displaystyle\sum\limits_{k=m}^{n}{n\choose k}{k\choose m}={n\choose m}2^{n-m}$.

I am not sure how to perform the induction and what the base case is. But by trying to induct on $n$, we note that when $n=m$ the equality is $$\binom{m}{m}\binom{m}{m}=\binom{m}{m}2^{m-m}$$ which is true because both sides equal $1$. For the inductive step, suppose $\sum\limits_{k=m}^{n}{n\choose k}{k\choose m}={n\choose m}2^{n-m}$ is true. Then we need to show that $$\sum\limits_{k=m}^{n+1}{n+1\choose k}{k\choose m}=\binom{n+1}{m}2^{n+1-m}.$$ I am stuck here. Or is it better to induct on $m$?

$\endgroup$
5
$\begingroup$

you can get by without induction if you observe: $$ \binom{n}{k} \binom{k}{m} = \binom{n}{m} \binom{n-m}{k-m} $$ then $$ \sum_{k=m}^n \binom{n}{k} \binom{k}{m} = \binom{n}{m}\sum_{j=0}^{n-m}\binom{n-m}{j} = \binom{n}{m}2^{n-m} $$

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

We may write the required equality as $$\sum_{k=0}^n\,\binom{n}{k}\,\binom{k}{m}=\binom{n}{m}\,2^{n-m}$$ for all integers $n,m\geq 0$, using the convention that $\displaystyle\binom{p}{q}=0$ for integers $p,q\geq 0$ such that $p<q$. We shall prove by induction on $m$ the generalized statement: $$\sum_{k=0}^n\,\binom{n}{k}\,\binom{k}{m}\,x^{k-m}=\binom{n}{m}\,(1+x)^{n-m}\,,$$ where $x:=1$ leads to the required equality. The basis step is $m=0$, where we have the well known Binomial Theorem $$\sum_{k=0}^n\,\binom{n}{k}\,\binom{k}{0}\,x^{k-0}=\sum_{k=0}^n\,\binom{n}{k}\,x^k=(1+x)^n=\binom{n}{0}\,(1+x)^{n-0}\,.$$

Now, suppose the identity is true when $m=s$ for some integer $s\geq 0$ (and for all integer $n\geq 0$). Therefore, we have $$\sum_{k=0}^{n}\,\binom{n}{k}\,\binom{k}{s}\,x^{k-s}=\binom{n}{s}\,(1+x)^{n-s}\,.$$ for all integer $n\geq 0$. Taking the derivative with respect to $x$, we obtain $$\sum_{k=0}^{n}\,\binom{n}{k}\,\binom{k}{s}\,(k-s)\,x^{k-s-1}=\binom{n}{s}\,(n-s)\,(1+x)^{n-s-1}\,.$$ Dividing both sides by $s+1$ to get $$\sum_{k=0}^n\,\binom{n}{k}\,\binom{k}{s}\,\frac{k-s}{s+1}\,x^{k-(s+1)}=\binom{n}{s}\,\frac{n-s}{s+1}\,(1+x)^{n-(s+1)}\,.$$ Since $\displaystyle\binom{p}{s}\,\frac{p-s}{s+1}=\binom{p}{s+1}$ for every integer $p\geq 0$, we get the desired equality $$\sum_{k=0}^n\,\binom{n}{k}\,\binom{k}{s+1}\,x^{k-(s+1)}=\binom{n}{s+1}\,(1+x)^{n-(s+1)}\,,$$ establishing that the required equality holds for $m=s+1$. By induction, we are done.


Alternatively, consider a task of choosing a committee from $n$ people, where $m$ committee members are given the chief status. If the committee has $k$ members, then there are $\displaystyle\binom{n}{k}$ ways to choose the committee and $\displaystyle\binom{k}{m}$ ways to choose the chiefs. Hence, the number of ways to perform this task is precisely $\displaystyle\sum\limits_{k=m}^n\,\binom{n}{k}\,\binom{k}{m}$. On the other hand, we may chose $m$ chiefs first, whereby there are are $\displaystyle\binom{n}{m}$ ways to do so. The non-chief committee members are then selected from $n-m$ remaining people, which can be done in $2^{n-m}$ ways. Hence, we can perform this task in $\displaystyle\binom{n}{m}\,2^{n-m}$ ways. The proof is now complete.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ +1 for a nice combinatorial solution! when such a representation can be found, it is the most aesthetically satisfying demonstration $\endgroup$ – David Holden Jun 21 '15 at 0:38

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.