0
$\begingroup$

Calculating this combination: $C_{n}^{l}\cdot C_{l}^{l}+C_{n}^{l+1}\cdot C_{l+1}^{l}+\ldots+C_{n}^{n}\cdot C_{n}^{l}=?$

  • 0
    See also: http://math.stackexchange.com/questions/380555/prove-that-for-n-m-geq0-that-sum-limits-k-mnk-choosemn-choose http://math.stackexchange.com/questions/1333148/prove-by-induction-sum-limits-k-m-nn-choose-kk-choose-m-n-choose-m http://math.stackexchange.com/questions/1640706/combinatorial-argument-for-sum-limits-k-in-binomnk-binomki-bin2016-11-16

4 Answers 4

0

I think it's necessary to make a more detailed explanation, just as following:

$\begin{align*} C_{n}^{l}C_{l}^{l}+C_{n}^{l+1}C_{l+1}^{l}+\dots+C_{n}^{n}C_{n}^{l} =\sum_{k=l}^{n}C_{n}^{k}C_{k}^{l} =\sum_{k=l}^{n}C_{n}^{l}C_{n-l}^{k-l} =2^{n-l}C_{n}^{l} \end{align*}$

The second step follows from that for arbitrary $k$,

$\begin{align*} C_{n}^{k}C_{k}^{l}&=\frac{n!}{k!(n-k)!}\frac{k!}{l!(k-l)!}\\ &=\frac{n!}{l!(n-k)!(k-l)!}\\ &=\frac{n!}{l!(n-l)!}\frac{(n-l)!}{(n-k)!(k-l)!}\\ &=C_{n}^{l}C_{n-l}^{k-l}\\ \end{align*}$

The last step follows from that

$\begin{align*} \sum_{k=l}^{n}C_{n}^{l}C_{n-l}^{k-l}&=C_{n}^{l}\sum_{k=l}^{n}C_{n-l}^{k-l} =C_{n}^{l}\sum_{i=0}^{n-l}C_{n-l}^{i}\\ &=C_{n}^{l}2^{n-l}=2^{n-l}C_{n}^{l}\\ \end{align*}$

that's all, thanks for reading.

  • 0
    @E.O.: Than$k$s for reminding and guiding. I know how to deal with it now.2012-10-03
2

You can resolve it purely computationally:

$\begin{align*} \sum_{k=\ell}^n\binom{n}k\binom{k}\ell&=\sum_{k=\ell}^n\frac{n!k!}{k!(n-k)!\ell!(k-\ell)!}\\ &=\sum_{k=\ell}^n\frac{n!}{(n-k)!(k-\ell)!\ell!}\\ &=\binom{n}\ell\sum_{k=\ell}^n\frac{(n-\ell)!}{(n-k)!(k-\ell)}!\\ &=\binom{n}\ell\sum_{k=0}^{n-\ell}\binom{n-\ell}k\\ &=\binom{n}\ell2^{n-\ell}\;. \end{align*}$

You can also resolve it combinatorially. Imagine that you have $n$ white balls. You’re going to paint $\ell$ of them red, and then you’re going to choose some (or perhaps none) of the remaining white balls and paint them blue. You can do this by first choosing $k$ balls, for some $k\ge\ell$, that are going to be painted either blue or red, and then choosing $\ell$ of these $k$ balls to be painted red; the other $k-\ell$ of the balls will be painted blue. For a particular value of $k$ the number of ways to do this is $\binom{n}k\binom{k}\ell$, so

$\sum_{k=\ell}^n\binom{n}k\binom{k}\ell$

is the total number of ways to carry out the task.

On the other hand, you could simply choose $\ell$ of the $n$ balls and paint them red, and then go through the other $n-\ell$ balls one at a time, either painting the ball blue or leaving it white. There are $\binom{n}\ell2^{n-\ell}$ ways to do this. Thus,

$\sum_{k=\ell}^n\binom{n}k\binom{k}\ell=\binom{n}\ell2^{n-\ell}\;.$

0

$C_{n}^{l}.C_{l}^{l}+C_{n}^{l+1}.C_{l+1}^{l}+\ldots+C_{n}^{n}.C_{n}^{l} =\sum_{k=l}^{n}C_{n}^{k}.C_{k}^{l} =\sum_{k=l}^{n}C_{n}^{l}.C_{n-l}^{k-l} =2^{n-l}C_{n}^{l} $

  • 0
    @Norbert See the [Identities with combinatorial proofs](http://en.wikipedia.org/wiki/Binomial_coefficient#Identities_involving_binomial_coefficients) section2012-09-27
0

I think it's necessary to make a more detailed explanation, just as following: $ C_{n}^{l}C_{l}^{l}+C_{n}^{l+1}C_{l+1}^{l}+\dots+C_{n}^{n}C_{n}^{l} =\sum_{k=l}^{n}C_{n}^{k}C_{k}^{l} =\sum_{k=l}^{n}C_{n}^{l}C_{n-l}^{k-l} =2^{n-l}C_{n}^{l} $ The second step follows from that for arbitrary $k$, $ \begin{align} C_{n}^{k}C_{k}^{l} &=\frac{n!}{k!(n-k)!}\frac{k!}{l!(k-l)!}\\ &=\frac{n!}{l!.(n-k)!(k-l)!}\\ &=\frac{n!}{l!.(n-l)!}\frac{(n-l)!}{(n-k)!(k-l)!}\\ &=C_{n}^{l}.C_{n-l}^{k-l} \end{align} $ The last step follows from that $ \begin{align} \sum_{k=l}^{n}C_{n}^{l}C_{n-l}^{k-l} &=C_{n}^{l}\sum_{k=l}^{n}C_{n-l}^{k-l}\text{ (as $k$ replaced by $i+l$)}\\ &=C_{n}^{l}\sum_{i=0}^{n-l}C_{n-l}^{i}\\ &=C_{n}^{l}2^{n-l} \end{align} $ that's all, thanks for reading.

  • 0
    @Rick Decker: Thank you very much! I had look at the source of your edits, it's perfect and I have learned from it. I am not very familiar with the rules and thanks for guide.2012-10-02