# Combinatorial argument for $1+\sum_{r=1}^{r=n} r\cdot r! = (n+1)!$ [duplicate]

Combinatorial argument for $$1+\sum\limits_{r=1}^{r=n} \ r\cdot r! = (n+1)!$$ The algebraic proof is easy as $r=(r+1)-1$.

• It should be $1 + \sum_{r = 1}^{n} r \cdot r! = (n + 1)!$. – N. F. Taussig Apr 6 '16 at 11:28

## 1 Answer

We count the number of permutations of $1,2,3,\ldots, n+1$ in two ways. First, it is equal to $(n+1)!$.

To get the other count, split into cases based on the size of the initial segment agreeing with the identity permutation $[1,2,3,\ldots, n,n+1]$. For example, $[1,2,4,3]$ agrees with $[1,2,3,4]$ for the first $2$ places, whereas $[2,4,1,3]$ agrees with $[1,2,3,4]$ for the first $0$ places. Let the number of initial places agreeing with the identity be $i$. Then the number of permutations agreeing with $[1,2,3,\ldots,n,n+1]$ for the first $i$ places is $(n-i) \cdot (n-i)!$, since there are $(n-i)$ ways to choose the $i+1$th place of the permutation, and $(n-i)!$ ways to rearrange the last $n-i$ places. This holds for $i = 0$ to $i = n$. For $i = n+1$, the formula $(n-i)(n-i)!$ doesn't work; instead the number of ways is just $1$. So we have that the total number of permutations of $1, 2, \ldots, n+1$ is $$1 + \sum_{i=0}^n (n-i)(n-i)! = 1 + \sum_{r=1}^n r \cdot r!.$$

Therefore, $$(n+1)! = 1 + \sum_{r=1}^n r \cdot r!.$$