8

Raisonnement par récurrence

Le raisonnement par récurrence ne peut s'utiliser que lorsque l'on cherche à démontrer qu'une proposition est vraie pour tout entier naturel n supérieur ou égal à un entier naturel n_0.

En terminale, on a généralement n_0=0 ou n_0=1.

Soit n_0 \in \N. On considère la proposition \mathcal{P}_n définie pour tout entier naturel n \geqslant n_{0}.
Si les deux conditions suivantes sont vérifiées :
1. \mathcal{P}_n est vraie pour l'entier n_0 ;
2. pour tout entier naturel k \geqslant n_{0}, « \mathcal{P}_k est vraie. » implique « \mathcal{P}_{k+1} est vraie. » ; alors on peut conclure que, pour tout n \geqslant n_{0}, la proposition \mathcal{P}_n est vraie.

Les étapes du raisonnement par récurrence sont :

• initialisation ;
• hypothèse de récurrence ;
• hérédité ;
• conclusion.

1. Soit n \in \N. On note \mathcal{P}_n la proposition « n^3 - n est un multiple de 3. »

2. Pour n = 0, n^{3}-n=0^{3}-0=0=3 \times 0, donc n^3 - n est un multiple de 3.
La proposition \mathcal{P}_0 est donc vraie.

3. On considère un entier naturel k pour lequel \mathcal{P}_k est vraie. Autrement dit, on suppose que k^3 - k est un multiple de 3. Il existe donc un entier relatif q tel que k^3 - k = 3q. On veut démontrer que \mathrm{P}_{k+1} est vraie, autrement dit, que (k+1)^{3}-(k+1) est un multiple de 3. On cherche donc q' \in \Z tel que (k+1)^{3}-(k+1)=3 q^{\prime}.

4. (k+1)^{3}-(k+1) =(k+1)(k+1)^{2}-k-1
=(k+1)\left(k^{2}+2 k+1\right)-k-1
=k^{3}+2 k^{2}+k+k^{2}+2 k+1-k-1
=k^{3}-k+3 k^{2}+3 k

Or, par hypothèse de récurrence, k^3 - k = 3q.
Ainsi, (k+1)^{3}-(k+1)=3 q+3 k^{2}+3 k=3\left(q+k^{2}+k\right).
On note q' = q + k^2 + k. q' est bien un entier en tant que somme d'entiers. On a ainsi trouvé q' \in \Z tel que (k+1)^{3}-(k+1)=3 q^{\prime} donc \mathcal{P}_{k+1} est vraie.

5. Ainsi, \mathcal{P}_0 est vraie et, pour tout entier k tel que \mathcal{P}_k est vraie, alors \mathcal{P}_{k+1} est vraie aussi. Par le principe de récurrence, on en déduit que, pour tout n \in \N, \mathcal{P}_n est vraie.
Donc, pour tout n \in \N, n^3 - n est un multiple de 3.

1. On nomme la proposition que l'on souhaite démontrer.

2. Cette étape est l'initialisation : on vérifie que \mathcal{P}_0 est vraie en remplaçant n par 0.

3. On énonce l'hypothèse de récurrence dont on se servira dans la démonstration de l'hérédité.

4. On démontre l'hérédité de la proposition. La plupart du temps, c'est la partie la plus technique du raisonnement par récurrence. L'hypothèse de récurrence doit être utilisée dans l'hérédité. Dans cet exemple, la principale difficulté consiste à traduire l'énoncé « multiple de 3 » en une proposition mathématique. Cela permet de savoir qu'une factorisation par 3 est nécessaire.

5. La conclusion est une étape importante du raisonnement mais rarement difficile à rédiger puisqu'elle reprend notamment l'énoncé de départ.