$n(n+1)2^{n-2} = \sum_{i=1}^ni^2\binom{n}{i}$  I would like to prove above identity combinatorially.  $n(n+1)$ of LHS is doubled amount of summing up from $1$ to $n$ and remaining $2^{n-1}$ denotes that there's some $n -1$ consecutive choice of something being exist or not.  How could I relate this two factors into potential those of RHS ?  Or will there any other option that I can refer to?  Any advice would be appreciate.
22727
Find a combinatorial argument for the following binomial identity:   $$n(n+1)2^{n-2} = \sum_{k=1}^{n}k^2\binom{n}{k} .$$   Algebraic proofs can be found at  , and a related identity at  .
111727
Give  a  proof  of  the  following  identity  by  counting  two  sets  of  partitions  in  two  different ways.  \begin{equation*}  \prod_{i\geq 0}(1+x^{2i+1})=1 + \sum_{n\geq 1}x^{n^2}\prod_{j=1}^n\frac{1}{1-x^{2j}}  \end{equation*} To prove this inductively, i only successfully complete the base cases, however the counting set for the left side i concluded that would be the number of partitions of n with distinct odd parts and for RS the product part would be the number of partitions of n with even parts, how would the summation of $x^{n^2}$ come into play with counting set. How would i initiate my proof?
104668
I need to prove this $$\sum_{k=0}^n \binom{n+k}{k}=\binom{2n+1}{n}$$ Using induction and basically only the Pascal's identity and the symmetry property for binomial coefficients. Now, I noticed that $\sum_{k=0}^n \binom{r+k}{k}=\binom{r+n+1}{n}$ has a relatively simple proof by induction and it basically holds for any $r$. Could I apply that property for $r=n$ and call it a day? I also tried to solve the problem by using a similar argument, the induction step however states that $$\sum_{k=0}^{n+1} \binom{n+1+k}{k}=\sum_{k=0}^{n} \binom{n+1+k}{k}+\binom{2n+2}{n+1}$$ then $$\sum_{k=0}^{n+1} \binom{n+1+k}{k}=\sum_{k=0}^{n} \binom{n+k}{k}+\sum_{k=0}^{n} \binom{n+k}{k-1}+\binom{2n+2}{n+1}$$ Using the induction hypothesis $$\sum_{k=0}^{n+1} \binom{n+1+k}{k}= \binom{2n+1}{n}+\sum_{k=0}^{n} \binom{n+k}{k-1}+\binom{2n+2}{n+1}$$ And that's where I got stuck. Is this a dead end?
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.
27227
Consider the identity $$\sum_{k=0}^n (-1)^kk!{n \brace k} = (-1)^n$$ where ${n\brace k}$ is a Stirling number of the second kind. This is slightly reminiscent of the binomial identity $$\sum_{k=0}^n(-1)^k\binom{n}{k} = 0$$ which essentially states that the number of even subsets of a set is equal to the number of odd subsets.   Now there is an easy proof of the binomial identity using symmetric differences to biject between even and odd subsets. I am wondering if there is an analogous combinatorial interpretation for the Stirling numbers. The term $k!{n\brace k}$ counts the number of set partitions of an $n$ element set into $k$ ordered parts. Perhaps there is something relating odd ordered partitions with even ordered partitions?  As an added note, there is a similar identity $$\sum_{k=1}^n(-1)^k(k-1)!{n\brace k}=0$$ A combinatorial interpretation of this one would also be appreciated.
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.
26767
a) Give a combinatorial proof that for every $n \geq r \geq 1$ that:  $$\sum_{i = 0}^{n} \binom{i}{r - 1} = \binom{n + 1}{r}$$  And use (a) to concoct a formula for $1^2 + 2^2 + ... + n^2$
44659
I would like to prove inductively that $${2n\choose n}=\sum_{i=0}^n{n\choose i}^2.$$  I know a couple of non-inductive proofs, but I can't do it this way. The inductive step eludes me. I tried naively things like $${2n+2\choose n+1}={2n+2\over n+1}{2n+1\choose n}=2\cdot {2n+1\over n+1}{2n\choose n},$$  But I don't think it can lead me anywhere. I would like the proof to be as simple as possible.
2269
Give a combinatorial proof for this identity for non-negative integer $k$ and $n$ such that $0 \leq k &lt; n$   $$\sum_{j=0}^{k} \binom{n}{j} = \sum_{j=0}^k \binom{n-1-j}{k-j}2^j$$   My attempt: I tried to reduce this identity. Since $k,n$ are nonnegative integer and $k&lt;n$ then I can change the upper limit into  $$\sum_{j=0}^{n-1} \binom{n}{j} =2^n-1 \quad \text{and} \quad \sum_{j=0}^{n-1} \binom{n-1-j}{n-1-j}2^j = \sum_{j=0}^{n-1} 2^j ~.$$  So, I just need to show $$\sum_{j=0}^{n-1} 2^j =2^n-1 $$ using combinatorial proof. Am I right? I really need helps
24152
Let $n$ be a nonnegative integer, and $k$ a positive integer. Could someone explain to me why the identity $$ \sum_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k} $$ holds?
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.
18697
Wikipedia has a proof of the identity $$ H_{n} =\sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} \frac{1}{k}$$    Curiously, there is also the identity  $$ \frac{1}{n} = \sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} H_{k} $$  Can the second identity be derived from the first one?
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.
83623
I'm trying to prove the following equation above. So far I have: \begin{align} 2^{2n} &amp;= (1+1)^{2n}\\ &amp;= \sum_{k=0}^{2n}\binom{2n}{k}1^k1^{n-k} = \sum_{k=0}^{2n}\binom{2n}{k} &amp; \text{(By the Binomial Theorem)} \end{align}  I know I have to use the following identity somehow: $$\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}$$  How do I split my summation to get what I'm looking for? Thanks!  EDIT: HERE IS MY SOLUTION \begin{align*} 2^{2n} &amp;= (1+1)^{2n}\\ &amp;= \sum_{k=0}^{2n}\binom{2n}{k}1^k1^{2n-k} &amp; \text{(By the Binomial Theorem)}\\ &amp;= \sum_{k=0}^{n}\binom{2n}{k} + \sum_{k=n+1}^{2n}\binom{2n}{k}\\ &amp;= \sum_{k=0}^{n}\binom{2n}{k} + \sum_{k=n+1}^{2n}\binom{2n}{2n-k} &amp; \text{(Binomial Symmetry)}\\ &amp;= \sum_{k=0}^{n}\binom{2n}{k} + \sum_{k=0}^{n-1}\binom{2n}{k}\\ &amp;= \sum_{k=0}^{n}\binom{2n}{k} + \sum_{k=1}^{n}\binom{2n}{k-1}\\ &amp;= \binom{2n}{0} + \sum_{k=1}^{n}\binom{2n}{k} + \sum_{k=1}^{n}\binom{2n}{k-1}\\ &amp;= \binom{2n}{0} + \sum_{k=1}^{n}\binom{2n+1}{k} &amp; \text{(By Identity listed above)}\\ &amp;= \sum_{k=0}^{n}\binom{2n+1}{k} \end{align*}
102725
Prove $\sum_{i=1}^n2^{i-1}=\sum_{i=0}^{n-1}2^i=2^n-1$ combinatorially.  This is easy to prove inductively.  I know that $\sum_{i=0}^n{n\choose i}=2^n$ so maybe change $\sum_{i=0}^{n-1}2^i$ to $\sum_{i=0}^{n-1}\sum_{j=0}^i{i\choose j}$.  I also know that $2^n-1$ is the number of proper subsets in a set of size $n$.
54052
I would appreciate if somebody could help me with the following problem  Q: Seeking a combinatorial proof $(\binom{n}{k}=\frac{n!}{k! (n-k)!} )$  $$\sum _{k=0}^n (n-2 k)^2 \binom{n}{k}=n\times  2^n$$
116415
For any integers $n$, $k$, $r$ where $n\geq k\geq r \geq 0$, give a combinatorial proof of the following identity:   \begin{align} \binom{n}{k}\binom{k}{r}=\binom{n}{r}\binom{n-r}{k-r} . \end{align}   The problem is that I can't come up with a good counting argument of what exactly the two sides are doing. The left hand side is quite mysterious, and the right hand side is apparently choosing $r$ items and then choosing $k-r$ items from the remaining, which should be equivalent to $\binom{n}{k}$ but somehow isn't. How should I approach this problem?