# 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:

1. Turning $\dbinom{n+i}{i}$ to $\dbinom{n+i}{n}$
2. Turning $\dbinom{2n+1}{n+1}$ to $\dbinom{2n+1}{n}$
3. Converting binomial coefficients to factorial form and seeing if anything can be cancelled.
4. Writing the sum out by hand to see if there's anything that could be cancelled.

I end up being stuck in each of these ways, though. Any ideas? Is there an identity that can help me?

## marked as duplicate by Jack D'Aurizio, Mark Viola, Lucian, user147263, vonbrandJul 24 '15 at 0:32

• I'd recommend using induction to prove the result, although I'm sure it could be done another way. – Raj Jul 23 '15 at 20:05
• Oh, I forgot to mentioned that I tried induction too (a classmate gave me that hint). I got stuck trying to move the induction hypothesis from $\sum\limits_{i=0}^{k}\dbinom{k+i}{i} = \dbinom{2k+1}{2k+1}$ to $\sum\limits_{i=0}^{k+1}\dbinom{k+i+1}{i} = \dbinom{2k+3}{k+2}$ Specifically the $k+i+1$ part--had no idea how to change that. – jsluong Jul 23 '15 at 20:24

Hint:

Use $$\binom{n+1+i}{i} - \binom{n+i}{i-1} = \binom{n+i}{i}$$

• Hey, thanks for this! This is the recursive formula rewritten, right? I'm trying to use it to see if I could solve this problem with another approach but, er, stuck again. Can I get another hint? – jsluong Jul 23 '15 at 20:40
• Yep, the same recursion you have in your answer, only with different values $k=i$ and $n \mapsto 1 + n + i$ – johannesvalks Jul 23 '15 at 20:42
• Should be $\binom{n+i}{i+1}$ on the RHS. – xivaxy Jul 23 '15 at 20:47
• @Dr.MV - indead, I have corrected it. – johannesvalks Jul 23 '15 at 21:37

Oh, hey! I just figured it out. Funny how simply posting the question allows you re-evaluate the problem differently...

So on Wikipedia apparently this is a thing (the recursive formula for computing the value of binomial coefficients): $$\dbinom{n}{k} = \dbinom{n-1}{k-1} + \dbinom{n-1}{k}$$

On the RHS of the equation we have (let's call this equation 1):

$$\dbinom{2n+1}{n+1} = \dbinom{2n}{n} + \dbinom{2n-1}{n} + \dbinom{2n-2}{n} + \cdots + \dbinom{n+1}{n} + \dbinom{2n-(n-1)}{n+1}$$ The last term $\dbinom{2n-(n-1)}{n+1}$ simplifies to $\dbinom{n+1}{n+1}$ or just 1.

Meanwhile on the LHS we have $\sum\limits_{i=0}^{n}\dbinom{n+i}{i}$ which is also $\sum\limits_{i=0}^{n}\dbinom{n+i}{n}$ because $\dbinom{n}{k} = \dbinom{n}{n-k}$.

Written out that is (let's call this equation 2): $$\sum\limits_{i=0}^{n}\dbinom{n+i}{n} = \dbinom{n}{n} + \dbinom{n+1}{n} + \dbinom{n+2}{n} + \cdots + \dbinom{2n}{n}$$

The first term $\dbinom{n}{n}$ simplifies to 1.

Hey, look at that.

In each written out sum there's a term in equation 1 and an equivalent in equation 2. And in each sum there's $n$ terms, so equation 1 definitely equals equation 2. I mean, the order of terms is flipped, but whatever. Yay!

• Cool that you found it! – johannesvalks Jul 23 '15 at 20:35
• Okay... so tell me what I should do. – jsluong Jul 23 '15 at 21:40
• @Dr.MV This is the subject of some debate.. The OP didn't know the answer beforehand, but figured it out an hour after posting the question. I think this is totally fine. – André 3000 Jul 23 '15 at 22:11
• @SpamIAm The answer was posted roughly the same time that the question was identified as a duplicate. So, given this question is indeed a duplicate, how does one justify the action? – Mark Viola Jul 23 '15 at 22:34
• Oh, well, I LaTeX my homework so I needed to type up the solution anyway. I figured other people could potentially benefit from the solution. This is a new account. I really am not trying to farm rep. – jsluong Jul 23 '15 at 23:22