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}=?$$
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$C_n^l={n\choose l}$ or $C_n^l={l\choose n}$? – 2012-09-27
-
0@Peter: It has to be the former, non-standard though that is; if it were the latter, every term would be $0$. – 2012-09-27
-
0@BrianM.Scott I would think too. That aside, I usually see $C_{n,k}={n\choose k}$, but I had never seen this one. – 2012-09-27
-
0@Peter: For $\binom{n}k$ I’ve seen $C(n,k),^nC_k,_nC_k,C_k^n$, and probably one or two more, but this is only the second time that I’ve seen the indices in what I consider the wrong order. – 2012-09-27
-
0See 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-bin – 2016-11-16
4 Answers
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.
-
0Why did you submit a nearly-identical answer 6 minutes after your first one? – 2012-10-02
-
0@Rick Decker: After I typed out the first one, I found that I was so careless that I haven't make use of $$ pairs to enclose mathematics to be displayed, so I submit a nearly-identical answer to replaced it. Thanks for your reminding and guiding. – 2012-10-03
-
1@AlfredChern note that by pressing the edit button at the bottom left hand corner you can change your answer without having to post a new one. – 2012-10-03
-
0@E.O.: Thanks for reminding and guiding. I know how to deal with it now. – 2012-10-03
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}\;.$$
$$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} $$
-
0How did you make the last step? – 2012-09-27
-
2@Norbert That is probably listed in Wikipedia in the zillion binomial identities list. =) – 2012-09-27
-
0@Norbert See the [Identities with combinatorial proofs](http://en.wikipedia.org/wiki/Binomial_coefficient#Identities_involving_binomial_coefficients) section – 2012-09-27
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.
-
0Your markup was almost correct. Make use of $$ pairs to enclose mathematics to be displayed. Look at the source of my edits to see how it's done. – 2012-10-02
-
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