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 : Posons P(n) : « 3 (4^n - 1) ». **Initialisation** (n=0) : 4^0 - 1 = 0 = 3 0. P(0) est vraie.
2. Étape 2 : **Hérédité** : supposons P(n) vraie, c'est-à-dire 4^n - 1 = 3k pour un certain k Z.
3. Étape 3 : 4^{n+1} - 1 = 4 4^n - 1 = 4(4^n - 1) + 4 - 1 = 4 3k + 3 = 3(4k + 1) Donc 4^{n+1} - 1 est divisible par 3. P(n+1) est vraie.
4. Étape 4 : **Conclusion** : par le principe de récurrence, 4^n - 1 est divisible par 3 pour tout n 0.