Une divisibilité démontrée par récurrence

Exercice d'entraînement · niveau 2 · mathématiques (ECT 1re année), chapitre 1 — Raisonnement, ensembles et applications · Raisonnement par récurrence

Énoncé

Démontrer par récurrence que pour tout entier $n \geq 0$ , le nombre $4^{n} - 1$ est divisible par $3$ .

En déduire, sans nouvelle récurrence, que $4^{n} + 2$ est lui aussi divisible par $3$ .

Corrigé

Notons $P (n)$ : « $4^{n} - 1$ est divisible par $3$ », c'est-à-dire « il existe un entier $k$ tel que $4^{n} - 1 = 3 k$ ». C'est cette écriture, avec un entier $k$ nommé, qui rend la propriété maniable.

Initialisation. Pour $n = 0$ : $4^{0} - 1 = 1 - 1 = 0 = 3 \times 0$ . Donc $P (0)$ est vraie.

Hérédité. Supposons $P (n)$ vraie pour un entier $n \geq 0$ fixé : il existe un entier $k$ avec $4^{n} - 1 = 3 k$ , c'est-à-dire $4^{n} = 3 k + 1$ . Alors $4^{n + 1} - 1 = 4 \times 4^{n} - 1 = 4 (3 k + 1) - 1 = 12 k + 3 = 3 (4 k + 1) .$ Le nombre $4 k + 1$ est un entier, 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 entier $n \geq 0$ .

La déduction. On écrit $4^{n} + 2 = (4^{n} - 1) + 3$ . Le premier terme est divisible par $3$ d'après ce qui précède, le second l'est visiblement ; une somme de deux multiples de $3$ est un multiple de $3$ . Donc $4^{n} + 2$ est divisible par $3$ , et l'on n'a pas eu besoin de refaire une récurrence : c'est le résultat déjà acquis qui travaille.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.