Exercice de raisonnement par récurrence

Avant de présenter les raisonnements par récurrence, nous allons donner une propriété importante de l’ensemble des entiers naturels que nous admettrons.

Toute partie non vide de $\mathbb{N}$

admet un plus petit élément.

Conséquence : Il n’existe pas de suite infinie d’entiers naturels strictement décroissante.

Le principe de récurrence

La récurrence simple

Soit $n_0\in\mathbb{N}$ . On considère une propriété (ou un prédicat) $\mathcal{P}_n$ définie pour $n\in\mathbb{N}$ , $n\ge n_0$

<img loading="lazy" ci-src="https://sherpas.com/blog/content/ql-cache/quicklatex.com-b52c797b0593e8029a0393ef3037ca76_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="n_0\in\mathbb{N}" title="Rendered by QuickLaTeX.com" height="15" width="53" style="vertical-align: -3px;"/>. On considère une propriété (ou un prédicat) <img loading="lazy" ci-src="https://sherpas.com/blog/content/ql-cache/quicklatex.com-e2f17ea1cde822bc8e078f4c8463f69d_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="\mathcal{P}_n" title="Rendered by QuickLaTeX.com" height="15" width="20" style="vertical-align: -3px;"/> définie pour <img loading="lazy" ci-src="https://sherpas.com/blog/content/ql-cache/quicklatex.com-588616762f1acc1b153991dd6fa4f83c_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="n\in\mathbb{N}" title="Rendered by QuickLaTeX.com" height="13" width="45" style="vertical-align: -1px;"/>, <img loading="lazy" ci-src="https://sherpas.com/blog/content/ql-cache/quicklatex.com-f7fb60614bc646d617c7be2a810aa128_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="n\ge n_0" title="Rendered by QuickLaTeX.com" height="15" width="52" style="vertical-align: -3px;"/><noscript><img loading="lazy" src="https://sherpas.com/blog/content/ql-cache/quicklatex.com-b52c797b0593e8029a0393ef3037ca76_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="n_0\in\mathbb{N}" title="Rendered by QuickLaTeX.com" height="15" width="53" style="vertical-align: -3px;"/>. On considère une propriété (ou un prédicat) <img loading="lazy" src="https://sherpas.com/blog/content/ql-cache/quicklatex.com-e2f17ea1cde822bc8e078f4c8463f69d_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="\mathcal{P}_n" title="Rendered by QuickLaTeX.com" height="15" width="20" style="vertical-align: -3px;"/> définie pour <img loading="lazy" src="https://sherpas.com/blog/content/ql-cache/quicklatex.com-588616762f1acc1b153991dd6fa4f83c_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="n\in\mathbb{N}" title="Rendered by QuickLaTeX.com" height="13" width="45" style="vertical-align: -1px;"/>, <img loading="lazy" src="https://sherpas.com/blog/content/ql-cache/quicklatex.com-f7fb60614bc646d617c7be2a810aa128_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="n\ge n_0" title="Rendered by QuickLaTeX.com" height="15" width="52" style="vertical-align: -3px;"/>

telle que :

Initialisation : $\mathcal{P}_{n_0}$

est vraie;

Hérédité : pour tout $n\in\N$ , $n\ge n_0$ , si $\mathcal{P}_n$ est vraie, alors $\mathcal{P}_{n+1}$

l’est aussi.

Alors, pour tout $n\in\mathbb{N}$ , $n\ge n_0$ , $\mathcal{P}_n$

est vraie.

Démonstration

On considère l’ensemble $A =\big\{n \in\N,\;n\ge n_0,\; \mathcal{P}_n\text{ est fausse}\big\}$

.
On suppose que $A$ est non vide, il admet donc un plus petit élément que nous noterons $m$ qui est différent de $n_0$ (car $\mathcal{P}_{n_0}$ est vraie). Alors m-1 n’est pas dans $A$ et donc l’entier suivant, $m$ , n’est pas non plus dans $A$ ce qui amène à une contradiction. On en déduit que $A$

est vide.

Exemple

Montrer que pour tout $n\in\mathbb{N}$ , la somme $S_n$ des $n$ premiers entiers naturels est égale à $\dfrac{n(n+1)}{2}.$

Soit $n\in\mathbb{N}$ . Montrons par récurrence sur $n\in\mathbb{N}$ la propriété $\mathcal{P}_n$ : $S_n=\dfrac{n(n+1)}{2}$

.
Initialisation : Pour $n=0$ , $S_0=0$

Initialisation :

, la propriété est évidente.
Hérédité : Soit $n\in\mathbb{N}$ . On suppose que $\mathcal{P}_n$ est vraie, montrons que $\mathcal{P}_{n+1}$ l’est encore. Par définition : $S_{n+1}=S_n+(n+1).$ D’après l’hypothèse de récurrence, on a : $S_n=\dfrac{n(n+1)}{2}$

Hérédité :

.
Ainsi : $S_{n+1}=\dfrac{n(n+1)}{2}+n+1=\dfrac{(n+1)(n+2)}{2}.$

$\mathcal{P}_{n+1}$ est bien vraie. D’après le principe de récurrence, la propriété est vraie pour tout $n\in\mathbb{N}$

On va maintenant présenter deux variantes du raisonnement par récurrence : la récurrence double et la récurrence forte.

La récurrence double

Proposition

Soit $n_0\in\mathbb{N}$ . On considère une propriété (ou un prédicat) $\mathcal{P}_n$ définie pour $n\in\mathbb{N}$ , $n\ge n_0$

