$$\sum_{\ell=k}^n \binom{\ell}{k} =  \binom{n+1}{k+1}$$  Can someone explain how we got that equation? Expanding it we get   $$\binom{k}{k} + \binom{k+1}{k} + \binom{k+2}{k} + .....+ \binom{n}{k}$$  but how does that add up to  $$\binom{n+1}{k+1}$$
8310
After reading , the most popular answer use the identity $$\sum_{t=0}^n \binom{t}{k} = \binom{n+1}{k+1}.$$  What's the name of this identity? Is it the identity of the  modified.  How can we prove it? I tried by induction, but without success. Can we also prove it algebraically?  Thanks for your help.    EDIT 01 : This identity is known as the  because, on Pascal's triangle, when the addends represented in the summation and the sum itself are highlighted, a hockey-stick shape is revealed.
41077
I have observed the following relation  $$\binom{n}{k}=\sum\limits_{i=0}^{k} \binom{n-i-1}{k-i}, \quad \frac{n}2\leq k \leq n-1$$  Numerical example with $n=5$ and $k=3$  $$\binom{\color{red}5}{\color{blueviolet}3}= \binom{\color{Magenta}4}{\color{blueviolet}3}+\binom{\color{blueviolet}3}{\color{Orange}2}+\binom{\color{Orange}2}{\color{YellowGreen}1}+\binom{\color{YellowGreen}1}{\color{Brown}0}$$  $$10\  \ \  = \  \ \ 4 \ \  \ +\ \  \ 3 \ \  \ +  \  \ \  2  \  \  \ \ + \ \ 1$$  Is this relation true? If yes, is there a name for it?  I´ve used identities like $\binom{n+1}{k+1} = \binom nk + \binom n{k+1}$ to show the relation above, but I failed. Does anyone have an idea how to manage it?  Thanks for taking time to read the question.
83623
I'm trying to prove the following equation above. So far I have: \begin{align} 2^{2n} &amp;= (1+1)^{2n}\\ &amp;= \sum_{k=0}^{2n}\binom{2n}{k}1^k1^{n-k} = \sum_{k=0}^{2n}\binom{2n}{k} &amp; \text{(By the Binomial Theorem)} \end{align}  I know I have to use the following identity somehow: $$\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}$$  How do I split my summation to get what I'm looking for? Thanks!  EDIT: HERE IS MY SOLUTION \begin{align*} 2^{2n} &amp;= (1+1)^{2n}\\ &amp;= \sum_{k=0}^{2n}\binom{2n}{k}1^k1^{2n-k} &amp; \text{(By the Binomial Theorem)}\\ &amp;= \sum_{k=0}^{n}\binom{2n}{k} + \sum_{k=n+1}^{2n}\binom{2n}{k}\\ &amp;= \sum_{k=0}^{n}\binom{2n}{k} + \sum_{k=n+1}^{2n}\binom{2n}{2n-k} &amp; \text{(Binomial Symmetry)}\\ &amp;= \sum_{k=0}^{n}\binom{2n}{k} + \sum_{k=0}^{n-1}\binom{2n}{k}\\ &amp;= \sum_{k=0}^{n}\binom{2n}{k} + \sum_{k=1}^{n}\binom{2n}{k-1}\\ &amp;= \binom{2n}{0} + \sum_{k=1}^{n}\binom{2n}{k} + \sum_{k=1}^{n}\binom{2n}{k-1}\\ &amp;= \binom{2n}{0} + \sum_{k=1}^{n}\binom{2n+1}{k} &amp; \text{(By Identity listed above)}\\ &amp;= \sum_{k=0}^{n}\binom{2n+1}{k} \end{align*}
64981
Is there any way to find:  $$\sum_{i=0}^n {\binom{n}{i}i^k}$$  I know that we can find it for small k by using binomial theorem by differentiating both sides and then multiplying both sides by x and repeating till the form presents itself and then putting x =1, but is there a way for any general power( k here) of i?
17936
Find the value of $\sum_0^n \binom{n}{k} (-1)^k \frac{1}{k+1}$.  Writing out several terms, I think the answer is $1/(n+1)$, but I'm struggling to prove this. I would greatly appreciate it if someone could show how to prove this.
33587
Prove that $\binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1}  $  Thanks in advance, my professor asked us to this a couple weeks ago, but I was enable to get to the right answer.   Good luck!  Here is what I got up to;  $\frac{(n+1)!}{(n-r)!(r+1)!} = \frac{(n)!}{(r)!(n-r)!} + \frac{(n)!}{(r+1)!(n-r-1)!}    $
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
23708
Find the value of $\sum_{k=1}^{n}k\binom{n}{k}$ ?    I know that $\sum_{k=0}^{n}\binom{n}{k}= 2^{n}$ and so, $\sum_{k=1}^{n}\binom{n}{k}= 2^{n}-1$ but how to deal with $k$ ?
59736
How do I see that$$\sum_{k \ge 0} \binom{n}{3k} = (1 + 1)^n + (\omega + 1)^n + (\omega^2 + 1)^n,$$where $\omega = \text{exp}\left({2\over3}\pi i\right)$? What is the underlying intuition behind this equality?
62841
Reading through my textbook I came across the following problem, and I am looking for some help solving it. In the back of the textbook they have shown the final answer but I'm not quite sure how to get there. If I could get some help that would be great, thanks!  Find,  $$\sum_{k=0}^{n}4^k \binom{n}{k}$$  The solution given is,  $$C(7,1)C(4,1)+C(7,2)C(4,2)+C(7,3)C(4,3)+C(7,4)C(4,4)$$
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?
74721
Evaluate the summation of: $$ \sum_{k=1}^n {n \choose k-1} {n \choose k} $$ I have been trying to solve this problem by translating C(n, k-1) into C(n, k), because I know that: $$ \sum_{k=1}^n {n \choose k}^2={2n \choose n} $$ However, I haven't been having any luck. Am I on the right track? What am I doing wrong?
29977
A known identity of binomial coefficients is that $$ \sum_i\binom{m}{i}\binom{n}{j-i}=\binom{m+n}{j}. $$ Is there a combinatorial proof/explanation of why it holds? 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?
122267
I still haven't quite realized how to solve binomial coefficient problems like this, can someone show me an elaborated way of solving this?  I need to write this expression in a more simplified way: $\sum_{k=0}^{10} k \pmatrix{10 \\ k}\pmatrix{20 \\ 10-k}$  I'm aware of the binomial identity $\sum_{k=i}^{n-j}\binom{k}{i}\binom{n-k}{j}=\binom{n+1}{j+1}$  Just can't seem to see how to use it.  Many thanks.
28191
I'm sure there's an identity or some known "trick" to solve this but I couldn't find it (Looked in Wikipedia, Wolfram and here):  $$ \sum_{k=0}^n (-1)^k{n \choose k} =0 $$  I want to know how this can be proven. I tried induction but I'm not sure what to do with ${{n+1}\choose k}$.  Thanks!
90426
I need to show that $$\sum\limits_{k=i}^{n}\binom{n}{k}\binom{k}{i} = \binom{n}{i}2^{n-i}$$  I know that $\displaystyle \binom{n}{k}\binom{k}{i}$ is counting the number of ways to pick $k$ elements from $n$ and then $i$ elements from those $k$, so $\displaystyle \sum\limits_{k=i}^{n}\binom{n}{k}\binom{k}{i}$ is counting the number of ways to do that $\forall k$.  I know that $\displaystyle \binom{n}{i} = \binom{n}{n-i}$ and that $2^{n-i}$ is the number of elements in the power set for $[n]\setminus[i]$.  How do I show that both sides are equivalent? I'm stumped on this one. Could anyone give me a pointer in the right direction?