Démontrer une propriété de divisibilité par récurrence
Créez un compte gratuit pour suivre votre avancement et reprendre où vous avez laissé.
Créer un compteMéthode
Pour démontrer qu'une propriété du type « pour tout entier $n \geqslant n_0$, l'entier $E(n)$ est divisible par $p$ », on rédige une démonstration par récurrence sur $n$.
- Étape 1 — Initialisation : vérifier que $p \mid E(n_0)$ pour le premier rang $n_0$.
- Étape 2 — Hérédité : supposer la propriété vraie au rang $n$, c'est-à-dire écrire $E(n) = pk$ avec $k$ entier (hypothèse de récurrence). Calculer $E(n+1) - E(n)$ ou exprimer $E(n+1)$ en fonction de $E(n)$, puis montrer que $p$ divise $E(n+1)$.
- Étape 3 — Conclusion : par initialisation et hérédité, la propriété est vraie pour tout $n \geqslant n_0$.
Divisibilité d'une expression polynomiale
Démontrer que pour tout entier naturel $n$, $E(n) = 4^n + 2$ est divisible par $3$.
Étape 1 — Initialisation : pour $n = 0$, $E(0) = 4^0 + 2 = 1 + 2 = 3$. Donc $3 \mid E(0)$.
Étape 2 — Hérédité : soit $n \geqslant 0$. On suppose qu'il existe un entier $k$ tel que $E(n) = 4^n + 2 = 3k$ (hypothèse de récurrence).
On exprime $E(n+1)$ :
D'après l'hypothèse, $4^n = 3k - 2$. Donc :
Comme $4k - 2$ est entier, $\color{red}{3 \mid E(n+1)}\color{black}$.
Étape 3 — Conclusion : par récurrence, pour tout entier naturel $n$, $\mathbf{3 \mid 4^n + 2}$.
Divisibilité d'une différence de puissances
Démontrer que pour tout entier naturel $n$, $E(n) = 7^n - 1$ est divisible par $6$.
Étape 1 — Initialisation : pour $n = 0$, $E(0) = 7^0 - 1 = 0$, et $6 \mid 0$.
Étape 2 — Hérédité : soit $n \geqslant 0$. On suppose qu'il existe un entier $k$ tel que $7^n - 1 = 6k$, soit $7^n = 6k + 1$.
On calcule :
D'où :
Comme $7k + 1$ est entier, $6 \mid E(n+1)$.
Étape 3 — Conclusion : par récurrence, pour tout entier naturel $n$, $\mathbf{6 \mid 7^n - 1}$.
Remarque
L'hérédité repose presque toujours sur le même schéma :
- isoler le terme dominant de $E(n+1)$ (souvent une puissance ou une factorielle) ;
- y substituer son expression issue de l'hypothèse de récurrence ;
- factoriser par $p$ pour conclure.
Une démonstration par disjonction modulo $p$ (voir la fiche méthode dédiée) est souvent plus directe quand l'expression est polynomiale en $n$. La récurrence est en revanche incontournable dès que l'expression contient une puissance $a^n$ ou une factorielle $n!$.
Attention
Toujours bien rédiger l'hypothèse de récurrence : « il existe un entier $k$ tel que $E(n) = pk$ ». Écrire seulement « $p \mid E(n)$ » sans introduire le quotient $k$ rend les calculs d'hérédité illisibles.
Ne jamais omettre l'initialisation, même si elle paraît évidente : une récurrence sans initialisation n'a aucune valeur démonstrative.