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, vonbrand Jul 24 '15 at 0:32

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ I'd recommend using induction to prove the result, although I'm sure it could be done another way. $\endgroup$ – Raj Jul 23 '15 at 20:05
  • $\begingroup$ 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. $\endgroup$ – jsluong Jul 23 '15 at 20:24


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

  • $\begingroup$ 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? $\endgroup$ – jsluong Jul 23 '15 at 20:40
  • $\begingroup$ Yep, the same recursion you have in your answer, only with different values $k=i$ and $n \mapsto 1 + n + i$ $\endgroup$ – johannesvalks Jul 23 '15 at 20:42
  • $\begingroup$ Should be $\binom{n+i}{i+1}$ on the RHS. $\endgroup$ – xivaxy Jul 23 '15 at 20:47
  • $\begingroup$ @Dr.MV - indead, I have corrected it. $\endgroup$ – 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!

  • $\begingroup$ Cool that you found it! $\endgroup$ – johannesvalks Jul 23 '15 at 20:35
  • $\begingroup$ Okay... so tell me what I should do. $\endgroup$ – jsluong Jul 23 '15 at 21:40
  • $\begingroup$ @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. $\endgroup$ – André 3000 Jul 23 '15 at 22:11
  • $\begingroup$ @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? $\endgroup$ – Mark Viola Jul 23 '15 at 22:34
  • 1
    $\begingroup$ 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. $\endgroup$ – jsluong Jul 23 '15 at 23:22

Not the answer you're looking for? Browse other questions tagged or ask your own question.