Récurrence : divisibilité par 3

Énoncé

Montrer par récurrence que pour tout n 0 : 4^n - 1 est divisible par 3.

Indice : Écris 4^{n+1} - 1 = 4 4^n - 1 = 4(4^n - 1) + 3 et utilise l'hypothèse de récurrence.

Correction

1. É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^n - 1 dans 4^{n+1} - 1. Pour cela on écrit 4^{n+1} = 4 4^n, puis on ajoute et retranche ce qu'il faut pour reconstituer le terme voulu. ⚠️ Et la conclusion doit exhiber un entier : écrire 4^{n+1}-1 = 3 (quelque chose) ne suffit pas, il faut que ce quelque chose soit visiblement entier.
2. Étape 2 : Posons P(n) : « 4^n - 1 est divisible par 3 », pour n 0. Initialisation (n = 0) : 4^0 - 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^0 - 1 = 0 = 3 0 \

3. Étape 3 : Hérédité. Soit n 0 fixé. Supposons P(n) : il existe un entier k tel que [formule] Montrons que 4^{n+1} - 1 est divisible par 3. On fait apparaître 4^n - 1 : 4^{n+1} - 1 = 4 4^n - 1 Le geste : écrire 4 4^n = 4(4^n - 1) + 4, ce qui fait apparaître le terme de l'hypothèse. 4^{n+1} - 1 = 4(4^n - 1) + 4 - 1 = 4(4^n-1) + 3

   4^{n+1} - 1 = 4(4^n - 1) + 3

4. Étape 4 : On substitue l'hypothèse 4^n - 1 = 3k : 4^{n+1} - 1 = 4 3k + 3 = 12k + 3 On factorise par 3 : [formule] Et 4k+1 est un entier, puisque k en est un. Donc 4^{n+1}-1 est divisible par 3 : P(n+1) est vraie. Conclusion : par récurrence, 4^n - 1 est divisible par 3 pour tout n 0. ℹ️ Contrôle sur les premiers rangs : 4^1-1 = 3, 4^2-1 = 15 = 3 5, 4^3-1 = 63 = 3 21 ✓

   4^{n+1}-1 = 3(4k+1), \ 4k+1 Z

5. Étape 5 : L'erreur classique : Écrire « 4^n - 1 est divisible par 3 » et s'en servir tel quel, sans jamais poser 4^n - 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^{n+1} = 4 4^n, puis ajouter et retrancher pour reconstituer le terme de l'hypothèse.