Prove the identity:   $$ {2n\choose0} + {2n\choose2} + \dots + {2n\choose{2n}} = 2^{2n-1} $$        $\forall n\in\mathbb{N}$     Progress:    I've tried using the binomial theorem to get: $$ 2^{2n-1}=\sum\limits_{k=0}^{2n-1} {{2n-1}\choose k} $$ Followed by Pascal's: $$ {2n\choose k}={{2n-1}\choose k}+{{2n-1}\choose{k-1}} $$ Then: $$ 2^{2n-1}=\sum\limits_{k=0}^{2n-1} \Bigg({2n\choose k}-{{2n-1}\choose{k-1}}\Bigg) $$ However, I don't feel right about this.
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.
54720
Mathematica tells me that  $$\sum _{k=0}^n { n \choose k} \frac{(-1)^k}{2k+1} = \frac{(2n)!!}{(2n+1)!!}.$$  Although I have not been able to come up with a proof.  Proofs, hints, or references are all welcome.
109886
I have to give a combinatorial proof of  $$\sum_{k=1}^nk{n\choose k}^2=n{2n-1\choose n}.$$  I find it difficult to solve such problems. I'm not a brilliant person and never will be so I need to have algorithms to solve most problems. Usually I won't just "see" solutions unless I have a thorough enough understanding of a theory. This is also the case here. I know what the symbols mean, but I don't see what I should count and how to obtain the identity.  I think the right-hand side counts $n$-element subsets of a $(2n-1)$-element set with one element chosen to be "special". I think I should find a partition of the set of such subsets into $n$ parts so that the left-hand side is the sum of the cardinalities of the parts. Is there $n$ of anything on the right-hand side? Well, there are $n$ choices for the "special" elements, but only after I've chosen the $n$-element subset. Otherwise I can choose the "special element" in $2n-1$ ways.  This is a homework problem so I probably shouldn't ask for a full solution. But I would like to have some guidelines for approaching such problems, perhaps based on this example.
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
10141
Prove: $\binom{n}{0}F_0+\binom{n}{1}F_1+\binom{n}{2}F_2+\cdots+\binom{n}{n}F_n=F_{2n}$;  I was stuck with this question for a while... Help me please!!! Thanks!!!
122319
I need to prove this identity:  $\sum_{k=0}^n \frac{1}{k+1}{2k \choose k}{2n-2k \choose n-k}={2n+1 \choose n}$  without using the identity:  $C_{n+1}=\sum_{k=0}^n C_kC_{n-k}$.  Can't figure out how to.
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.
39421
I have to prove the identity using a combinatorial proof:  $\displaystyle\sum\limits_{k=0}^n 2^k \binom{n}{k} = 3^n$  I think this should be my combinatorial proof:  We want to form a committee of $k$ people from a total of $n$ people. There are two ways of counting this committee.  1) Go through each member from the $n$ total people, and decide if they should be added to the committee or not, until we have reached $k$ people. This gives us the LHS.  ...For the RHS, however, I am not sure how to form it. I think it should be something like forming subsets of $3$ people and choosing from that, but I'm not sure how that will form the same committee as the LHS.   EDIT: Okay, I also had the idea of forming a ternary string, and I could get the RHS this way. But I was not sure about the LHS. But the first answer gave me the right idea. Thanks a lot.
16105
How do you prove that $\sum\limits_{n=0}^{\infty}{2n \choose n}x^n=(1-4x)^{-1/2}$? I tried to identify the sum as a binomial series, but the $4$ and the $-1/2$ puzzle me. (This series arises in studying the first passage time of a simple random walk.)
37474
How would you prove that the generating function of $\binom{2n}{n}$ is $\frac{1}{\sqrt{1-4x}}$?  More precisely, prove that( for $|x|&lt;\frac{1}{4}$ ):  $$\sum^{\infty}_{n=0}x^n\binom{2n}{n}=\frac{1}{\sqrt{1-4x}}$$  Background: I was trying to solve $$S=\sum^{\infty}_{n=0}\frac{(2n+1)!}{8^n(n!)^2}=\sum^{\infty}_{n=0}\frac{(2n+1)}{8^n}\binom{2n}{n}$$ Which if we let $f(x)$ be the generating function in question, would be simply $$f(x)+2xf'(x)$$ With $x=\frac{1}{8}$. Is there a simple proof of the first identity?  states it without a proper reference ( states it without proof). Is there an easier way of calculating $S$? (which is $\sqrt{8}$, by 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?
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}$.
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?
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?
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.
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
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.