telle que :

Initialisation : $\mathcal{P}_{n_0}$ et $\mathcal{P}_{n_0+1}$

Initialisation : $\mathcal{P}_{n_0}$

et $\mathcal{P}_{n_0+1}$ sont vraies ;

Hérédité : pour tout $n\in\N$ , $n\ge n_0$ , si $\mathcal{P}_n$ et $\mathcal{P}_{n+1}$ sont vraies, alors $\mathcal{P}_{n+2}$

l’est aussi.

Alors, pour tout $n\in\mathbb{N}$ , $n\ge n_0$ , $\mathcal{P}_n$

est vraie.

Exemple

On considère la suite de Fibonacci définie par : $u_0=0,\;u_1=1,\;\forall n\in\mathbb{N},\;u_{n+2}=u_{n+1}+u_n.$

Soit $n\in\mathbb{N}^*$ . Montrons par récurrence double sur $n\in\mathbb{N}^*$ la propriété $\mathcal{P}_n$ : $u_{n}\in\mathbb{N}^*$

. Montrons par récurrence double sur $n\in\mathbb{N}^*$

la propriété $\mathcal{P}_n$ : $u_{n}\in\mathbb{N}^*$

Initialisation : Pour $n=1$ et $n=2$

, la propriété est évidente.

Hérédité : Soit $n\in\mathbb{N}^*$ . On suppose que $\mathcal{P}_n$ et $\mathcal{P}_{n+1}$ sont vraies, montrons que $\mathcal{P}_{n+2}$ l’est encore. On a : $u_{n+2}=u_{n+1}+u_{n}$ . La somme de deux entiers naturels non nuls est encore un entier naturel non nul, $\mathcal{P}_{n+2}$

Hérédité : Soit $n\in\mathbb{N}^*$

. On suppose que $\mathcal{P}_n$ et $\mathcal{P}_{n+1}$ sont vraies, montrons que $\mathcal{P}_{n+2}$ l’est encore. On a : $u_{n+2}=u_{n+1}+u_{n}$ . La somme de deux entiers naturels non nuls est encore un entier naturel non nul, $\mathcal{P}_{n+2}$ est bien vraie.

D’après le principe de récurrence double, la propriété est vraie pour tout $n\in\mathbb{N}^*$

La récurrence forte

Proposition

Soit $n_0\in\mathbb{N}$ . On considère une propriété (ou un prédicat) $\mathcal{P}_n$ définie pour $n\in\mathbb{N}$ , $n\ge n_0$

telle que :

Initialisation : $\mathcal{P}_{n_0}$

est vraie ;

Hérédité : pour tout $n\in\mathbb{N}$ , $n\ge n_0$ , si, pour tout $k\in\llbracket n_0,n\rrbracket$ , $\mathcal{P}_k$ est vraie, alors $\mathcal{P}_{n+1}$

l’est aussi.

Alors, pour tout $n\in\mathbb{N}$ , $n\ge n_0$ , $\mathcal{P}_n$

est vraie.

Exemple

Montrons par récurrence forte sur $n\in\mathbb{N}$ , $n\ge 2$ , la propriété $\mathcal{P}_n$ : « $n$

, la propriété $\mathcal{P}_n$ : « $n$ admet une décomposition comme produit de nombres premiers ».
Initialisation : $2$ est un nombre premier, donc $\mathcal{P}_2$

Initialisation :

est vraie.
Hérédité : Soit $n\in\mathbb{N}$ , $n\ge 2$ . On suppose que $\mathcal{P}_k$ est vraie pour tout $k\in\llbracket 2,n\rrbracket$ , montrons que $\mathcal{P}_{n+1}$

Hérédité :<img loading="lazy" src="https://sherpas.com/blog/content/ql-cache/quicklatex.com-588616762f1acc1b153991dd6fa4f83c_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="n\in\mathbb{N}" title="Rendered by QuickLaTeX.com" height="13" width="45" style="vertical-align: -1px;"/>, <img loading="lazy" src="https://sherpas.com/blog/content/ql-cache/quicklatex.com-d5482ac64c45006c6548c713888a5d34_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="n\ge 2" title="Rendered by QuickLaTeX.com" height="15" width="42" style="vertical-align: -3px;"/>

. On suppose que $\mathcal{P}_k$ est vraie pour tout $k\in\llbracket 2,n\rrbracket$ , montrons que $\mathcal{P}_{n+1}$ l’est encore. Deux cas sont à considérer :

soit $n+1$ est premier, dans ce cas, $\mathcal{P}_{n+1}$

est bien vraie ;

soit $n+1$ n’est pas premier, alors, il existe deux entiers $p$ et $q$ avec $2 \le p \le n$ et $2 \le q \le n$ tels que $n+1=pq$ . Or, $\mathcal{P}_p$ et $\mathcal{P}_q$ sont vraies, donc $p$ et $q$ sont des produits de nombres premiers et $n+1$ aussi. $\mathcal{P}_{n+1}$

est encore vraie.

D’après le principe de récurrence forte, la propriété est vraie pour tout $n\in\mathbb{N}$ , $n\ge 2$

Cet article est extrait de l’ouvrage Maths MPSI-MP2I. Tout-en-un : cours, méthodes, entraînement et corrigés (éditions Vuibert, juin 2021) écrit par E. Thomas, S. Bellec, G. Boutard. ISBN n°9782311408720