Direkter Beweis
n^3 - n = (n - 1)·n·(n + 1)
Von 3 aufeinander folgenden Zahlen ist immer mind. eine durch 2 teilbar und genau eine durch drei teilbar. Damit ist das Produkt durch 2 und durch 3 und damit immer durch 6 teilbar.
Beweis über vollständige induktion
Induktionsanfang n = 1
1^3 - 1 = 0 --> 0 ist ohne Rest durch 6 teilbar
Induktionsschritt n --> n + 1
(n + 1)^3 - (n + 1) ist durch 6 teilbar
(n^3 + 3·n^2 + 3·n + 1) - (n + 1) ist durch 6 teilbar
n^3 + 3·n^2 + 2·n ist durch 6 teilbar
(n^3 - n) + (3·n^2 + 3·n)
(n^3 - n) + 3·(n^2 + n)
Der erste Summand ist laut Iduktionsannahme durch 3 teilbar. Der zweite Summand enthält den Faktor 3 und ist daher ebenso durch 3 teilbar.
Damit ist für alle n gezeigt das n^3 - n durch 3 teilbar ist.