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.

Note historique

Pierre de Fermat, né dans la première décennie du XVIIe siècle, à Beaumont-de-Lomagne près de Montauban (Tarn-et-Garonne), et mort le 12 janvier 1665 à Castres (département du Tarn), est un magistrat et surtout mathématicien français, surnommé « le prince des amateurs ». Il est aussi poète, habile latiniste et helléniste, et s’est intéressé aux sciences et en particulier à la physique ; on lui doit notamment le petit théorème de Fermat, le principe de Fermat en optique. Il est particulièrement connu pour avoir énoncé le dernier théorème de Fermat, dont la démonstration n’a été établie que plus de 300 ans plus tard par le mathématicien britannique Andrew Wiles en 1994.

Wikipedia.org

Exercice.
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 ?

Corrigé.
Les cinq premiers nombres de Fermat :
$F_{0}=2^{1}+1=3$,
$F_{1}=2^{2}+1=5$,
$F_{2}=2^{4}+1=17$,
$F_{3}=2^{8}+1=257$,
$F_{4}=2^{16}+1=65\,537$, sont tous premiers.

$F_5= 2^{2^5}+1 =2^32+1=4294967297 = 641\times 6700417$ n’est donc pas premier.

1.2. Étude d’un exemple

Exercice résolu 1.
Démontrer que pour tout entier naturel $n$, « $4^n +5$ est un multiple de $3$ ».

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$.

Définition.
Soit $n_0$ un entier naturel donné. Pour tout entier naturel $n\geqslant n_0$.
On dit que la proposition $P_{n}$ est héréditaire à partir du rang $n_0$ si, et seulement si : $$\color{brown}{\text{Pour tout } n\geqslant n_0 :\; [P_{n}\Rightarrow P_{n+1}]}$$ Autrement dit :
Pour tout entier $n\geqslant n_0$ : [Si $P_{n}$ est vraie, alors $P_{n+1}$ est vraie].

Ce qui signifie que pour tout entier $n$ fixé : Si on suppose que la proposition est vraie au rang $n$, alors on doit démontrer qu’elle est vraie au rang $(n+1)$.

Théorème.
Soit $n_0$ un entier naturel donné.
Pour tout 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}$ est vraie » il est équivalent de démontrer que :
1°) $P_{n_0}$ est vraie [Initialisation] ;
2°) Pour tout entier $n\geqslant n_0$ : [$P_{n}\Rightarrow P_{n+1}$] [Hérédité].

3. Exercices résolus

Revenons à notre exemple n°1.

Exercice résolu 1.
Démontrer que pour tout entier naturel $n$, « $4^n +5$ est un multiple de $3$ ».

Corrigé.
On peut facilement vérifier que c’est le cas pour une ou quelques valeurs de $n$.
Ici, on veut démontrer que : Pour tout entier $n$ : « $4^n+5$ est un multiple de $3$ ».

Méthode : (commentaire en rouge italique)
On commence par nommer la proposition logique et préciser la méthode de raisonnement :
Pour tout entier $n$, on appelle $P_n$ la proposition logique  $$P_n~~:~~\left[4^n+5$ est un multiple de 3\right]$$ ».
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 naturel fixé, $n\geqslant n_0$, (sous-entendu $n\geqslant n_0$ donné), pour lequel la proposition $P_{n}$ est vraie (et on traduit cet énoncé en donnant la propriété avec des symboles). $$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 (H.R.), on sait que : « $4^n+5$ est un multiple de $3$ ».

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 : $\quad 4^{n+1}+5=(3k-5)\times4+5$
Donc : $\quad 4^{n+1}+5=12k-20+5$
Donc : $\quad 4^{n+1}+5=12k-15$
D’où : $\quad 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. Nous avons démontré que la proposition est vraie au rang $0$ et que, pour tout entier $n\geqslant 0$ : [$P_{n}\Rightarrow P_{n+1}$].
Donc, d’après le principe de récurrence, pour tout entier $n\geqslant 0$, $P_{n}$ est vraie.

Exercice résolu n°2. (Facile)
Démontrer que pour tout entier naturel n, on a : $2^n> n$.

Corrigé.
On appelle $P_{n}$ la proposition logique « $2^n>n$ ».
Montrons par récurrence que : Pour tout entier $n$ : [$P_{n}$ est vraie].

