Langage de la logique et des ensembles

Raisonnement par récurrence - Exercice 4

30 min
50
Encore un exercice pour maîtriser la méthodologie de la démonstration par récurrence, mais dans le domaine de l'Arithmétique.
Question 1

Soit nn un nombre entier naturel non nul. Autrement dit : n∈N⋆n \in \mathbb{N}^\star.
Démontrer que 77 divise 32n−2n3^{2n} - 2^n.

Correction
Nous allons réaliser cette démonstration par récurrence.
Soit nn un nombre entier naturel non nul. Notons par P(n)P(n) la propriété suivante :
P(n):7  divise  32n−2nP(n) : 7 \,\, {\bf{divise}} \,\, 3^{2n} - 2^n
▶ Etape  1:L′initialisation{\color{green}{\bf{\blacktriangleright \,Etape \,\, 1 : L'initialisation}}}
Soit n=1n=1, vérifions si la propriété P(1)P(1) est bien vérifiée. On a :
P(1):7  divise  32×1−21P(1) : 7 \,\, {\bf{divise}} \,\, 3^{2\times 1} - 2^1
Soit :
P(1):7  divise  32−2P(1) : 7 \,\, {\bf{divise}} \,\, 3^2 - 2
Soit encore :
P(1):7  divise  9−2P(1) : 7 \,\, {\bf{divise}} \,\, 9 - 2
Donc :
P(1):7  divise  7P(1) : 7 \,\, {\bf{divise}} \,\, 7
Ce qui est indéniablement vrai puisque tout entier naturel est son propre diviseur. Donc la propriété P(1)P(1) est bien vérifiée.
▶▶ Etape  2:La  transmission{\color{blue}{\bf{\blacktriangleright \blacktriangleright \,Etape \,\, 2 : La \,\, transmission}}}
Dans cette deuxième étape de la démonstration, nous allons supposer que la propriété P(n)P(n) est vraie, et sous cette vérité, démontrer que la propriété P(n+1)P(n+1) est également vraie. Autrement dit, nous allons démontrer que P(n)⟹P(n+1)P(n) \Longrightarrow P(n+1).
Ainsi, supposons que nous ayons bien la propriété 7  divise  32n−2n 7 \,\, {\bf{divise}} \,\, 3^{2n} - 2^n. Ceci revient à accepter l'existence d'un certain nombre entier naturel NN non nul, tel que 32n−2n=7N3^{2n} - 2^n = 7N.
Dans ce cas, déterminons l'expression de P(n+1)P(n+1), et vérifions sa vérité. On a alors :
32(n+1)−2n+1=32n+2−2n+13^{2(n+1)} - 2^{n+1} = 3^{2n + 2} - 2^{n+1}
Soit :
32(n+1)−2n+1=32n32−2n+13^{2(n+1)} - 2^{n+1} = 3^{2n}3^2 - 2^{n+1}
D'où :
32(n+1)−2n+1=32n32−2n32+2n32−2n+13^{2(n+1)} - 2^{n+1} = 3^{2n}3^2 - 2^n 3^2 + 2^n 3^2 - 2^{n+1}
En factorisant par 323^2, on trouve que :
32(n+1)−2n+1=32(32n−2n)+2n32−2n+13^{2(n+1)} - 2^{n+1} = 3^2 \big( 3^{2n} - 2^n \big) + 2^n 3^2 - 2^{n+1}
En écrivant 2n+1=2n21=2n22^{n+1} = 2^n 2^1 = 2^n 2. Donc :
32(n+1)−2n+1=32(32n−2n)+2n32−2n23^{2(n+1)} - 2^{n+1} = 3^2 \big( 3^{2n} - 2^n \big) + 2^n 3^2 - 2^n 2
En factorisant par 2n2^n, on obtient :
32(n+1)−2n+1=32(32n−2n)+2n(32−2)3^{2(n+1)} - 2^{n+1} = 3^2 \big( 3^{2n} - 2^n \big) + 2^n (3^2 - 2)
Comme 32−2=73^2 - 2 = 7 on peut donc écrire :
32(n+1)−2n+1=32(32n−2n)+2n73^{2(n+1)} - 2^{n+1} = 3^2 \big( 3^{2n} - 2^n \big) + 2^n 7
Comme la propriété P(n)P(n) est supposée vraie, on a 32n−2n=7N3^{2n} - 2^n = 7N, d'où :
32(n+1)−2n+1=327N+2n73^{2(n+1)} - 2^{n+1} = 3^2 7N + 2^n 7
En factorisant par 77, on trouve que :
32(n+1)−2n+1=7(32N+2n)3^{2(n+1)} - 2^{n+1} = 7 \big( 3^2 N + 2^n \big)
Soit encore :
32(n+1)−2n+1=7(9N+2n)3^{2(n+1)} - 2^{n+1} = 7 \big( 9N + 2^n \big)
Comme N∈N⋆N \in \mathbb{N}^\star alors 9N∈N⋆9N \in \mathbb{N}^\star. De plus, 2n∈N⋆2^n \in \mathbb{N}^\star également. Donc 9N+2n∈N⋆9N + 2^n \in \mathbb{N}^\star. Posons alors N=9N+2n∈N⋆\mathcal{N} = 9N + 2^n \in \mathbb{N}^\star, et on aboutit à la relation :
32(n+1)−2n+1=7N3^{2(n+1)} - 2^{n+1} = 7 \mathcal{N}
Ceci signifie que 7  divise  32(n+1)−2n+17 \,\, {\bf{divise}} \,\, 3^{2(n+1)} - 2^{n+1}.
On constate alors que la propriété P(n+1)P(n+1) est donc bien vérifiée. On a donc bien démontré que P(n)⟹P(n+1)P(n) \Longrightarrow P(n+1).
▶▶▶ Etape  3:La  conclusion{\color{red}{\bf{\blacktriangleright \blacktriangleright \blacktriangleright \,Etape \,\, 3 : La \,\, conclusion}}}
En vertu des axiomes de la récurrence, la propriété P(n):7  divise  32n−2nP(n) : 7 \,\, {\bf{divise}} \,\, 3^{2n} - 2^n est vraie pour tout entier naturel n≠0n \neq 0. ■{\color{red}{\blacksquare}}