Prove that $\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+...=\binom{n}{1}+\binom{n}{3}+\binom{n}{5}+...$ using a combinatorial approach, NOT an algebraic approach.  Fot values of $n$ which are odd this is simple, using Pascal's identity and/or Pascal's triangle, but I am not sure how to approach this for even values of $n$. Thank you for your help.
123247
What number do I get if I subtract the binomial coefficients $n\choose k$ with an even $k$ from those with an odd $k$, where $n$ is fixed? Am I supposed to subtract a binomial coefficient with an even $k$ from one with an odd $k$ and say what the number you would get or how exactly does this work?
99124
I need to evaluate, for a certain worded question:   If n is even $$\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots\binom{n}{n}$$  If n is odd $$\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots\binom{n}{n-1}$$   I havent been able to reduce this using the binomial expansion.
19470
The left hand side has terms involving  $\binom{n}{m}= \dfrac{n!}{(n-m)!m!}$    $$1+\dfrac{1}{2}\binom{n}{1} +\frac{1}{3}\binom{n}{2}+...........+\frac{1}{n+1}\binom{n}{n} = \dfrac{2^{n+1}-1}{n+1}$$  I've done induction and proved $P(0)$ holds and also $P(1),P(2)$ holds (Just in case)  Now I've found $P(K+1)$ so the sum on the left is going to equal $\dfrac{2^{n+1}-1}{n+1}$ + $\dfrac{1}{n+2}$  and the right hand side is going to equal $\dfrac{2^{n+2}-1}{n+2}$  My problem is coming with the algebra though. I can't get those sides to equal. I can't get rid of the $n+1$ in the denominator.   Anyone have any ideas for me? They'd be much appreciated!  P.S. Someone gave me a hint and said that you can use the binomial theorem to solve this.
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?
116086
Question: If $(1+x)^n=\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+\dotsm+\binom{n}{n}x^n$, prove that $\binom{n}{1}-2\binom{n}{2}+3\binom{n}{3}-\dotsm+(-1)^{n-1}n\binom{n}{n}=0$  My attempt:  I wrote the expression for $\binom{n}{k}$ for each term in the L.H.S and then tried to simplify but could not reach the R.H.S.  Please help. I have no idea on how to begin. I am not allowed to use calculus.
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.
25606
Can someone give me a hint how to evaluate $$ \binom{n}{0}+\binom{n}{2}+\cdots+\binom{n}{o(n)},$$ where $o(n)$ is $n$ if $n$ is even and $n-1$ otherwise ?
109085
How can you show that $$ \binom{2n}{n}^2 = \sum_{m=0}^{n} \binom{2n}{2m} \binom{2m}m \binom{2n-2m}{n-m} $$?  I was fooling around with random walks, and apparently both expressions are supposed to be the number of unweighted random walks on a 2D square lattice of $2n$ steps that ends at the origin.  Whole thing reminds me of Vandermonde's identity but I can't it. Any hints?
104266
Please give me feedback on my answer to this question. Question: For all $ n\geq1:\binom{2n}{0}+\binom{2n}{2}+\binom{2n}{4}+\cdots+\binom{2n}{2k}+\cdots+\binom{2n}{2n} $   is equal to $ \binom{2n}{1}+\binom{2n}{3}+\binom{2n}{5}+\cdots+\binom{2n}{2k+1}+\cdots+\binom{2n}{2n-1} $. Answer: False, since;  Let $a=1,  b=-1$  and $n=1$  ,$k=0$   , using Binomial expression.  $$(a+b)^n=  \sum   \binom{n}{k}  a^{k}b^{n-k}$$  Then $(1+-1)^{2(1)}=\binom{2}{0}1^{0}(-1)^{2-0}+\binom{2}{1}1^{1}(-1)^{2-1}+\binom{2}{2}1^{2}(-1)^{2-2}=\binom{2}{0}-\binom{2}{1}+\binom{2}{2}$  Thus :For all $n\geq1:  \binom{2n}{0}+\binom{2n}{2}+\binom{2n}{4}+\cdots+\binom{2n}{2k}+\cdots+\binom{2n}{2n}   \ne \binom{2n}{1}+\binom{2n}{3}+\binom{2n}{5}+\cdots+\binom{2n}{2k+1}+\cdots+\binom{2n}{2n-1}$  .
54004
How do I prove $2 \binom n2 + 4 \binom n4 + 6 \binom n6 + \cdots = n 2^{n-2}$  I thought about using known $\sum k\binom nk = n2^{n-1} $ and then just dividing it by 2. But is it possible you can help me with writing the full solution, because for the first known theorem you need to derivate $(a+b)^n $and also $a=1, b=x$. But for this one it won't work. maybe I can just prove that known theorem I presented, prove it, and then just divide it by 2. because the known theorem is  $1 \binom n2 + 2 \binom n4 + 3 \binom n6 + \cdots$ (co efficients are divided by two than the presented question)  Edit: I posted a solution.
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}$
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.
64945
I'm really iffy on combinatorial proofs in general and now that there is a sum, it's just confused me even more. Can someone try and walk me through this proof?  $$ \binom{m + n}{r} = \sum_{k=0}^r \binom{m}{k}\binom{n}{r - k} $$
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.
88724
By Newton's Formula:  $$(a+b)^n = \sum_{k=0}^n \binom{n}{k} a^{n-k}b^k $$ Proof that every $\dbinom{n}{k}$ is odd if and only if $n=2^r-1$.   I have already shown that if $n$ is of the form $2^r-1$, having used the property  $$\binom{n-1}{k} = \binom{n}{k}-\binom{n}{k-1}+ \binom{n}{k-2} - \cdots \pm \binom{n}{0}.$$ But I have not been able to demonstrate "$\Rightarrow$".   Please, help me! Thanks.
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  .
36137
So I came across Pascal's identity: Prove that for any fixed $r\geq 1$, and all $n\geq r$, $$ \binom{n+1}{r}=\binom{n}{r}+\binom{n}{r-1}. $$  I know you can use basic algebra or even an inductive proof to prove this identity, but that seems really cumbersome. I was wondering if anyone had a "cleaner" or more elegant way of proving it. For example, I think the following would be a decent combinatorial proof.   Proof: Let $S$ be a set with $n+1$ elements, and consider some fixed $x\in S$. There are $\binom{n+1}{r}\;\; r$-subsets of $S$--count them according to whether or not they contain $x$: there are $\binom{n}{r}$ not containing $x$, (each formed by choosing $r$ of the remaining $n$ elements in $S\setminus\{x\}$), and there are $\binom{n}{r-1}\;\; r$-sets containing $x$, (each formed by selecting an additional $r-1$ elements in $S\setminus\{x\}$).   Is that right? Are there any other efficient ways of doing it?