i) Initialisation.
Pour $n= 0$, on a :
$2^0=1$ et $n=0$, donc $2^0>0$,
et par suite, $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 de récurrence, on sait que $P_{n}$ est vraie. Donc
$$2^n>n\quad\text{(H.R.)}$$
Mais alors, $2^{n+1}=2^n\times 2^1 = 2\times 2^n = 2^n+2^n$
Or d’après (HR), $$2^n>n \quad\text{(1)} $$
et pour tout entier $n$, $2^n$ est un entier naturel non nul. Donc :
$$2^n\geqslant 1 \quad\text{(2)} $$
En additionnant membre à membre les deux inégalités (1) et (2), on obtient une troisième inégalité de même sens. Donc : $$2^n+ 2^n >n+1\quad\text{(1)}$$
On obtient : $$2^{n+1}>n+1\quad\text{(3)}$$
Ce qui montre que $P_{n+1}$ est vraie. Donc, la proposition est héréditaire.

Conclusion. Nous avons démontré que la proposition est vraie au rang $0$ et que, pour tout entier $n\geqslant 0$ : [$P_{n}\Rightarrow P_{n+1}$].
Donc, d’après le principe de récurrence, pour tout entier $n\geqslant 0$, $P_{n}$ est vraie.

Exercice résolu n°3.
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. Nous avons démontré que la proposition est vraie au rang $0$ et que, pour tout entier $n\geqslant 0$ : [$P_{n}\Rightarrow P_{n+1}$].
Donc, d’après le principe de récurrence, pour tout entier $n\geqslant 0$, $P_{n}$ est vraie.

Exemple 4.
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+\cdots+n = \dfrac{n(n+1)}{2}$ » ou encore « $\dsum_{k=1}^{k=n} k = \dfrac{n(n+1)}{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 ]. Donc :
$$ 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. Nous avons démontré que la proposition est vraie au rang $0$ et que, pour tout entier $n\geqslant 0$ : [$P_{n}\Rightarrow P_{n+1}$].
Donc, d’après le principe de récurrence, pour tout entier $n\geqslant 0$, $P_{n}$ est vraie. $ est vraie.

Exercice résolu 4.

4. Exercices supplémentaires pour progresser

Exercice 5.
Démontrez que pour tout entier naturel $n$ : « $7^{4n}-1$ est un multiple de $5$ ».

Exercice 6.
Démontrez que pour tout entier naturel $n$ : « $\dsum_{k=0}^{k=n} k^2 =\dfrac{n(n+1)(2n+1)}{6}$ ».

Exercice 7.
Démontrez que pour tout entier naturel $n$ : « $\dsum_{k=0}^{k=n} k^3 =\left[\dfrac{n(n+1)}{2}\right]^2$ ».

Exercice 8.
Démontrez que pour tout entier naturel $n$ : « $\dsum_{k=0}^{k=n} k(k+1) =\dfrac{n(n+1)(n+2)}{3}$ ».

Exercice 9.
On considère la suite $(u_n)$ de nombres réels définie par : $u_0=1$ et $u_{n+1}=\sqrt{u_n+6}$.
1°a) Écrire une propriété en fonction de $n$ exprimant que la suite $(u_n)$ est « à termes strictement positifs ».
1°b) Démontrer que la suite $(u_n)$ est « à termes strictement positifs ».
2°a) Écrire une propriété en fonction de $n$ exprimant que la suite $(u_n)$ est majorée par 3.
2°b) Démontrer que la suite $(u_n)$ est majorée par 3.
3°a) Écrire une propriété en fonction de $n$ exprimant que la suite $(u_n)$ est strictement croissante.
3°b) Démontrer que la suite $(u_n)$ est strictement croissante.

Exercice 10.
Soit ${\mathcal C}$ un cercle non réduit à un point.
Soient $A_1$, $A_2,\ldots,A_n$, $n$ points distincts du cercle ${\mathcal C}$.
1°) En faisant un raisonnement sur les valeurs successives de $n$, émettre une conjecture donnant le nombre de cordes distinctes qu’on peut construire entre les $n$ points $A_i$, en fonction de $n$. Justifier votre réponse.
2°) Démontrer votre conjecture.

Corrigé
A vous de jouer !

Vues : 1808