# Prove that $\frac{(n + 1)!}{((n + 1) - r)!} = r \sum_{i=r - 1}^{n} \frac{i!}{(i - (r - 1))!}$

I Need Help proving That

$$\frac{(n + 1)!}{(n - r + 1)!} = r \cdot \sum_{i=r - 1}^{n} \frac{i!}{(i - r + 1)!}$$

Or in terms of Combinatorics functions:
$$P_{r}^{n+1} = r \cdot \sum_{i = r-1}^{n} {P_{r-1}^{i}}$$

Where $$P_{r}^{n}$$ is $$r! \cdot {n \choose r}$$

What I've tried:
Creating a problem that the solution is the Left-hand side, and then solving it with another idea that'll have the same equation as the Right-hand side, the Problem Is obvious: How to take $$r$$ people out of $$n+1$$ and order then, But I couldn't find the idea that'll lead to the right-hand side of the equation, maybe a better problem can be suggested by someone that will make getting to the right-hand side easier to get to will help?

I also expanded the right-hand side to:
$$r \cdot ({\frac{(r-1)!}{0!} + \frac{r!}{1!} + \frac{(r+1)!}{2!} + \frac{(r+2)!}{3!} + \cdots + \frac{n!}{(n-r+1)!}})$$

But I couldn't get anything further because when I try to simplify the fractions and have a common denominator, the equations won't get any simpler and the fraction will appear in the numerator.

• Hello and welcome to Math.SE. Please take a look at How to ask a good question. and edit your question, since your question does not meet the standards on Math.SE. The biggest problems are: there is no context, it is not clear why you are asking, your work is not visible and your ideas and thoughts are missing. Currently the question is simply "This is my problem. Solve it.". Commented Jul 17 at 14:09
• @KevinDietrich Thank You for notifying me of this issue, I'm editing it. Commented Jul 17 at 14:15

If you divide both sides by $$r!$$, you find:

$$\frac{(n + 1)!}{(n + 1 - r)! r!} = {n + 1 \choose r} = \sum_{i = r - 1}^{n} \frac{i!}{(i - (r - 1))! (r - 1)!} = \sum_{i = r - 1}^{n} {i \choose r - 1}$$

This equation is known as the hockey-stick identity.

On the left-hand side, you find the number of ways to choose $$r$$ out of $$n + 1$$ elements. On the right-hand side, you find the sum of the number of ways to select $$r - 1$$ items out of $$i$$ items, where $$i$$ varies from $$r - 1$$ to $$n$$.

To see why these are equal, imagine all $$n + 1$$ items lying in a row. Starting from item $$r$$, iterate over all possible values for the last item you will choose:

• If you choose $$r$$ as the last item, you have to select all $$r - 1$$ items from the $$r - 1$$ items to the left to get $$r$$ items in total.
• If you choose $$r + 1$$ as the last item, you have to select $$r - 1$$ items from the $$r$$ remaining items to the left to get $$r$$ items in total.
• $$\ldots$$
• If you choose $$n + 1$$ as the last item, you have to select $$r - 1$$ items from the $$n$$ remaining items to the left to get $$r$$ items in total.

Thus, the equation $$\frac{(n + 1)!}{(n - r + 1)!} = r \cdot \sum_{i = r - 1}^{n} \frac{i!}{(i - r + 1)!}$$ indeed holds.

• Hello, Thank you for the effort. I understood perfectly Commented Jul 17 at 15:37

Induction on $$n$$ should work. For $$n=r-1$$ it is true and for the induction step note that $$r!(\binom{n+2}{r}-\binom{n+1}{r})=r!\binom{n+1}{r-1}=r\frac{(n+1)!}{(n-r+2)!}$$.

• the book mentioned that solve them without induction, but yes this works, maybe this will be helpful for someone else, upvoted Commented Jul 17 at 15:39

LHS: Select $$r$$ distinct elements from the set $$S_n = \{0, 1, 2, \ldots, n\}$$, then arrange them in a sequence of length $$r$$, which can be done in $$P(n + 1, r) = \binom{n + 1}{r}r! = \frac{(n + 1)!}{r!(n + 1 - r)!} \cdot r! = \frac{(n + 1)!}{(n + 1 - r)!}$$ ways.
RHS: Consider ordered selections of $$r$$ elements from the set $$S_n$$ whose largest elements is $$i$$. For each such selection, we must select $$r - 1$$ of the $$i$$ elements that are less than $$i$$, then arrange the $$r$$ selected elements in $$r!$$ ways. Notice that $$i$$ must be at least $$r - 1$$ since we must select $$r - 1$$ elements smaller than $$i$$ from $$S_n$$. Moreover, $$i$$ must be at most $$n$$. Hence, the number of sequences of length $$r$$ that we can form from distinct elements of $$S_n$$ is $$\sum_{i = r - 1}^{n} \binom{i}{r - 1} \cdot r! = \sum_{i = r - 1}^{n} \frac{i!}{(r - 1)![i - (r - 1)!]} \cdot r! = \sum_{i = r - 1}^{n} \frac{i!}{(i - r + 1)!} \cdot r = r \sum_{i = r - 1}^{n} \frac{i!}{(i - r + 1)!}$$
Equating the two formulas for the number of sequences of $$r$$ distinct elements of set $$S_n$$ gives the desired result.