Suppose we have the following two identities:    $\displaystyle \sum_{k=0}^{n} \binom{n}{k} = 2^n$ $\displaystyle \sum_{k=0}^{n} (-1)^{k} \binom{n}{k} = 0$   The first says that the number of subsets of an $n$-set is $2^n$. The second says that the number of subsets of even size equals the number of subsets of odd size (of an $n$-set). Thus there are $2^{n-1}$ subsets of even length and $2^{n-1}$ subsets of odd length?  To combinatorially prove the second identity, let $A$ be a $k$-subset of $[n]$. Then note whether $k$ is odd or even?
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?
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?
57034
Determine the value of $\displaystyle \sum_{k=n}^{2n} \binom{k} {n} 2^{-k}$ for $n \geq 1$  My attempt: I have asked this question before in another math forum but it leads no solution. My friend suggested me to search for something like series-k. I also looked at my textbook in combinatoric section (which apparently leads to Binomial Theorem), but really I don't have any idea for this one.  Could you help me?
64671
I stumbled across this identity involving binomial coefficients this morning:  If $n$, $k$, $a$, and $b$ are positive integers and $n=a+b$, then  $$ \binom{n}{k} =\sum_{i=0}^k \binom{a}{k-i}\binom{b}{i}.$$  The proof is trivial. (Partition a set $N$ of $n$ things into disjoint sets $A$ of $a$ things and $B$ of $b$ things. Now to pick $k$ items from $N$, either all $k$ are from $A$, or $k-1$ are from $A$ and $1$ is from $B$, or...)  Has this identity appeared before (I expect the answer to be "Yes!") and if so, does it have a name?
88921
Can this identity be derived from the binomial theorem?  $$n(n+1)2^{n-2} = \sum_{i=1}^{n}  i^2 \binom{n}{i}$$    I tried starting from $2^n = \displaystyle\sum_{i=0}^{n} \binom{n}{i}$ and dividing it by $4$ in order to get $2^{n-2}$.
16744
I am trying to prove the following identities:  a. $$\sum_{k=0}^n(-1)^k{n\choose k}^2 = \bigg\{^{0 \ \text{if k is odd}}_{(-1)^m{2m\choose m} \ \text{if n = 2m}}$$ b. $$\sum^k_{i=0} {n+i \choose i}={n+k+1\choose k}$$  For part $b$ I know I can use induction. It is clearly true when $k=0$ and then assuming for $k-1$ we get $$\sum^k_{i=0}{n+i\choose i}={n+k\choose k-1}+{n+k \choose k}={n+k+1\choose k} \ ...$$
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?
66192
Let n be an even integer. How many different ways can I choose subsets of the set {1,2...,n} if they all have to have odd size, but the intersection of any two of them has to have even size?  Please help me answer this question or lead me in the right direction. Thank you :)
81704
The identity I am interested in reads, $$ \sum_{k=0}^{n-1} {2k \choose k} \cdot 2^{2(n-k)} = 2n \cdot {2n \choose n}. $$ It is not hard to prove using the generating functions, but it seems that there should be a combinatorial argument. I tried different ideas with lattice path counting, but without success.   Update: I found a related discussion , however, among the many arguments there is no combinatorial one.  Update 2: it seems I have found a combinatorial proof (quite indirect), but will post it only after the bounty expires. I hope someone comes up with an answer before this so that the bounty is not wasted.
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?
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*}
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?
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?
7156
Prove that   $$\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$$   I can't find counting interpretations for either of the sides. A hint of "if $S$ is a subset of $\{1, . . . , n\}$ and $S^\prime$ is its complement then $|S| + |S^\prime| = n$" was also given, but I still don't know how to begin.
73413
I want to prove the following equality:  $$\displaystyle\sum_{k=1}^{n}k{n \choose k}2^{n-k}=n3^{n-1}$$  So I had an idea to use $((1+x)^n)'=n(1+x)^{n-1}$  So I could just use the binomial theorem and let $$x=2 \implies (n3^{n-1})$$ and then modify the sum into that one on the left side.  So I need to prove that : $$\displaystyle\sum_{k=1}^{n}k{n \choose k}2^{n-k}=n(1+x)^{n-1}$$ if$$x=2$$ Any help would be appreciated.
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$$
95326
I'm trying to figure out a combinatorial proof for:  $$\displaystyle \sum_{k \mathop = 0}^n \binom {r+k} k = \binom {r + n + 1} n$$  I've tried the committee counting thing, but that didn't work.