Prove that $\sum_{k=0}^{n} k \binom{n}{k} \binom{m}{k}=n\binom{m+n-1}{n}$  I have tried induction by $n$ and by $m$ with Pascal's Identity, but that always seems to drop $k$ to $k-1$ and I am not sure what to do with that afterwards. I have also tried rewriting the $\binom{m+n-1}{n}$ part to $\sum_{i=o}^{n} \binom{m-2+i}{i}$, but that did not work as well. I know that $\sum_{k=0}^{n} k \binom{n}{k}$ can be obtained from first derivative of $(1+x)^n$ multiplied by $x$ and setting $x=1$ but I don't see how to multiply it then by $\binom{m}{k}$, if this approach is even usable here. I am not really sure what to do with this problem.
122214
I believe the following is an identity (I've tested with a few random $m$ and $n$ values, could be wrong though):  $$\sum_{k= 0}^{\infty}{m \choose k}{n \choose k}k=n\binom{m+n-1}{m-1}$$ but I'm not sure how to prove it.   Initially I thought of considering the right side combinatorially: pick $m-1$ things from a bucket of $m+n-1$ things and repeat this $n$ times. But how do I think of the left side combinatorially, since there is an infinite sum? Or maybe this is the incorrect approach?
106937
I can't figure out an algebraic proof for the following identity:  $$\sum_{i=0}^k{{n \choose i}{m \choose {k-i}}}= {{m+n}\choose k}$$  Combinatorical solution:  We can see that as choosing some from $n$ and the rest of $k$ from $m$, thus $k$ in total.  Or we could just choose $k$ from the union.
5363
Give an algebraic and a combinatorial proof for the following identity:       $$ \sum _{k=0} ^m \binom nk \binom{n-k}{m-k} = 2^m \binom {n}{m}.$$      For the combinatorial argument, use the analogy of $n$ party guests, where $m$ of them describe themselves as either vegetarian or vegan (but not both).   After proving the identity using algebraic transformations, I'm unable to find a combinatorial argument for it. For the right hand side, if we multiply $\binom nm $ by $2^n$, we get the Pascal-triangle but with each row multiplied by $2^n$, but here we're multiplying by $2^m$. What does this mean? How does the analogy with the party guests work? Any help would be much appreciated.
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.
86807
Prove the identity $\sum_{k=0}^{n}\sum_{r=0}^{k} \binom{k}{r} \binom{n}{k} = 3^n$. I believe I need to use the binomial theorem here, but I don't know how to deal with the double summations.
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?
12493
Assume $f$ and $g$ are differentiable at $x$. Prove that $(fg)^{(n)} = \sum_{k=0}^n \binom{n}{k}f^{(k)}(x)g^{(n-k)}(x)$   I am assuming here $fg = f(x) g(x)$. Then we can prove this via induction. If $n = 0$ we have $1 = 1$ which is true. Now assume it is true for some $m$ we need to show it is possible for $m+1$. We have $(fg)^m = \sum_{k=0}^m f^{(k)}(x)g^{m-k}(x)$. How do we show that?
53069
I need to proof this following equality :  $$\binom{m+n}{m}=\sum_{i=0}^m \left(\binom{m}{i}\binom{n}{i}\right)$$  This is what I did combinatoric proof:  Left : subset with $m$ members from $m+n$  Right : $\binom{m}{i} \rightarrow$ The number of subsets in set $m$ could also be written as $2^m$ AND $\binom{n}{i} \rightarrow$ the number of subsets with $m$ members from set $n$  In case $ n \leq m \implies \binom{n}{i}=2^n$  So this is what I came up with I still can't see why those expression are equal.  Any ideas? Thanks.
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?
28191
I'm sure there's an identity or some known "trick" to solve this but I couldn't find it (Looked in Wikipedia, Wolfram and here):  $$ \sum_{k=0}^n (-1)^k{n \choose k} =0 $$  I want to know how this can be proven. I tried induction but I'm not sure what to do with ${{n+1}\choose k}$.  Thanks!
8310
After reading , the most popular answer use the identity $$\sum_{t=0}^n \binom{t}{k} = \binom{n+1}{k+1}.$$  What's the name of this identity? Is it the identity of the  modified.  How can we prove it? I tried by induction, but without success. Can we also prove it algebraically?  Thanks for your help.    EDIT 01 : This identity is known as the  because, on Pascal's triangle, when the addends represented in the summation and the sum itself are highlighted, a hockey-stick shape is revealed.
286
How do I prove the following identity:  $$\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{2n - 2k}{n - 1} = 0$$  I am trying to use inclusion-exclusion, and this will boil down to a sum like inclusion-exclusion, and the $\binom{2n-2k}{n-1}$ term wouldn't matter (it will be equivalent to set sizes). Is this a correct way to go?
123923
I'm trying to prove binomial theorem by induction, but I'm a little stuck. I would look at online resources as this problem has been done many times, but the version I am trying to prove the binomial theorem in a different form.  $$(1 + x)^n = \sum_{k = 0}^{n} \binom{n}{k} x^k$$  I'm mostly confused as to how I can make the left side be equivalent to a summation, any help is appreciated. Try to hint me along!
39049
Given the identity  $$\sum_{i=0}^{n} \binom{k-1+i}{k-1} = \binom{n+k}{k}$$  Need to give a combinatorial proof   a) in terms of subsets  b) by interpreting the parts in terms of compositions of integers  I should not use induction or any other ways...  Please help.
82684
I've worked out a proof, but I was wondering about alternate, possibly more elegant ways to prove the statement. This is my (hopefully correct) proof:  Starting from the identity $2^m = \sum_{k=0}^m \binom{m}{k}$ (easily derived from the binomial theorem), with $m = 2n$:  $2^{2n} = 4^n = \binom{2n}{0} + \binom{2n}{1} + \cdots + \binom{2n}{2n-1} + \binom{2n}{2n}$  Applying the property $\binom{m}{k} = \binom{m}{m-k}$ to the second half of the list of summands in RHS above:  $4^n = \binom{2n}{0} + \binom{2n}{1} + \cdots + \binom{2n}{n-1} + \binom{2n}{n} + \underbrace{\binom{2n}{n-1} +\cdots \binom{2n}{1} + \binom{2n}{0}}_{\binom{m}{k} = \binom{m}{m-k} \text{ has been applied}}$  Rearranging the above sum by alternately taking terms from the front and end of the summand list in RHS above (and introducing the term $\binom{2n}{-1} = 0$ at the beginning just to make explicit the pattern being developed):  $4^n = (\binom{2n}{-1} + \binom{2n}{0}) + (\binom{2n}{0} + \binom{2n}{1}) + \cdots + (\binom{2n}{n-1} + \binom{2n}{n})$  Finally, using the property $\binom{m}{k} + \binom{m}{k-1} = \binom{m+1}{k}$ on the paired summands, we get the desired result:  $4^n = \binom{2n+1}{0} + \binom{2n+1}{1} + \cdots + \binom{2n+1}{n}$
65822
Please feel free to close this is necessary as I didn't see exactly this question (some variations that I tried but didn't seem to apply. Prove: $$\sum_{k=0}^{n}{\binom{n}{k}^2}=\binom{2n}{n}$$ I figured trying to muscle through it by expanding and then multiplying each term by variants of 1 such as $\frac{n^2}{n^2}$ and $\frac{n^2(n-1)^2}{n^2(n-1)^2}$ to get common denominators, but that was NOT the way it seemed as it got ugly pretty quickly.  Then I tried thinking up formulas of the binomial theorem that I could differentiate like other sums of binomial coefficient problems and i couldn't think of one.  Any help here would be great.
119758
Is it true that $\sum_kk\binom{n}{k}^2=n\binom{2n-1}{n-1}$? (I proved it using generating functions). Could you help me to prove it combinatorially? please