Linked Questions

45
votes
13answers
8k views

Proof of the Hockey-Stick Identity: $\sum\limits_{t=0}^n \binom tk = \binom{n+1}{k+1}$

After reading this question, 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 Pascal's triangle ...
9
votes
3answers
3k views

Proving that $\sum\limits_{k=0}^{n} {{m+k} \choose{m}} = { m+n+1 \choose m+1 }$ [duplicate]

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 \...
2
votes
4answers
4k views

Fermat's Combinatorial Identity: How to prove combinatorially? [duplicate]

$$\binom{r}{r} + \binom{r+1}{r} + \binom{r+2}{r} + \dotsb + \binom{n}{r} = \binom{n+1}{r+1}$$ I don't have much experience with combinatorial proofs, so I'm grateful for all the hints. (Presumptive) ...
6
votes
4answers
465 views

Combinatorial Proof for Binomial Identity: $\sum_{k = 0}^n \binom{k}{p} = \binom{n+1}{p+1}$ [duplicate]

I am studying combinatorics and I came across the identity $$\sum\limits_{k=0}^n \binom kp =\binom {n+1}{p+1}.$$ I have read the algebraic proof and it does not appeal to me. Is there an elegant ...
1
vote
2answers
2k views

Show $\sum_{k=0}^{m} \binom{n-k}{m-k}=\binom{n+1}{m}$ [duplicate]

My question is: show $$\sum_{k=0}^{m} \binom{n-k}{m-k}=\binom{n+1}{m}$$ $$n\geq m\geq 1$$ I tried to do this via induction and failed. there has to be another way of doing this. We could either ...
4
votes
2answers
1k views

Induction proof concerning a sum of binomial coefficients: $\sum_{j=m}^n\binom{j}{m}=\binom{n+1}{m+1}$ [duplicate]

I'm looking for a proof of this identity but where j=m not j=0 http://www.proofwiki.org/wiki/Sum_of_Binomial_Coefficients_over_Upper_Index $$\sum_{j=m}^n\binom{j}{m}=\binom{n+1}{m+1}$$
3
votes
2answers
690 views

Sum of combinations with varying $n$ [duplicate]

What is the sum of number of ways of choosing $n$ elements from $(n+r)$ elements where $r$ is fixed and $n$ varies from $1$ to $m$ ? Can this be reduced to a formula ? $$ \sum ^m _{n=1} \binom{n + r}...
2
votes
2answers
153 views

Prove $\sum\limits_{i=0}^{n}\binom{n+i}{i}=\binom{2n+1}{n+1}$ [duplicate]

I'm trying to prove this algebraically: $$\sum\limits_{i=0}^{n}\dbinom{n+i}{i}=\dbinom{2n+1}{n+1}$$ Unfortunately I've been stuck for quite a while. Here's what I've tried so far: Turning $\dbinom{n+...
2
votes
1answer
608 views

Combinatorial proof for $\sum_{k = 0}^n \binom {r+k} k = \binom {r + n + 1} n$ [duplicate]

I'm trying to figure out a combinatorial proof for: $$\displaystyle \sum_{k \mathop = 0}^n \binom {r+k} k = \binom {r + n + 1} n$$ I've tried the committee counting thing, but that didn't work.
3
votes
1answer
211 views

How to simplify $\sum_{i=1}^{k}\binom{n + i - 1}{i}$? [duplicate]

How to simplify $\sum_{i=1}^{k}\binom{n + i - 1}{i}$? I tried reducing the sum to $\binom{n}{1}, \binom{n}{2}, \binom{n}{3}$ and so on but couldn't get a pattern.
1
vote
2answers
101 views

Combinatoric Proof of $\sum_0^n\binom{k-1+i}{k-1} = \binom{n+k}{k}$ [duplicate]

$\sum_0^n\binom{k-1+i}{k-1} = \binom{n+k}{k}$ I think there are two different ways to prove the above identity: one is algebraic and the other one is combinatoric. I have seen there's some ways to ...
0
votes
1answer
96 views

Prove $\sum_{k=m}^n {k \choose m} = {n+1 \choose m+1}$ [duplicate]

I am trying to determine whether $\sum_{k=m}^n {k \choose m} = {n+1 \choose m+1}$, so far I am assuming that this is a false statement, but was wondering if there was a proof indicating this is a true ...
0
votes
1answer
249 views

Sum of Number of non-decreasing sequences [duplicate]

I know that the number of non-decreasing sequences of length $n$ and numbers in the sequence lying in the range $[l,r]$ is given by $$\binom{n+r-l}{n}$$ What is the formula to find the $$\sum_{n=1}^{...
1
vote
1answer
90 views

How can you show that $\binom {n}{7}=\sum_{k=7}^n \binom {k-1} {6}$? [duplicate]

How can you show that $\binom {n}{7}=\sum_{k=7}^n \binom {k-1} {6}$? This counts the number of subsets from $\{1,2,3,\dots,n\}$ having size $7$. To me, the summation part counts subsets of size $6$. ...
0
votes
1answer
71 views

Solve this combination with a summation. Edited and maybe Solved [duplicate]

I have been quite stuck on this problem and with the help of others, I may have solved it. This is what I have to prove. $$\binom{N}{n+1}=\sum^{N-1}_{k=n} \binom{k}{n}.$$ So far I have this $${N ...

15 30 50 per page