1. Soit n∈N. On note Pn la proposition « n3−n est un multiple de 3. »
2. Pour n=0, n3−n=03−0=0=3×0, donc n3−n est un multiple de 3.
La proposition P0 est donc vraie.
3. On considère un entier naturel k pour lequel Pk est vraie. Autrement dit, on suppose que k3−k est un multiple de 3. Il existe donc un entier relatif q tel que k3−k=3q. On veut démontrer que Pk+1 est vraie, autrement dit, que (k+1)3−(k+1) est un multiple de 3. On cherche donc q′∈Z tel que (k+1)3−(k+1)=3q′.
4. (k+1)3−(k+1)
=(k+1)(k+1)2−k−1
=(k+1)(k2+2k+1)−k−1
=k3+2k2+k+k2+2k+1−k−1
=k3−k+3k2+3k
Or, par hypothèse de récurrence, k3−k=3q.
Ainsi, (k+1)3−(k+1)=3q+3k2+3k=3(q+k2+k).
On note q′=q+k2+k. q′ est bien un entier en tant que somme d'entiers. On a ainsi trouvé q′∈Z tel que (k+1)3−(k+1)=3q′ donc Pk+1 est vraie.
5. Ainsi, P0 est vraie et, pour tout entier k tel que Pk est vraie, alors Pk+1 est vraie aussi. Par le principe de récurrence, on en déduit que, pour tout n∈N, Pn est vraie.
Donc, pour tout n∈N, n3−n est un multiple de 3.