Problem proving $ P_{r}^{r} + P_{r}^{r+1} + ... + P_{r}^{2r} = P_{r}^{2r+1} $

Question

Show that $$ P_{r}^{r} + P_{r}^{r+1} + ... + P_{r}^{2r} = P_{r}^{2r+1} $$ where r is a nonnegative integer.

This is what I've come up with so far but I'm not sure how to continue. I know I need to prove the following.

$$ r! + (r+1)!+ \frac{(r+2)!}{2!} + ... + \frac{(2r)!}{r!} = \frac{(2r+1)!}{(r+1)!} $$

EDIT: Applying Pascal Rule,

$$\binom{2r+1}{r+1} = \binom{2r}{r} + \binom{2r}{r+1} = \binom{2r}{r} + \binom{2r-1}{r} +\binom{2r-1}{r+1}$$

Still not clear how it will merge, pls explain. Thanks!

Answer 1

Hint: you need to show $$ \binom{r}{0}+\binom{r+1}{1}+\cdots+\binom{2r}{r}=\binom{2r+1}{r+1}.\tag{*} $$ This form can be proved by successive applications of the Pascal's rule to the RHS.

---

Edit: (*) can be obtained by dividing both sides of $$ r!+(r+1)!+\frac{(r+2)!}{2!}+\cdots+\frac{(2r)!}{r!}=\frac{(2r+1)!}{(r+1)!} $$ by $r!$.

Answer 2

Have you tried a combinatorial argument, that should slay the problem with ease. A sketch of one made up on the fly: From (2r+1) objects, r objects are selected and arranged in a row. This can be done by choosing only from r of the original (2r+1) objects, then permuting them, or choosing from (r+1) objects and permuting them etc. Adding these various permutations will naturally give the required sum as they are mutually exclusive.

Or would you prefer a more algebraic proof? An algebraic proof would rely upon division of the sum you gave by a factor of r!

$$ r! + (r+1)!+ \frac{(r+2)!}{2!} + ... + \frac{(2r)!}{r!} = \frac{(2r+1)!}{(r+1)!} $$

This reduces the above sum to simply a sum of binomial coefficients.

Edit:

Well, going from your own working, we simply iteratively apply Pascal's rule to the remaining binomial coefficient that has the (r+1) in the lower half. Can you see that by doing so, you effectively set up a series of binomial coefficients?

Truncating it to the last application, you should get:

$\binom{2r+1}{r+1}=\binom{2r}{r}+\binom{2r-1}{r}+....+\binom{r+1}{r}+\binom{r+1}{r+1}$.

Which is the required result.

Answer 3

Hint: Divide both sides of your desired identity by $r!$ and convert to binomial coefficients to get $$ \sum_{t=0}^r \binom{t+r}{r} = \binom{2r+1}{r+1}. $$ This is a special case of the more general identity $$ \sum_{t=0}^n \binom{t+r}{r} = \binom{n+r+1}{r+1}, $$ which has a simple combinatorial proof: the right-hand side counts the number of subsets of $[n+r+1]$ of size $r+1$, and the left-hand side counts them by their maximal element $t+r+1$.