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

  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ⁿ - 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.
  2. É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 ✓

  3. É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

  4. É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 ∈ ℤ

  5. É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.