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}$$
7838
How can we prove that     $$\sum_{k=0}^{n}\binom{R}{k}\binom{M}{n-k}=\binom{R+M}{n}?$$   (Presumptive) Source: Theoretical Exercise 8, Ch 1, A First Course in Probability, 8th ed by Sheldon Ross.
86894
I am looking for an intuitive explanation for the identity:  $$\binom{n}{h}\binom{n-h}{k} = \binom{n}{k}\binom{n-k}{h}$$  Thanks!
30402
I need hint proving this $$\sum_{k=0}^{n}\binom{2n}{k}k=n2^{2n-1}$$
85347
I'm trying to prove the following  $$ \sum_{r=0}^{n}(r+1) \binom{n}{r} = (n+2)2^{n-1} $$  using the identity $$ \sum_{r=0}^{n} \binom{n}{r} = 2^{n} $$  but I'm not able to. This is what I did so far,   $$ \sum_{r=0}^{n}(r+1) \binom{n}{r} = (1) \binom{n}{0} + (2) \binom{n}{1} + ... + (n+1) \binom{n}{n} $$
75307
How can I show that  $$ \sum_{i=1}^{n-1}i=\binom{n}{2}? $$  This is what I have tried, but I do not know if it is correct:  Proof.  Let $n=2$. Then,  $$ \begin{align} \sum_{i=1}^{1}i&amp;=1\text{, and}\\ \binom{2}{2}&amp;=1. \end{align} $$  Hence, it holds. Assume that this is true for $k$. Then, we show that it is also true for $k+1$:  $$ \begin{align} \sum_{i=1}^{k}i=k+\sum_{i=1}^{k-1}i&amp;=k+\binom{k}{2}\\ &amp;=k+\frac{k!}{2(k-2)!}\\ &amp;=k+\frac{k(k-1)}{2}\\ &amp;=\frac{k(k+1)}{2}\\ &amp;=\frac{(k+1)!}{2!(k-1)!}=\binom{k+1}{2}.\square \end{align} $$  Also, proofs by induction are confusing to write. Is there a standard "skeleton" for them I can use?
69136
Give a combinatorial proof of the following identity:  $$3^n=\sum_{i=0}^{n}\binom{n}{i}2^{n-i}$$  I can't see any counting argument that would yield $3^n$, and the right hand side is also pretty opaque. For some reason I really really suck at doing these proofs - I just started my first combinatorics course.
33587
Prove that $\binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1}  $  Thanks in advance, my professor asked us to this a couple weeks ago, but I was enable to get to the right answer.   Good luck!  Here is what I got up to;  $\frac{(n+1)!}{(n-r)!(r+1)!} = \frac{(n)!}{(r)!(n-r)!} + \frac{(n)!}{(r+1)!(n-r-1)!}    $
91965
I can't figure out an algebraic proof for the following identity, (and I don't know if I can use the binomial theorem for this one): $$\sum_{k=0}^m(-1)^{m-k}{{n \choose {k}}}= {{n-1}\choose m}$$  Thank you, for your help in advance.
94359
I found the following formula in a book without any proof:  $$\sum_{k=0}^{2m}(-1)^k{\binom{2m}{k}}^3=(-1)^m\binom{2m}{m}\binom{3m}{m}.$$  I don't know how to prove this at all. Could you show me how to prove this? Or If you have any helpful information, please teach me. I need your help.  Update : I .
7233
How can I prove the identity:  $$ \sum_{k=0}^n\binom{2n}{2k}^2-\sum_{k=0}^{n-1}\binom{2n}{2k+1}^2=(-1)^n\binom{2n}{n}? $$  Maybe, can we expand $$ f(x)=(1+x)^{2n}? $$  Thank you.
107936
Prove $$\sum_{k=0}^s{\frac{\binom{s}{k}}{\binom{t}{r+k}}} = \frac{t+1}{(t+1-s)\binom{t-s}{r}} $$ for  $r + s \le t$
49298
I'm trying to prove that  \begin{equation} \sum_{k= 0}^{n} k \binom{n}{k} = n \cdot 2^{n - 1} \end{equation}  with the Binomial Theorem.  I know that the B.T. states that  \begin{equation} (x + y)^n =  \sum_{k= 0}^{n} \binom{n}{k} x^{n-k}y^{k}  \end{equation}  The proof that I have tried starts with:  \begin{equation} n \cdot 2^{n-1} =  \end{equation}  Actually I am stucked with this step.
95380
I tried to solve this problem without any success. I really hope that you will know the answer. $f(n,m)$ presents the number of binary strings (empty string included) that include at most n times '1', and at most m times '0'.      Prove: $$f(n,m) = \binom{n+m+2}{n+1}-1$$
33723
Question:  $$\sum_{k=1}^{n}k\binom{2n}{n+k}=\frac n2\binom{2n}{n}$$ is true for every $n\in \mathbb N$? If this is true, then how can we prove this?   When I was playing with numbers, I conjectured this. Though I found that this holds for many $n$s, I haven't found any proof. Can anyone help?
10141
Prove: $\binom{n}{0}F_0+\binom{n}{1}F_1+\binom{n}{2}F_2+\cdots+\binom{n}{n}F_n=F_{2n}$;  I was stuck with this question for a while... Help me please!!! Thanks!!!
115573
Let $n \in \mathbb{Z}^+$, prove the identity $$ \sum_{k=1}^{n-1} \binom {n} {k} \frac{kn^{n-k}}{k+1}=\frac{n(n^{n}-1)}{n+1}$$  First of all  $$ \sum_{k=1}^{n-1} \binom {n} {k} \frac{kn^{n-k}}{k+1}=n^{n}\Bigg(\sum_{k=1}^{n-1} \binom {n} {k} \frac{kn^{-k}}{k+1} \Bigg)$$ $$=n^n\Bigg(\sum_{k=1}^{n-1} \binom {n}{k} \bigg(1-\frac{1}{k+1}\bigg)\bigg(\frac{1}{n^k}\bigg)\Bigg)$$ $$=n^n \sum_{k=1}^{n-1} \binom {n} {k} \frac{1}{n^k}-n^n \sum_{k=1}^{n-1} \binom {n}{k}  \bigg( \frac{1}{k+1}\bigg)\bigg(\frac{1}{n^k} \bigg)$$  We have for the first sum $$(1+\frac{1}{x})^n = \sum_{k=0}^n \binom{n}{k}\frac{1}{x^k}.$$ For the second sum  $$(1+x)^n = \sum_{k=0}^n \binom{n}{k}x^k.$$  Integrating both sides from $0$ to $x$, we see that   $$\frac{(1+x)^{n+1}-1}{n+1} = \sum_{k=0}^n \binom{n}{k}\frac{x^{k+1}}{k+1}.$$  Putting $x=1$ yields $$\frac{2^{n+1}-1}{n+1}=\sum_{k=0}^n \binom{n}{k}\frac{1}{k+1}$$  Here where I have stopped. I could not get them similar for what I have. Would someone help me out !
64981
Is there any way to find:  $$\sum_{i=0}^n {\binom{n}{i}i^k}$$  I know that we can find it for small k by using binomial theorem by differentiating both sides and then multiplying both sides by x and repeating till the form presents itself and then putting x =1, but is there a way for any general power( k here) of i?