7
$\begingroup$

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$.

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

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!. $$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.