Raisonnement par récurrence


1. Méthode de raisonnement par récurrence

1.1. Note historique

Les nombres de Fermat

Définition.
Un nombre de Fermat est un entier naturel qui s’écrit sous la forme $2^{2^n}+1$, où $n$ est un entier naturel. Pour tout $n\in\N$ on note $F_n=2^{2^n} + 1$, le $(n+1)$-ème nombre de Fermat.

Calculer $F_0$, $F_1$, $F_2$ $F_3$, $F_4$ et $F_5$.
A l’aide d’une calculatrice ou d’un algorithme, vérifiez si ces nombres sont premiers ou non.
Que constatez-vous ?

En 1640, le mathématicien français Pierre de Fermat a émis la conjecture que « pour tout $n\in\N$, $F_n$ est un nombre premier ». Il s’avère que cette conjecture est fausse.

Presque un siècle plus tard en 1732, le premier à lui porter la contradiction, est le mathématicien suisse Leonhard Euler en présentant un diviseur (donc deux diviseurs au moins) de $F_5$ prouvant qu’« il existe au moins un nombre de Fermat qui n’est pas premier ». Il affirme que $F_5$ est divisible par 641.

Blaise Pascal, à 19 ans, en 1642 invente la première (calculatrice) qu’il appelait la « Pascaline » ou « machine arithmétique ». [Musée Lecoq à Clermont Ferrand].

Mais, existe-il un moyen de démontrer qu’une propriété dépendant d’un entier $n$, est vraie pour tout $n\in\N$ sans passer par la calculatrice ?

1.2. Étude d’un exemple

Exercice résolu 1.
Pour chaque entier naturel n, on considère la proposition logique $P_n$ : « $4^n +5$ est un multiple de $3$ ». On se propose de « démontrer » que : Pour tout entier $n$, $P_n$ est vraie.

Corrigé.
On peut facilement vérifier que c’est le cas pour une ou quelques valeurs de $n$.

Par exemple :
$P_0$ : $4^0 +5 = 1+5 = 6$ est un multiple de $3$. Donc $P_0$ est vraie.
$P_1$ : $4^1 +5 = 4+5 = 9$ est un multiple de $3$. Donc $P_1$ est vraie.
$P_2$ : $4^2 +5 = 16+5 = 21$ est un multiple de $3$. Donc $P_2$ est vraie.
$P_3$ : $4^3 +5 = 64+5 = 69$ est un multiple de $3$. Donc $P_3$ est vraie.
$P_4$ : $4^4 +5 = 256+5 = 261$ est encore un multiple de $3$. Donc $P_4$ est vraie.
Et ainsi de suite…
Le « Et ainsi de suite… » ne suffit pas pour démontrer que $P_n$ est vraie pour tout entier $n$ !

L’étude de quelques exemples ne prouve pas que $P_n$ est vraie pour tout entier $n$ !
La preuve ? Nous venons de voir que $F_5$ n’est pas un nombre premier. Donc $P_5$ est fausse.

Nous allons voir qu’un raisonnement par récurrence permet de faire cette démonstration.

2. Principe du raisonnement par récurrence

Il s’agit d’un raisonnement « en escalier ».
On démontre que la proriété $P_n$ est vraie pour le premier rang $n_0$ pour démarrer la machine.
Puis on démontre que la propriété est héréditaire. Si la propriété est vraie à un rang $n$ donné, on démontre qu’elle est aussi vraie au rang suivant $n+1$.

Théorème.
Soit $n_0$ un entier naturel donné.
Pour chaque entier naturel $n\geqslant n_0$, on considère la proposition logique $P_n$ dépendant de l’entier $n$.
Pour démontrer que « Pour tout entier $n\geqslant n_0$, $P_{n_0}$ est vraie » il est équivalent de démontrer que :
1°) $P_{n_0}$ est vraie [Initialisation] ;
2°) Pour tout entier $n\in\N$ : [$P_{n}\Rightarrow P_{n+1}$] [Hérédité].
(Autrement dit : pour tout entier $n$ fixé : Si $P_{n}$ est vraie, Alors $P_{n+1}$ est vraie).

