prove the following identity:  $\displaystyle\sum_{k=0}^{n}\frac{1}{k+1}\binom{2k}{k}\binom{2n-2k}{n-k} = \binom{2n+1}{n}$  what I tried:  I figured that: $\displaystyle\binom{2n+1}{n} = (2n+1) C_n$ and $\displaystyle\sum_{k=0}^{n}\frac{1}{k+1}\binom{2k}{k}\binom{2n-2k}{n-k}= \sum_{k=0}^{n}C_k\binom{2n-2k}{n-k}$  from here i tried simplifying:$\displaystyle\binom{2n-2k}{n-k}$ to something i could work with but did not succeed  I also know that $\displaystyle C_n = \sum_{k=0}^{n-1}C_k C_{n-k-1}$ so I tried to prove : $\displaystyle\sum_{k=0}^{n}C_k\binom{2n-2k}{n-k}= C_n + \sum_{k=0}^{n-1}C_k\binom{2n-2k}{n-k} = C_n + 2n\sum_{k=0}^{n-1}C_kC_{n-k-1}$ but that approach also failed (couldn't prove the last equality)  any suggestions?
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.
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?
80878
I need a hand in showing that $$ \sum_{n=2}^m \binom{n}{2} = \binom{m+1}{3}$$   Thanks in advance for any help.
70280
Prove that $\displaystyle \sum^{n}_{r=0}(-1)^r\cdot \large\frac{\binom{n}{r}}{\binom{r+3}{r}} = \frac{3!}{2(n+3)}$   $\bf{My\; Try::}$ We can write $$\frac{\binom{n}{r}}{\binom{r+3}{r}} = \frac{n!}{r!\times (n-r)!}\times \frac{r!\times 3!}{(r+3)!} = \frac{3!\times n!}{(n-r)!\times (r+3)!}$$  So our sum is $$ 3!\sum^{n}_{r=0}(-1)^r\frac{n!}{(n-r)!\times (r+3)!} = \frac{3!}{(n+1)(n+2)(n+3)}\sum^{n}_{r=0}(-1)^r\frac{(n+3)!}{(r+3)!\times (n-r)!}$$  So we get Sum $$ \frac{3!}{(n+1)(n+2)(n+3)}\sum^{n}_{r=0}(-1)^r\binom{n+3}{r+3} = -\frac{3!}{(n+1)(n+2)}\sum^{n}_{r=0}(-1)^{r+3}\binom{n+3}{r+3}$$  $$  = -\frac{3!}{(n+1)(n+2)(n+3)}\left[-\binom{n+3}{3}+\binom{n+3}{4}-\binom{n+3}{5}--.......+(-1)^{n+3}\binom{n+3}{n+3}\right]$$  $$=-\frac{3!}{(n+1)(n+2)(n+3)}\left[\binom{n+3}{0}-\binom{n+3}{1}+\binom{n+3}{2}-\binom{n+3}{3}+\binom{n+3}{4}-\binom{n+3}{5}--.......+(-1)^{n+3}\binom{n+3}{n+3}\right]+\frac{3!}{(n+1)(n+2)(n+3)}\left[\binom{n+3}{0}-\binom{n+3}{1}+\binom{n+3}{2}\right]$$  So we get $$ = \frac{3!}{(n+1)(n+2)(n+3)}\left[1-(n+3)+\frac{(n+3)(n+2)}{2}\right] = \frac{3!}{(n+1)(n+2)}\times \frac{n^2+3n+2}{2} = \frac{3!}{(n+1)(n+2)(n+3)}\times \frac{(n+1)(n+2)}{2} = \frac{3!}{2(n+3)}$$  Can we prove it Using Combinatorial way,bcz above method is very lengthy  If yes then plz explain here  Thanks
55711
Why is $\displaystyle\sum\limits_{k=0}^{n}(-1)^k\binom{n}{k}^2=(-1)^{n/2}\binom{n}{n/2}$ if $n$ is even ?   The case if $n$ is odd, is clear, since $\displaystyle(-1)^k\binom{n}{k}+(-1)^{n-k}\binom{n}{n-k}=0$ (we have $(n+1)/2$ such pairs.)  but if $n$ is even we have no symmetry, I tried to consider the odd and even terms separately but with no success.   Do you have an idea ? Thanks in advance.
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$.
70000
I have to prove that:     $$\sum_{k=0}^{n} {{m+k} \choose{m}} = { m+n+1 \choose m+1 }$$   I tried to open up the right side with Pascal's definition that: $$ { n \choose k} = {n-1 \choose {k}} + {n-1 \choose {k-1}}$$  Here is what I came up with, and I am sure it is wrong because it does not equal the left side:  $$ {m+n+1 \choose m+1} = {m+n \choose m+1} + {m+n \choose m} = ... ={m+n \choose m+1} + {m+n-1 \choose m} + {m+n-2 \choose m-1} + ... + {m \choose m+1} = \sum_{k=0}^{n} {m+k \choose m+k-n+1 }  $$  Which, again, probably is wrong because it is not equal $\sum_{k=0}^{n} { m+k \choose m}$. Any help is appreciated
110616
The sum of the series $$\binom{n}{0}-\binom{n-1}{1}+\binom{n-2}{2}-\binom{n-3}{3}+..........$$   $\bf{My\; Try::}$ We can write it as $\displaystyle \binom{n}{0} = $ Coefficient of $x^0$ in $(1+x)^n$   Similarly $\displaystyle \binom{n-1}{1} = $ Coefficient of $x^1$ in $(1+x)^{n-1}$  Similarly $\displaystyle \binom{n-2}{2} = $ Coefficient of $x^2$ in $(1+x)^{n-2}$  Now, how can I solve it after that, Help Required, Thanks
18697
Wikipedia has a proof of the identity $$ H_{n} =\sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} \frac{1}{k}$$    Curiously, there is also the identity  $$ \frac{1}{n} = \sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} H_{k} $$  Can the second identity be derived from the first one?
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.
50713
Show that $\displaystyle\sum_{i=0}^l \dfrac{{l\choose i}}{{n\choose k + i}} = \dfrac{n+1}{(n-l+1) {n-l\choose k}}$ for all $k,l, n\geq 0$ with $k+l \leq n.$  The $k+l\leq n$ part doesn't seem that important. The claim clearly holds for $n=0,$ and in that case $k$ and $l$ must both be zero. I think the claim can be shown by induction, but I'm not sure how to do so; I'm not sure how to use the inductive hypothesis to prove the inductive step. The sum on the LHS is not always an integer, so finding a combinatorial argument doesn't seem very feasible. For $n = 1,$ we can have $(k,l) = (0,0), (1,0), (0,1),$ and in each case the sum holds. Perhaps multiplying both sides by a number (idk ${n-l\choose k}$) might be useful?
102133
I am trying to prove the follwowing: $$\sum_{k=0}^n F_kF_{n-k}=\sum_{k=0}^n(k+1)F_{k+1}(-2)^{n-k}$$  where $F_k = F_{k-1} + F_{k-2}$ with $F_0 = F_1=1$ are the Fibonacci numbers.  Now the left hand side of the identity is simply the cauchy product of the $n$-th coefficient of the generating function multiplied by itself, meaning the $n$-th coefficient of  $$F(z)\cdot F(z)$$ where $F(z)=\sum_{k\ge 0} F_k z^k$. I am not sure however, if this insight really helps a lot. The only thing I know about the coefficients are its explicit form $$F_k=\sum_{k\ge 0}\binom{n-k}{k}$$ but this did not lead to any results as I would be left with  $$\sum_{k=0}^n F_kF_{n-k}=\sum_{k=0}^n\sum_{l\ge 0 }\binom{n-l}{l}\sum_{j\ge 0}\binom{n-j}{j}$$  I would appreciate any hints or ideas.
67305
Suppose that $\displaystyle\frac{1}{a}+\frac{1}{b}+\frac{1}{c}=\frac{1}{a+b+c}$ . Then , prove that $\displaystyle\frac{1}{a^5}+\frac{1}{b^5}+\frac{1}{c^5}=\frac{1}{a^5+b^5+c^5}.$  Attempt :  From the given relation , $\displaystyle \frac{a}{b}+\frac{b}{a}+\frac{b}{c}+\frac{c}{b}+\frac{a}{c}+\frac{c}{a}=-2$.........(1)  Now I want to calculate , $\displaystyle \frac{a^5}{b^5}+\frac{b^5}{a^5}+\frac{b^5}{c^5}+\frac{c^5}{b^5}+\frac{a^5}{c^5}+\frac{c^5}{a^5}$. I tried by expanding pair of terms and putting the value of (1), but it can't help...
60124
It's asked to simplify the sum  $$\displaystyle\sum_{0\le i &lt;j\le n+1} \binom{n}{i} \times \binom{n+1}{j} $$  inspecting first values of $n$ shows the sum if apparently equal to $4^n$  I tried re-writing the sum as   $$\displaystyle\sum_{j=1}^{n+1} \binom{n+1}{j} \displaystyle\sum_{i=0}^{j-1} \binom{n}{i}  $$ but that doesn't seem to lead us to the result.  Any suggestions are welcome.  Thanks.
77151
In a proof I've come across the following identity:     $$ \sum_{l=0}^{n-j} \binom{M-1+l}{l} \binom{n-M-l}{n-j-l} = \binom{n}{j} $$   I see that it's right, when plugging in numbers, but I don't see the algebraic or combinatorial proof behind it. Can anyone help me with that?
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.
123944
[Corrected question]  I'm struggling at proving the following combinatorical identity: $$\sum_{k=0}^{n}k{n\choose k}^2 = n{2n-1 \choose n-1} $$ I would like to see a combinatorical (logical) solution, or an algebraic solution.