Pour aller plus loin : le raisonnement par récurrence en arithmétique

I- Introduction

Le raisonnement par récurrence est utilisé pour montrer des résultats faisant intervenir une variable entière de l'ensemble $\mathbb{N}$ ou d'une partie de cet ensemble, comme par exemple $\mathbb{N}^{}$, $\mathbb{N}^{}-\lbrace 1,2 \rbrace$, etc.

Cette démonstration s'effectue en trois étapes :

L'étape initialisation : Montrer que le résultat est vrai pour le tout premier rang (en général le premier rang est 0, mais il se peut que le premier rang soit 1, 2 ou autre, cela dépend du résultat à démontrer).

L'étape hérédité : Montrer que le résultat est héréditaire, c'est-à-dire montrer que le résultat peut être "transmis" d'un rang fixé quelconque $k$ au rang suivant $k+1$.

La conclusion.

Pour expliquer ce principe assez intuitivement, prenons les deux exemples suivants :

Exemple 1 : La file de dominos

Si l'on pousse le premier domino de la file (Initialisation).
Et si les dominos sont posés l'un après l'autre d'une manière à ce que la chute d'un domino entraîne la chute de son suivant (Hérédité). Sauf s'il y a un trou...
Alors : Tous les dominos de la file tombent. (la conclusion)

Exemple 2 : L'échelle
Si on sait monter le premier barreau de l'échelle (Initialisation).
Et si l'on sait toujours passer d'un barreau au barreau qui le suit (Hérédité).
Alors : On peut monter l'échelle. (la conclusion)

II. Le principe de la démonstration par récurrence

Cette démonstration s’applique lorsque l’on cherche à démontrer qu’une propriété dépendant d’un entier naturel $n$ est vraie pour tout entier $n \geq n_0$, $n_0$ étant un entier naturel donné.

On procède en trois étapes :

Étape n°1 : Initialisation

On montre que la propriété est vraie pour $n = n_0$ (au rang $n_0$).

Étape n°2 : Hérédité

On démontre que :
Si la propriété est supposée vraie pour un entier naturel $n$ supérieur ou égal à $n_0$ (ceci s’appelle l’hypothèse de récurrence), alors elle est vraie pour l’entier suivant $n + 1$.
On veut donc montrer que, si elle est vraie à un rang $n$, elle est aussi vraie au rang suivant $n + 1$.

Étape n°3 : Conclusion

On combine les étapes 1 et 2 :
La propriété est vraie au rang $n_0$ (étape n°1) et elle est héréditaire à partir du rang $n_0$ (étape n°2), donc le principe de récurrence permet de conclure que la propriété est vraie pour n’importe quel entier naturel $n \geq n_0$.

III. Exemples rédigés

$1.$ Montrer une divisibilité par récurrence

Énoncé :

Montrer que pour tout entier naturel $n$, 3 divise $4^n - 1$.

On va utiliser une démonstration par récurrence.

On note $P(n)$ la propriété : "3 divise $4^n-1$".

Pour $n = 0$ : $4^0 - 1 = 1 - 1 = 0$ est divisible par 3, donc $P(0)$ est vraie.

On suppose $P(n)$ vraie, ce qui se traduit par : il existe un entier naturel $k$ tel que $4^n - 1 = 3k$, donc $4^n = 3k + 1$.

Au rang $n + 1$ :
$4^{n+1} - 1 = 4 \times 4^n - 1 = 4 \times (3k + 1) - 1 = 4 \times 3k + 4 \times 1 - 1 = 4 \times 3k + 3 = 3(4k + 1)$.

Conclusion : D'après le principe de récurrence, pour tout entier naturel $n$, 3 divise $4^n - 1$.

$2.$ Déterminer le chiffre des unités : 4 méthodes pour un même énoncé

Énoncé
Un entier naturel $n$ étant donné, quel est le chiffre des unités de l'écriture décimale de $n^5-n$ ?

