Linked Questions
35 questions linked to/from How to prove Vandermonde's Identity: $\sum_{k=0}^{n}\binom{R}{k}\binom{M}{n-k}=\binom{R+M}{n}$?
9
votes
5
answers
2k
views
Vandermonde's Identity: How to find a closed formula for the given summation [duplicate]
I've stumbled upon the following challenging question. Find a closed formula for the following summation $$ S(a,b,n) = \sum_{k=0}^n {a \choose k} {b \choose n-k}$$ for all possible parameters $a,b$.
...
- 5,032
10
votes
4
answers
33k
views
Prove that $\sum_{k=0}^r {m \choose k} {n \choose r-k} = {m+n \choose r}$ [duplicate]
Prove that $$\sum_{k=0}^r {m \choose k} {n \choose r-k} = {m+n \choose r}.$$
This problem is in the chapter about discrete random variables, but I have no idea what to go about substituting.
I can't ...
- 601
8
votes
2
answers
4k
views
Proof of $\sum_{0 \le k \le a} {a \choose k} {b \choose k} = {a+b \choose a}$ [duplicate]
$$\sum_{0 \le k \le a}{a \choose k}{b \choose k} = {a+b \choose a}$$
Is there any way to prove it directly?
Using that $\displaystyle{a \choose k}=\frac{a!}{k!(a-k)!}$?
- 153
5
votes
3
answers
605
views
Proving a binomial coefficient identity [duplicate]
I'm having some trouble with the following proof: $$\sum^k_{a=0} {{n}\choose{a}}{{m}\choose{k-a}} = {{n+m}\choose{k}}$$
I'm trying to prove this to learn a couple of things about the Pascal's ...
- 401
2
votes
2
answers
672
views
Looking for combinatorial identity: $\sum\limits_{j=0}^k{n \choose k-j}{m \choose j}$ [duplicate]
Is there a nicer closed form expression for the following expression? $$\sum_{j=0}^k{n \choose k-j}{m \choose j}$$
- 2,791
0
votes
1
answer
1k
views
Proving binomial identities [duplicate]
Can someone help me prove these two binomial identities using either walks in Pascal's triangle or a committee-selection model?
$(1)$ $\qquad$ $\displaystyle\sum_{k=0}^m {m\choose k}{n\choose r+k}={m+...
- 379
1
vote
4
answers
91
views
Evaluating $\binom{n}{0}\binom{n+1}{0}+\binom{n}{1}\binom{n+1}{1}+\ldots+\binom{n}{n-1}\binom{n+1}{n-1}+\binom{n}{n}\binom{n+1}{n}$ [duplicate]
Here's a question that arose when I was trying to solve a probability problem in my textbook. I'm trying to calculate the sum:
$$\binom{n}{0}\binom{n + 1}{0} + \binom{n}{1}\binom{n + 1}{1} + \binom{n}{...
- 1,415
1
vote
3
answers
132
views
One Binomial Equation $\sum_{i=0}^{z} {n_1 \choose i}{n_2 \choose z-i} = {n_1+n_2 \choose z}$ [duplicate]
I saw one proof using this formula:
$$ \sum_{i=0}^{z} {n_1 \choose i}{n_2 \choose z-i} = {n_1+n_2 \choose z}$$
Can anyone help explain it, thank you!
- 974
2
votes
1
answer
346
views
Prove $\sum_ {k=0} ^n {n \choose k}^2 = {2n \choose n} $? [duplicate]
Give a proof of the following identity using a double-counting argument:
$\sum_ {k=0} ^r {m \choose k} {n \choose r - k} = {{m+n} \choose r} $
Then using this result, derive the following special ...
- 45
-1
votes
2
answers
58
views
looking for combinatorial identity [duplicate]
Does anybody know a nicer expression for the sum $\sum_{i=0}^{k} \binom{n}{i} \binom{n-i}{k-i}$?
- 341
1
vote
1
answer
60
views
$\sum_{x+y =c}{a\choose x}{b\choose y} = {a+b\choose c}$ [duplicate]
When trying to prove a problem I find that I need the above formula to be true, but I have no idea how to prove it. I am trying to prove that a given probability mass function is equivalent to a ...
- 590
2
votes
0
answers
218
views
Prove: ${n\choose 0}{m\choose k}+{n\choose 1}{m\choose {k-1}}+...+{n\choose k}{m\choose 0}={{m+n}\choose k}$ [duplicate]
Prove: ${n\choose 0}{m\choose k}+{n\choose 1}{m\choose {k-1}}+...+{n\choose k}{m\choose 0}={{m+n}\choose k}$
Is it possible to use Pascal's identity or writing binomial coefficients with factorials?
- 3,479
1
vote
3
answers
63
views
Prove identity $\binom{2n}{n} = \sum_{k=0}^{n} \binom{n}{k}\binom{n}{n-k}$ [duplicate]
I found hard (for me at least) example, in fact it just would be nice to prove.
$$\binom{2n}{n} = \sum_{k=0}^{n} \binom{n}{k}\binom{n}{n-k}$$
- 11
0
votes
1
answer
108
views
Proof of sum of binomial distribution [duplicate]
I have two stochastic variable $X\sim B(n,p)$ and $Y\sim B(m,p)$, I need to prove that $Z=X+Y \sim B(n+m,p)$.
Why is $$\sum_{k=0}^{u} \binom{n}{k} \binom{m}{u-k} = \binom{n+m}{u}$$
- 101
0
votes
1
answer
73
views
How to solve $\binom{n+m}{k} = \sum_{i=0}^{k} \binom{m}{i} \binom{n}{k-i} $ [duplicate]
How to prove this?
$n$, $m$ and $k \in \mathbb{N_{0}} $
$$\binom{n+m}{k} = \sum_{i=0}^{k} \binom{m}{i} \binom{n}{k-i}$$
- 382