I'm undergraduate student of mathematics.  I need to prove: $$\sum_{k=0}^{n} \binom{2n}{2k}= 2^{2n-1}$$ Can you please help me
23483
I'm repeating material for test and I came across the example that I can not do. How to calculate this sum: $\displaystyle\sum_{k=0}^{n}{2n\choose 2k}$?
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
49701
I know that $$\sum_{k=0}^n \binom nk k^2=2^{n-2}(n^2+n),$$ but I cannot find a way how to prove it. I tried induction but it did not work. On wiki they say that I should use differentiation but I do not know how to apply it to binomial coefficient.  Thanks for any response.  (Presumptive) Source: Theoretical Exercise 1.12(b), P18, A First Course in Pr, 8th Ed, by S Ross
33723
Question:  $$\sum_{k=1}^{n}k\binom{2n}{n+k}=\frac n2\binom{2n}{n}$$ is true for every $n\in \mathbb N$? If this is true, then how can we prove this?   When I was playing with numbers, I conjectured this. Though I found that this holds for many $n$s, I haven't found any proof. Can anyone help?
26130
Why is $\sum_{k=0}^n (_k^n) 2^k$ simplified as $3^n$ and not just $2^n$ ? The answer uses the binomial theorem as a solution: let $a=1$ and let $b=2$. So $1+2 = 3$. But since $1+2 = 3$ why do we not use $1+1 = 2$?
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?
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}$
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?
115268
Prove by induction: $$\sum_{k=1}^{n} \binom n k = 2^n -1 $$ for all $n\in \mathbb{N}$.   Today I wrote calculus exam, I had this problem given.  I have the feeling that I will get $0$ points for my solution, because I did this:   Base Case: $n=1$ $$\sum_{k=1}^{1} \binom 1 1 = 1 =  2^1 -1 .$$  Induction Hypothesis: for all $n \in \mathbb{N}$: $$\sum_{k=1}^{n} \binom n k = 2^n -1 $$  Induction Step: $n \rightarrow n+1$ $$\sum_{k=1}^{n+1} \binom {n+1} {k} = \sum_{k=1}^{n} \binom {n+1} {k} + \binom{n+1}{n+1} = 2^{n+1} -1$$  Please show me my mistake because next time is my last chance in this class.
51603
Prove the identity:  $$n(n-1)2^{n-2}=\sum_{k=1}^n {k(k-1) {n \choose k}}$$  I tried using the binomial coefficients identity $2^n = \sum_{k=1}^n {n \choose k}$  but got stuck along the way.
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?
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.
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.
83167
$$2^{n-2} n (n -1) = \sum\limits_{k=2}^n k (k - 1) \binom{n}{k}.$$  I'm completely stumped. I just have no idea how to do this. What I've tried so far has been simplifying the right hand side slightly to $\sum\limits_{k=2}^n \binom{n}{k - 2}$, and then proving that this somehow is equal to some manipulation of the left hand side. I can't seem to find any breakthroughs that way though.  If anyone could help out or point me in the right direction that would be great.  EDIT: I've actually just realized my simplification of the right hand side is wrong. Now I'm even more stuck.
68476
Here's how it is.  So I was studying some notes on Discrete Structures then I discovered this. Prove that $2^N = \binom{N}{0} + \binom{N}{1} + \binom{N}{2} + \dots + \binom{N}{N}$ Since I was new to this, I didn't quite understand it.  I tried using the binomial expansion but it confused me a little.  Can someone please help me solve this.  That would be great.
65141
Prove that$$\overbrace{\binom n 0 + \binom n 1 + \binom n 2 + \cdots + \binom{n}{\frac{n-1} 2}} + \overbrace{\binom n {\frac{n+1} 2} + \cdots + \binom n {n-1} + \binom n n} = 2^n. $$   Background:  This problem came from the following link:    and I didn't understand why that was true in which no one on the page has proved it to be so. and i was wondering what was the proof on that
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  .