combinatorics - Prove $sumlimits_{i=0}^{n}binom{n+i}{i}=binom{2n+1}{n+1}$

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?

Answer

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!