Récurrence : divisibilité par 3
Énoncé
Montrer par récurrence que pour tout n ≥ 0 : 4ⁿ - 1 est divisible par 3.
Indice : Écris 4ⁿ⁺¹ - 1 = 4 × 4ⁿ - 1 = 4(4ⁿ - 1) + 3 et utilise l'hypothèse de récurrence.
Correction
- Étape 1 : Une récurrence sur une divisibilité — et le geste qui la déverrouille n'est pas évident la première fois.
Récurrence et divisibilité :
« 3 divise A » s'écrit A = 3k avec k entier. C'est cette écriture qu'il faut poser, car c'est elle qu'on peut manipuler algébriquement.
👉 Le geste de l'hérédité : faire apparaître 4ⁿ - 1 dans 4ⁿ⁺¹ - 1. Pour cela on écrit 4ⁿ⁺¹ = 4 × 4ⁿ, puis on ajoute et retranche ce qu'il faut pour reconstituer le terme voulu.
⚠️ Et la conclusion doit exhiber un entier : écrire 4ⁿ⁺¹-1 = 3 × (quelque chose) ne suffit pas, il faut que ce quelque chose soit visiblement entier.
- Étape 2 : Posons P(n) : « 4ⁿ - 1 est divisible par 3 », pour n ≥ 0.
Initialisation (n = 0) :
4⁰ - 1 = 1 - 1 = 0, et 0 = 3 × 0
0 est divisible par 3, donc P(0) est vraie.
ℹ️ Zéro est divisible par tout entier non nul : c'est une convention parfois surprenante, mais elle découle directement de la définition (0 = 3 × 0).
4⁰ - 1 = 0 = 3 × 0 ✓
- Étape 3 : Hérédité. Soit n ≥ 0 fixé. Supposons P(n) : il existe un entier k tel que
4ⁿ - 1 = 3k
Montrons que 4ⁿ⁺¹ - 1 est divisible par 3. On fait apparaître 4ⁿ - 1 :
4ⁿ⁺¹ - 1 = 4 × 4ⁿ - 1
Le geste : écrire 4 × 4ⁿ = 4(4ⁿ - 1) + 4, ce qui fait apparaître le terme de l'hypothèse.
4ⁿ⁺¹ - 1 = 4(4ⁿ - 1) + 4 - 1 = 4(4ⁿ-1) + 3
4ⁿ⁺¹ - 1 = 4(4ⁿ - 1) + 3
- Étape 4 : On substitue l'hypothèse 4ⁿ - 1 = 3k :
4ⁿ⁺¹ - 1 = 4 × 3k + 3 = 12k + 3
On factorise par 3 :
4ⁿ⁺¹ - 1 = 3(4k+1)
Et 4k+1 est un entier, puisque k en est un. Donc 4ⁿ⁺¹-1 est divisible par 3 : P(n+1) est vraie.
Conclusion : par récurrence, 4ⁿ - 1 est divisible par 3 pour tout n ≥ 0.
ℹ️ Contrôle sur les premiers rangs : 4¹-1 = 3, 4²-1 = 15 = 3× 5, 4³-1 = 63 = 3 × 21 ✓
4ⁿ⁺¹-1 = 3(4k+1), 4k+1 ∈ ℤ
- Étape 5 : L'erreur classique :
Écrire « 4ⁿ - 1 est divisible par 3 » et s'en servir tel quel, sans jamais poser 4ⁿ - 1 = 3k.
Une phrase ne se manipule pas ; une égalité, si. Poser = 3k est ce qui permet de substituer et de factoriser — c'est-à-dire de faire des mathématiques plutôt que de répéter l'énoncé.
👉 Et à la fin, nommer l'entier obtenu : « 4k+1 est un entier car k en est un ». Sans cette phrase, on n'a pas montré la divisibilité, seulement écrit un produit.
À retenir :
Divisibilité ⟶ poser A = 3k avec k entier, et conclure en exhibant un nouvel entier.
👉 Et le geste de l'hérédité : 4ⁿ⁺¹ = 4 × 4ⁿ, puis ajouter et retrancher pour reconstituer le terme de l'hypothèse.