Définition.
Soit $n_0$ un entier naturel donné. Pour chaque entier naturel $n\geqslant n_0$, on considère la proposition logique $P_{n}$ dépendant de l’entier $n$.
On dit que la proposition $P_{n}$ est héréditaire à partir du rang $n_0$ lorsque, pour tout entier $n$ : [Si $P_{n}$ est vraie, alors $P_{n+1}$ est vraie].

Revenons à notre exemple n°1.

Corrigé.
On peut facilement vérifier que c’est le cas pour une ou quelques valeurs de $n$.
On veut démontrer que : Pour tout entier $n$ : « $4^n+5$ est un multiple de $3$ ».
Méthode (en rouge) : (commentaire en italique)
On commence par nommer la proposition logique :
On appelle $P_n$ la proposition logique « $4^n+5$ est un multiple de $3$ ».
Montrons par récurrence que : Pour tout entier $n$ : [$P_n$ est vraie].

i) Initialisation.
(On vérifie pour le premier rang. Ici on commence à 0).
Pour $n = 0$, $4^0+5 = 1+5 = 6$ est (bien) un multiple de $3$.
Donc $P_0$ est vraie.

ii) Hérédité.
Soit $n\in\N$ un entier supérieur ou égal à $n_0$ fixé (sous-entendu $$n\geqslant n_0$ donné ).
Supposons que $P_{n}$ est vraie. Et on traduit en donnant la propriété avec des symboles : C’est-à-dire :
$$4^n+5\text{ est un multiple de }3\quad(H.R.)$$
(H.R.) pour « Hypothèse de récurrence »
Montrons que $P_{n+1}$ est vraie.
D’après l’hypothèse de récurrence, on sait que : « $4^n+5$ est un multiple de $3$ » (HR).
On traduit cette affirmation par un énoncé mathématique.
Donc, il existe un entier $k$ tel que $4^n+5 = 3k$. Ici $k\geqslant 2$ car $n\geqslant 0$.
Et là, on essaie d’exprimer « $4^n+5$ » à l’aide de $k$.
Nous avons un élément commun « $4^n$ ». On l’exprime à l’aide de $k$ pour faire le lien.
On a alors : $4^n = 3k – 5$.
Or, [Astuce élémentaire] d’après le cours de la classe de 4ème : $4^{n+1}=$4^n\times4^1=4^n\times4$.
On remplace $4^n$ par $3k-5$ dans cette égalité.
Et on écrit : $4^{n+1}=(3k-5)\times4$
Donc : $4^{n+1}+5=(3k-5)\times4+5$
Donc : $4^{n+1}+5=12k-20+5$
Donc : $4^{n+1}+5=12k-15$
D’où : $4^{n+1}+5=3(4k-5)$.
On pose $k’ = 4k-5$. Comme $k$ est un entier supérieur ou égal à $2$, on en déduit que $k’\geqslant 3$.
Par conséquent : « Il existe un entier $k’$ tel que : $4^{n+1}+5$ est un multiple de $3$ ».
Ce qui montre que $P_{n+1}$ est vraie. Donc la propriété est héréditaire.
Conclusion. Pour tout entier $n$, $P_{n}$ est vraie.

Exercice résolu n°2.
Soit $a$ un nombre réel strictement positif.
Démontrer que pour tout entier naturel n, on a : $(1+a)^n\geqslant 1+na$.
Cette inégalité s’appelle Inégalité de Bernoulli.

Corrigé.
On suit notre méthode (cette fois sans commentaire !).
On appelle $P_{n}$ la proposition logique « $(1+a)^n\geqslant 1+na$ ».
Montrons par récurrence que : Pour tout entier $n$ : [$P_{n}$ est vraie].

i) Initialisation.
Pour $n= 0$, $(1+a)^0=1$ et $1+0a=1$.
Donc $(1+a)^0\geqslant 1+0a$.
Donc $P_{0}$ est vraie.

