2
$\begingroup$

This question already has an answer here:

I am looking for a combinatorial proof of the following identity

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

I appreciate your help!

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ What do you mean by "combinatorial"? Can't you use induction? $\endgroup$ – 7raiden7 Apr 16 '14 at 10:50
  • $\begingroup$ @7raiden7 I am particularly looking for a proof using bijection. But feel free to add your proof/comments! $\endgroup$ – mozaic Apr 16 '14 at 10:55
  • 2
    $\begingroup$ See math.stackexchange.com/questions/598238/… $\endgroup$ – TheOscillator Apr 16 '14 at 11:27
  • $\begingroup$ 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 $\endgroup$ – John Joy Apr 16 '14 at 14:00
  • $\begingroup$ There is a truly hairraising proof using the generating function $\sum_{n \ge 0} n! z^n$... $\endgroup$ – vonbrand Apr 16 '14 at 14:42
3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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