Prove ${2n\choose n}=\sum\limits_{k=0}^n {n\choose k}^2$     My Approach: I will be making use of $$\tag 1\quad{m+n\choose r} = {m\choose 0}{n \choose r} + {m\choose 1}{n\choose r- 1} + \cdot\cdot\cdot + {m\choose r}{n \choose 0}$$ and $$\tag 2{a \choose b}={a\choose a-b}$$     By (1) $${2n\choose n} = {n+n\choose n}= {n\choose 0}{n\choose n}+{n\choose 1}{n\choose n-1}+\cdot\cdot\cdot + {n\choose n}{n\choose 0}$$  By (2) $${2n\choose n} = {n\choose 0}^2 + {n\choose 1}^2 + \cdot\cdot\cdot + {n\choose n}^2$$  Then $${2n\choose n}=\sum\limits_{k=0}^n {n\choose k}^2$$    Please have a look at my solution and give me any hints and\or suggestions you may have.
883
I was hoping to find a more "mathematical" proof, instead of proving logically $\displaystyle \sum_{k = 0}^n {n \choose k}^2= {2n \choose n}$.  I already know the logical Proof:  $${n \choose k}^2 = {n \choose k}{ n \choose n-k}$$  Hence summation can be expressed as:  $$\binom{n}{0}\binom{n}{n} + \binom{n}{1}\binom{n}{n-1} + \cdots + \binom{n}{n}\binom{n}{0}$$  One can think of it as choosing $n$ people from a group of $2n$  (imagine dividing a group of $2n$ into $2$ groups of $n$ people each. I can get $k$ people from group $1$ and another $n-k$ people from group $2$. We do this from $k = 0$ to $n$.
62005
4 . (a) Prove that   $$\sum_{k=0}^l \binom{n}{k} \binom{m}{l-k} = \binom{n+m}{l}.$$   Hint: Apply the binomial theorem to $(1+x)^n(1+x)^m$.   I'm having a hard time trying to solve the problem above. I've done all of the previous exercises of the 2nd chapter with little difficulty, so far. I think I might be missing a trivial point somewhere.    The answer I got from the Answer Book, and is not very helpful either... :(      4. (a) Since $(1+x)^n(1+x)^m = (1+x)^{n+m}$  we have  $$\sum_{k=0}^n \binom{n}{k}x^k\cdot\sum_{j=0}^m \binom{m}{j}x^j\cdot=\sum_{l=0}^{n+m} \binom{n+m}{l}x^l$$  But the coefficient of $x^l$ on the left is clearly $$\sum_{k=0}^l\binom{n}{k}\binom{m}{l-k}.$$  One term of the sum occurring for each pair $k$, $j = l-k$.     I couldn't get the last part of the answer: why is it that the "coefficient of $x^l$ on the left is clearly $\sum_{k=0}^l\binom{n}{k}\binom{m}{l-k}$."?
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$$
85347
I'm trying to prove the following  $$ \sum_{r=0}^{n}(r+1) \binom{n}{r} = (n+2)2^{n-1} $$  using the identity $$ \sum_{r=0}^{n} \binom{n}{r} = 2^{n} $$  but I'm not able to. This is what I did so far,   $$ \sum_{r=0}^{n}(r+1) \binom{n}{r} = (1) \binom{n}{0} + (2) \binom{n}{1} + ... + (n+1) \binom{n}{n} $$
119758
Is it true that $\sum_kk\binom{n}{k}^2=n\binom{2n-1}{n-1}$? (I proved it using generating functions). Could you help me to prove it combinatorially? please
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.
110400
I need to prove the following: $$\sum_{k=0}^n {n \choose k}\cdot\frac{(-1)^k}{k+1} = \frac{1}{n+1}$$  Started from the left, I got this far:  $$\frac{1}{n+1}+\sum_{k=1}^n {n+1 \choose k+1}\cdot(-1)^k$$  Am I right so far? Any ideas how to move on? thanks.  Edit: I guess my last move had a mistake, then perhaps this is ok? $$\frac{1}{n+1}\cdot\sum_{k=0}^n {n+1 \choose k+1}\cdot(-1)^k$$  How do you suggest I move on?
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
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?
91965
I can't figure out an algebraic proof for the following identity, (and I don't know if I can use the binomial theorem for this one): $$\sum_{k=0}^m(-1)^{m-k}{{n \choose {k}}}= {{n-1}\choose m}$$  Thank you, for your help in advance.
77669
Show that $\frac{2^{2n}}{2n} \le {2n \choose n}$, $n\in\mathbb{N}$.  What I can see easily is that $\frac{2^{2n}}{2n + 1} \le {2n \choose n}$, since $(1+1)^{2n} = \sum_{m=0}^{2n}{2n \choose m} = 2^{2n}$. This sum contains $2n+1$ terms with the largest being ${2n \choose n}$. So ${2n \choose n}$ is larger than $\frac{2^{2n}}{2n + 1}$. However I have found the statement $\frac{2^{2n}}{2n} \le {2n \choose n}$, which is not obvious to me.
52285
I am trying to get a combinatorial proof for this summation identity, for $0\leq k\leq \frac{n}{2}$ $$\sum_{m=k}^{n-k}\binom{m}{k}\binom{n-m}{k}=\binom{n+1}{2k+1}$$  The way I interpreted is that, for the right hand side $\binom{n+1}{2k+1}$ is the number of ways to choose $2k+1$ from total of $n+1$, then for left hand side, condition on dividing $n+1$ into two groups of size $m+1$ and $(n+1)-(m+1)=n-m$, then if choose $k$ the group of $n-m$ then it gives $\binom{n-m}{k}$, so there are $2k+1-k=k+1$ to choose from the group of size $m+1$, this is $\binom{m+1}{k+1}$, therefore I got the left hand side as $\sum_{m=k}^{n-k}\binom{m+1}{k+1}\binom{n-m}{k}\neq\sum_{m=k}^{n-k}\binom{m}{k}\binom{n-m}{k}$. what did I do wrong here? please help.
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!!!
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.
19037
Let $n$ be a positve integer. Prove that$$\sum\limits^m_{k=0} \frac{2n-k\choose k}{2n-k\choose n}\frac{2n-4k+1}{2n-2k+1}2^{n-2k}=\frac{n\choose m}{2n-2m\choose n-m}2^{n-2m}$$ for each non-negative integers $m\leq n$.  I know this is to be done by induction. Base case is easy. But I can't simplify expression for $(m+1)$. Please guide.   Edit: $\large P(m+1)=P(m)+\frac{2n-(m+1)\choose m+1}{2n-(m+1)\choose n}\cdot\frac{2n-4(m+1)+1}{2n-2(m+1)+1}\cdot2^{n-2(m+1)}$  $\Large=\frac{n\choose m}{2n-2m \choose n-m}.2^{n-2m}+\frac{2n-m-1\choose m+1}{2n-m-1\choose n}\cdot\frac{2n-4m-3}{2n-2m-1}.2^{n-2m-2}$   It must be equal to $\Large\frac{n\choose m+1}{2n-2m-2\choose n-m-1}.2^{n-2m-2}$  So lets try to simplify it-   $\Large=\frac{n!(n-m)!}{m!(2n-2m)!}.2^{n-2m}+\frac{n!(n-m-1)!}{(m+1)!(2n-2m-2)!}\cdot\frac{2n-4m-3}{2n-2m-1}\cdot2^{n-2m-2}$   $\Large=\frac{2^{n-2m-2}\cdot n!(n-m-1)!}{m!(2n-2m-2)!(2n-2m-1)}[\frac{2}{1}+\frac{1}{(m+1)}\cdot\frac{2n-4m-3}1]$   $\Large=\frac{2^{n-2m-2}\cdot n!(n-m-1)!}{m!(2n-2m-2)!(2n-2m-1)}[\frac{2n-2m-1}{m+1}]$   $\Large=\frac{2^{n-2m-2}\cdot n!(n-m-1)!}{(m+1)!(2n-2m-2)!}$  $\Large=\frac{\frac{n!}{(m+1)!(n-m-1)!}}{\frac{(2n-2m-2)!}{(n-m-1)!(n-m-1)!}}\cdot2^{n-2m-2}$  $\Large=\Large\frac{n\choose m+1}{2n-2m-2\choose n-m-1}.2^{n-2m-2}$   I think it is right. But is there any shorter way also?
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?
45758
I'm studying for a midterm and need some help with proving summation     $$\sum\limits_{k=0}^n\binom{n}{k}2^k = 3^n$$   using the binomial theorem.  This is what I've been thinking so far:   In the binomial theorem, we set $x = 0$ and $y = 2$, so:  $3^n = (x+y)^n = \sum\limits_{k=0}^n\binom{n}{k}y^k$  $ = \sum\limits_{k=0}^n\binom{n}{k}2^k$  Am I getting this correct so far or completely wrong? Any help would be appreciated. Thanks.