ii) Hérédité.
Soit $n\in\N$ un entier fixé.
Supposons que $P_{n}$ est vraie. (Hypothèse de récurrence).
Montrons que $P_{n+1}$ est vraie.
D’après notre hypothèse, on sait que $P_{n}$ est vraie. Donc
$$(1+a)^n\geqslant 1+na\quad\text{(H.R.)}$$
Mais alors [Astuce élémentaire], on sait que $(1+a)^{n+1}=(1+a)^n\times(1+a)$.
Or, par hypothèse de récurrence (H.R.), on sait que $(1+a)^n\geqslant 1+na$ (*)
D’après l’énoncé, $a$ est un nombre réel strictement positif, donc $(1+a) >1$.
Donc, on peut multiplier les deux membres de l’inégalité (*) par $(1+a)$ sans changer de sens de l’inégalité. On obtient : $(1+a)^{n}\times(1+a)\geqslant (1+a)^n\times(1+a)$.
En développant l’expression de droite, on obtient : $(1+a)^{n+1}\geqslant 1+na+a+na^2$.
Comme $na^2\geqslant0$, on a : $1+na+a+na^2\geqslant 1+na+a$.
Par conséquent : $(1+a)^{n+1}\geqslant 1+(n+1)a$.
Ce qui montre que $P_{n+1}$ est vraie. Donc la propriété est héréditaire.

Conclusion. Pour tout entier $n$, $P_{n}$ est vraie.

Exemple 3.
Démontrez que pour tout entier non nul $n$, la somme des n premiers nombres entiers non nuls, est égale à $\dfrac{n(n+1)}{2}$.

Corrigé.
Dans cet exemple, la propriété $P_{n}$n’est pas exprimée concrètement.

1ère étape : Exprimer et nommer la proprété $P_{n}$.
Pour chaque entier naturel $n$, non nul (ici on commence à $n_0 = 1$), on appelle $P_{n}$ la proposition logique : « $1+2+3+dotsaxis+n = {n(n+1)} over {2}$ » ou encore « $Sum from{k=1} to{k=n} k = {n(n+1)} over {2}$ ».

2ème étape : Montrons, par récurrence que : Pour tout entier n : [$P_{n}$ est vraie].
i) Initialisation.
Pour $n = 1$, il n’y a qu’un seul terme dans la somme de gauche qui est égal à $1$.
A droite, on a $\dfrac{1(1+1)}{2}=\dfrac{2}{2} =1$.
D’où l’égalité. Donc $P_{1}$ est vraie.

ii) Hérédité.
Soit $n\in\N$ un entier fixé.
Supposons que $P_{n}$est vraie. (Hypothèse de récurrence).
Montrons que $P_{n+1}$ est vraie.
D’après l’hypothèse de récurrence, on sait que :
$$\dsum_{k=1}^{k=n}k=\dfrac{n(n+1)}{2}\quad\text{(H.R.)}$$
Mais alors, [Astuce élémentaire : la somme des $(n+1)$ premiers nombres est égale à la somme des n premiers nombres, plus le $(n+1)$-ème ], on sait que :
$$ 1+2+3+\cdots+n+(n+1)=\color{brown}{\left[1+2+3+\cdots+n\right]}+(n+1)\quad(*)$$
Or, par hypothèse de récurrence (H.R.) , on sait que : $\color{brown}{1+2+3+\cdots+n}=\dfrac{n(n+1)}{2}$ (H.R.).
On remplace $1+2+3+…+n$ par la fraction dans l’égalité (*) et on obtient :
$$1+2+3+\cdots+n+(n+1)=\color{brown}{\dfrac{n(n+1)}{2}}+(n+1)$$
puis on réduit au même dénominateur.
Ce qui donne : $1+2+3+\cdots+n+(n+1)=\dfrac{(n+1)(n+2)}{2}$, qu’on peut encore écrire :
$$1+2+3+\cdots+n+(n+1)=\dfrac{(n+1)left[(n+1)+1 right]}{2}$$
Ce qui n’est autre que l’expression de $P_{n+1}$.
Ce qui montre que $P_{n+1}$ est vraie. Donc la propriété est héréditaire.

Conclusion. Pour tout entier $n$, $P_{n}$ est vraie.

Exercice résolu 4.

3. Exercices supplémentaires pour progresser