2
$\begingroup$

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?

$\endgroup$

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
4
$\begingroup$

Hint:

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

$\endgroup$
  • $\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
2
$\begingroup$

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!

$\endgroup$
  • $\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.