1. Zeige zuerst mit vollständiger Induktion, dass
$$ \sum_{k=0}^n k \cdot k! = (n+1)! - 1 $$
2. Wir zeigen nun mit vollst. Ind. dass sich die Zahlen \( m \in \{ 0,...,(n+1)!-1 \} \) eindeutig als
$$ m =\sum_{k=0}^n a_k \cdot k!,\quad 0\le a_k \le k $$
darstellen lassen:
Induktionsstart n=0: Behauptung klar, denn die Zahl in \( \{ 0,...,(n+1)!-1 \} = \{ 0 \} \) lässt sich eindeutig als $$ 0 = \sum_{k=0}^0 a_k \cdot k! = a_k \cdot 0! $$
mit \( a_0 = 0 \) darstellen.
Induktionsschritt \( n \to n+1 \): Nach Induktionsvoraussetzung lassen sich die Zahlen \( m \in \{ 0,...,(n+1)!-1 \} \) eindeutig in der Form $$ m =\sum_{k=0}^n a_k \cdot k!,\quad 0\le a_k \le k $$ darstellen. Da außerdem \( (n+1)! > m \) muss für eine Darstellung $$ m =\sum_{k=0}^{n+1} a_k \cdot k!,\quad 0\le a_k \le k $$ schon \( a_{n+1} = 0 \) gewählt werden, die Darstellung bleibt also eindeutig.
Wegen 1. hat keine Zahl \( m\in \{ 0,...,(n+2)!-1 \} \setminus \{ 0,...,(n+1)!-1 \} = \{ (n+1)!,...,(n+2)!-1 \} \) eine Darstellung der Form $$ m =\sum_{k=0}^n a_k \cdot k!,\quad 0\le a_k \le k $$ da diese stets kleiner gleich \( (n+1)! - 1 \) sind, aber \( m > (n+1)! - 1 \).
Es bleibt nun zu zeigen, dass alle Zahlen \( m \in \{ (n+1)!,...,(n+2)!-1 \} \) eine eindeutige Darstellung der Form $$ m =\sum_{k=0}^{n+1} a_k \cdot k!,\quad 0\le a_k \le k $$ besitzen. Schauen wir uns diese Menge mal genauer an:
$$ \{ (n+1)!,...,(n+2)!-1 \} = \left\{ \begin{matrix} (n+1)!, ~(n+1)! + 1 , ~...,~ (n+1)! + ((n+1)! - 1), \\ 2(n+1)!, ~2(n+1)! + 1 , ~..., ~2(n+1)! + ((n+1)! - 1),\\3(n+1)!, ~3(n+1)! + 1 , ~..., ~3(n+1)! + ((n+1)! - 1),\\\vdots\\ (n+1)(n+1)!, ~(n+1)(n+1)! + 1 ,~ ..., ~\underbrace{(n+1)(n+1)! + ((n+1)! - 1)}_{=(n+2)!-1} \end{matrix} \right\} $$
Das \( m \) kann also eindeutig in der Form \( m = a_{n+1} (n+1)! + a \) mit \( 1 \le a_{n+1} \le n+1 \) und \( a < (n+1)! \) dargestellt werden. Wir haben bereits gezeigt, dass \( a \) eine eindeutige Darstellung $$ a =\sum_{k=0}^n a_k \cdot k!,\quad 0\le a_k \le k $$ besitzt und somit auch \( m \): $$ m = \sum_{k=0}^{n+1} a_k \cdot k!,\quad 0\le a_k \le k $$
