$$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} = 4^n$$  Is there a combinatorial proof of above identity, without any arithmetic transformation?  Thanks...
12381
It's not difficult to show that  $$(1-z^2)^{-1/2}=\sum_{n=0}^\infty \binom{2n}{n}2^{-2n}z^{2n}$$  On the other hand, we have $(1-z^2)^{-1}=\sum z^{2n}$.  Squaring the first power series and comparing terms gives us  $$\sum_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}2^{-2n}=1$$  that is,  $$\sum_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}=2^{2n}$$  My question: is there a more direct, combinatorial proof of this identity?  I've been racking my brains trying to come up with one but I'm not having much success.
18020
How does one show that $$\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}=2^{n}$$ for each nonnegative integer $n$?  I tried using the  but I guess I am applying it incorrectly. With the snake oil technique we have $$F(x)= \sum_{n=0}^{\infty}\left\{\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}\right\}x^{n}.$$ I think I have to interchage the summation and do something. But I am not quite comfortable in interchanging the summation. Like after interchaging the summation will $$F(x)=\sum_{k=0}^{n}\sum_{n=0}^{\infty}\binom{n+k}{k}\frac{1}{2^k}x^{n}?$$ Even if I continue with this I am unable to get the correct answer.  How does one prove this using the Snake oil technique?  A combinatorial proof is also welcome, as are other kinds of proofs.
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.
123943
$$n!=\sum_{k=0}^n \binom{n}{k}(n-k+1)^n(-1)^k$$  Could anyone give the proof of the above equation? Thanks in advance!
68698
Do you have any idea to prove the following identity via a combinatorial (or algebraic) method?  $\sum_{n=r}^{n=\infty} {n \choose r}^{-1} = \frac{r}{r-1}$  This is  of the book Chen C.C., Koh K.M. Principles and techniques in combinatorics. The book does not give a solution, although it mentions: "see H. W. Gould, Combinatorial Identities, Morgantown, W.V. (1972), 18-19".  many thanks in advance, Shahram
10614
Show that $$\sum_{k=0}^n(-1)^k\binom nk=0$$ So for odd $n$ we have an even number of terms. So $\binom nk=\binom n{n-k}$ which have opposite signs. Thus the sum is 0.  For even $n$ we have that $$\sum_{k=0}^n(-1)^k\binom nk= \binom n0+\sum_{k=1}^{n-1}(-1)^k\binom nk+\binom nn$$ Now $$\sum_{k=1}^{n-1}(-1)^k\binom nk= \sum_{k=1}^{n-1}(-1)^k\left[\binom{n-1}k+\binom{n-1}{k-1}\right]$$ What would that sum be in the square brackets?
34666
Prove that $\sum_{k=0}^{m}\dfrac{\binom{m}{k}}{\binom{n}{k}}=\dfrac{n+1}{n+1-m}$.  We know, n > m. From the right side. we have $\dfrac{n+1}{n+1-m}=\dfrac{1}{1-\dfrac{m}{n+1}}$. since n > m. $0&lt;\dfrac{m}{n+1}&lt;1$. Then $\dfrac{1}{1-\dfrac{m}{n+1}}=1+\dfrac{m}{n+1}+(\dfrac{m}{n+1})^2+...$ I don't know what to do next? Did I choose the right path?
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?
87923
Prove that $$\sum_{k=0}^n {n \choose k}^{\!2} = {2n \choose n}.$$  The exercise provides the following hint: $\,\,\displaystyle{n \choose k}={n\choose n-k}$.  Any help?
104982
Prove the identity  $$\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}=0$$  Use a combinatorial interpretation of the positive and negative terms.   Edit: I have already proven it using the binomial theorem, more specifically with $(1-1)^n$. I'm having difficulty understanding what is meant by a combinatorial interpretation of the positive and negative terms.    I'm having trouble understanding exactly what is necessary for a combinatorial interpretation. Looking at small cases, I see that the symmetry of the expansion allows us to cancel out lots of terms.   Is this what is meant by a combinatorial interpretation? Is there any resources that introduce the idea of what constitute a combinatorial interpretation?  I feel like the professor threw us off in the deep end and I'm trying to keep my head above water with the few problems I have to work with and that I understand.
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.
8115
Prove the combinatorial identity $${n \choose k} = {n-2\choose k-2} + 2{n-2\choose k-1} + {n-2\choose k} .$$   I understand the left side, which is obvious, but I'm struggling to get anywhere on the RHS. I also would appreciate suggestions on how to approach these kind of problems. I was told to use committees and split them up, but even then it's not so intuitive to me.  I've tried substituting small numbers to see where I can go.  Thank you in advance for your time.
84238
I am looking for the combinatorial argument for the identity:  \begin{equation} k\binom{n}{k} = n\binom{n-1}{k-1} \end{equation}  This is easy to show algebraically as:  \begin{equation} \binom{n}{k} = \dfrac{n(n-1)(n-2)(n-k+1)}{k(k-1)!} \end{equation}   What is the combinatorial argument? What are some general ideas to get started?   Here is a clarification of 2. From what I have seen so far, proving (combinatorially) an identity with an addition sign usually implies that we need to partition a set (this makes sense because of the addition rule and provides a nice visual). On the contrary, the previous observation leads me to believe that multiplication in identities can be resolved with the multiplication principle, but what is the "visual/interpretation" for this? Could someone provide such an interpretation for the example identity given above?
77151
In a proof I've come across the following identity:     $$ \sum_{l=0}^{n-j} \binom{M-1+l}{l} \binom{n-M-l}{n-j-l} = \binom{n}{j} $$   I see that it's right, when plugging in numbers, but I don't see the algebraic or combinatorial proof behind it. Can anyone help me with that?
71474
Prove $$\sum_{k = 0}^{n}(-1)^{n - k} \binom{n}{k} \cdot k^n = n! \qquad\text{and}\qquad \sum_{k = 0}^{n}(-1)^{n - k} \binom{n}{k} \cdot k^m = 0,$$ where $m \in \{0, 1, 2, \cdots, n - 1\}$.  To be honest, I tried to use some combinatorial ideas but was not able to see interconnections. Also, I had an idea to prove it using induction but failed to do that either. Help will be much appreciated! I just got stuck and don't see any continuation of solution for this problem
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.
9
I am stuck with the identity  $$ F_{2n} = \sum_{k=1}^n \binom{n}{k} F_k, $$  which happens to be formula . I am using induction, but so far without too much result.  $$ \sum_{k=1}^{n+1} \binom{n+1}{k} F_k = \\ F_{n+1} + \sum_{k=1}^n \binom{n+1}{k} F_k = \\ F_{n+1} + \sum_{k=1}^n \binom{n}{k} F_k + \sum_{k=1}^n \binom{n}{k-1}F_k =\\ F_{n+1} + F_{2n} + \sum_{k=1}^n \binom{n}{k-1}F_k, $$   I am stuck with the sum $ \sum_{k=1}^n \binom{n}{k-1}F_k$, because, on the other hand   $$ F_{n+1}+ \sum_{k=1}^n \binom{n}{k-1}F_k = F_{2n+1} $$  Which would conclude the proof. What am I missing?