Looking for combinatorial proof for identity $n! = 1 \cdot 1! + 2\cdot 2! … (n-1) \cdot (n-1)! + 1$ [duplicate]

I am looking for a combinatorial proof of the following identity

$$n! = 1 + \sum_{i=1}^{n-1} {i \cdot i!}$$

marked as duplicate by ShreevatsaR, lhf, Namaste, Davide Giraudo, leonbloyApr 16 '14 at 12:17

• What do you mean by "combinatorial"? Can't you use induction? – 7raiden7 Apr 16 '14 at 10:50
• @7raiden7 I am particularly looking for a proof using bijection. But feel free to add your proof/comments! – mozaic Apr 16 '14 at 10:55
• – TheOscillator Apr 16 '14 at 11:27
• This is just a simple telescoping sum. $$1 + \sum_{k=1}^{n-1} k\cdot k!=1 + \sum_{k=1}^{n-1} ((k+1)-1)\cdot k!=1 + \sum_{k=1}^{n-1} (k+1)\cdot k!- \sum_{k=1}^{n-1} k!$$ $$=1 + \sum_{k=1}^{n-1} (k+1)!- \sum_{k=1}^{n-1} k!$$ $$=1 - \sum_{k=1}^{n-1} k!+ \sum_{k=1}^{n-1} (k+1)!$$ $$=1-1!+2!-2!+3!-3!+...-(n-2)!+(n-1)!-(n-1)!+n!$$ $$=0+0+0+...+n!=n!$$ see math.unb.ca/apics.papers/90/90.html – John Joy Apr 16 '14 at 14:00
• There is a truly hairraising proof using the generating function $\sum_{n \ge 0} n! z^n$... – vonbrand Apr 16 '14 at 14:42

$$1+\sum_{i=1}^{n-1}i.i!=1+\sum_{i=1}^{n-1}\left(i+1\right).i!-\sum_{i=1}^{n-1}i!=1+\sum_{i=2}^{n}i!-\sum_{i=1}^{n-1}i!=n!$$

Consider permutations $w \in S_n$ and partition them according to the largest $k$ such that $w(k) \neq k$. (Note there is one permutation that is excluded from this partition, namely the identity permutation.) Let $A_k$ denote the above set of permutations. Then $w \in A_k$ is determined by choosing the value of $w(k)$, which must be one of the numbers $1, 2, \dots, k-1$. Then there are $(k-1)!$ ways to assign values of $w(1), w(2), \dots, w(k-1)$. Since there are $n!$ permutations in $S_n$, it follows that $$n! = 1 + \sum_{k=2}^n (k-1) \cdot (k-1)!.$$ Your identity follows by reindexing, setting $i = k - 1$. (Note that $A_1$ is empty.)

Let's proceed by induction:

Base case: $n=0$: $0!=1+0=1\Rightarrow$ True;

Let's suppose for $n$ and prove it for $n+1$: $$(n+1)!=(n+1)n!=(n+1)(1+\sum_{i=1}^{n-1} ii!)=1+\sum_{i=1}^{n-1} ii!+n(1+\sum_{i=1}^{n-1} ii!)=1+\sum_{i=1}^{n-1} ii!+nn!=1+\sum_{i=1}^{n} ii!$$

Let $T_n=n!$ be the total number of permutations. Consider some particular permutation $P_0$, and let $S_{n,k}$ be the number of permutations that have a common prefix with $P_0$ of length $k$.

Then $$T_n = S_{n,0} + S_{n,1} + \cdots + S_{n,n-1} + S_{n,n-1} + S_{n,n}=\\= (n-1)(n-1)! + (n-2)(n-2)!+\cdots +1$$

That is, $S_{n,k}= (n-k-1) (n-k-1)!$ if $k<n$, and $S_{n,n}=1$. Hence

$$n!=1 + \sum_{k=0}^{n-1} (n-k-1) (n-k-1)!=1 + \sum_{j=0}^{n-1} j\, j!$$