Un entier naturel $n$ étant donné, quel est le chiffre des unités de l'écriture décimale de $n^5 - n$ ?

On remarque, en effectuant plusieurs essais, que $n^5 - n$ se termine par zéro. On va essayer de le démontrer.

On peut écrire $n^5 - n = n(n - 1)(n + 1)(n^2 + 1)$. Cette écriture appelle à deux remarques :

$\circ$ le produit est pair car $n$ et $n + 1$ sont deux entiers consécutifs.

$\circ$ de plus, les naturels 2 et 5 sont premiers entre eux.

Donc, pour démontrer que $n^5 - n$ est divisible par 10, on doit démontrer uniquement qu'il est divisible par 5.

On va se servir de quatre méthodes différentes.

1^ère Méthode : par récurrence

Pour $n = 0$ : vraie

Supposons que la relation soit vraie au rang $n$, soit : $n^5 - n = 5k$ avec $k \in \mathbb{N}$.

Démontrons qu'elle est vraie au rang $n + 1$, soit $(n + 1)^5 - (n + 1)$ est un multiple de 5.

On a :
$(n + 1)^5 - (n + 1) = n^5 + 5n^4 + 10n^3 + 10n^2 + 5n + 1 - n - 1$
$(n + 1)^5 - (n + 1) = n^5 - n + 5(n^4 + 2n^3 + 2n^2 + n) = 5k + 5(n^4 + 2n^3 + 2n^2 + n)$.

Cette dernière expression montre que la relation est vraie au rang $n+1$.

Le principe de récurrence permet de conclure.

2^ème méthode : les congruences

On étudie les valeurs possibles pour le reste dans la division euclidienne de $n$ par 5.

Si $n \equiv 0 , \text{(mod 5)}$, alors $n^5 - n \equiv 0 , \text{(mod 5)}$.
Si $n \equiv 1 , \text{(mod 5)}$, alors $n^5 \equiv 1 , \text{(mod 5)}$ donc $n^5 - n \equiv 0 , \text{(mod 5)}$.
Si $n \equiv 2 , \text{(mod 5)}$, alors $n^5 \equiv 2 , \text{(mod 5)}$ donc $n^5 - n \equiv 0 , \text{(mod 5)}$.
Si $n \equiv 3 , \text{(mod 5)}$, alors $n^5 \equiv 3 , \text{(mod 5)}$ donc $n^5 - n \equiv 0 , \text{(mod 5)}$.
Si $n \equiv 4 , \text{(mod 5)}$, alors $n^5 \equiv 4 , \text{(mod 5)}$ donc $n^5 - n \equiv 0 , \text{(mod 5)}$.

La conclusion est immédiate.

3ème méthode : factorisation de $n^5 - n$

$n^5 - n = n(n - 1)(n + 1)(n^2 + 1)$

Si $n \equiv 0 \, [5]$ alors $n^5 - n \equiv 0 \, [5]$.

Si $n \equiv 1 \, [5]$ alors $n-1 \equiv 0 \, [5]$, alors $n^5 - n \equiv 0 \, [5]$.

Si $n \equiv 2$ ou $n \equiv 3 \, [5]$, alors $n^2 + 1 \equiv 0 \, [5]$ et $n^5 - n \equiv 0 \, [5]$.

Si $n \equiv 4 \, [5]$, alors $n+1 \equiv 0 \, [5]$ et $n^5 - n \equiv 0 \, [5]$.

La conclusion en découle.

4^ème méthode : on utilise le petit théorème de Fermat

$n^5 - n = n(n^4 - 1)$

Si $n \equiv 0 \, [5]$ alors $n^5 - n \equiv 0 \, [5]$.

Si $n$ n'est pas congru à zéro (modulo 5), comme 5 est premier, $n$ est premier avec 5. D'après le petit théorème de Fermat, $n^5 - n \equiv 0 \, [5]$.

On a donc $n^5 - n \equiv 0 \, [5]$.