Quelques raisonnements classiques

Plan du chapitre "Raisonner"

Le raisonnement par récurrence

On admet les propriétés de l’ensemble ${\mathbb{N}}$ des entiers naturels.
En particulier, on admet les résultats suivants, pour toute partie ${A}$ de ${\mathbb{N}}$ :

si ${A}$ est non vide, alors ${A}$ possède un élément minimum ${a}$ (il est caractérisé par : ${\forall\,b\in A,\;a\le b}$ ).
si de plus ${A}$ est majorée, alors possède un élément maximum.
(dire que ${A}$ est majorée, c’est dire qu’il existe ${n}$ dans ${\mathbb{N}}$ tel que : ${\forall\,a\in A,\;a\le n}$ )

Proposition (récurrence simple)
Soit

{\mathcal{P}}

une propriété (un « prédicat ») portant sur les entiers naturels.
Soit

{n_{0}}

un entier naturel. On suppose que la proposition

{\mathcal{P}(n_{0})}

est vraie.
On suppose également, pour tout entier

{n\ge n_{0}}

, que l’implication

{\mathcal{P}(n)\Rightarrow\mathcal{P}(n+1)}

est vraie.
Alors la proposition

{\mathcal{P}(n)}

est vraie pour tout entier

{n\ge n_{0}}

Voici donc comment montrer qu’une propriété ${\mathcal{P}(n)}$ est vraie à partir d’un entier ${n_0}$ :

On vérifie que l’entier ${n_{0}}$ satisfait à la propriété: c’est le pas initial de la récurrence.
La plupart du temps, on a bien sûr ${n_{0}=0}$ , ou ${n_{0}=1}$ …
On se donne ensuite un entier ${n\ge n_{0}}$ , et on suppose que ${\mathcal{P}(n)}$ est vraie (c’est hypothèse de récurrence). On démontre alors que ${\mathcal{P}(n+1)}$ est vraie (c’est le « passage du rang ${n}$ au rang ${n+1}$ »). On exprime l’implication ${\mathcal{P}(n)\Rightarrow\mathcal{P}(n+1)}$ en disant que la propriété ${\mathcal{P}}$ est héréditaire.
On conclut en annonçant que, par récurrence, la propriété est vraie pour tout entier ${n\ge n_{0}}$ .

Une variante réside dans la manière d’avancer dans la récurrence. Il arrive en effet que l’hypothèse ${\mathcal{P}(n)}$ seule soit insuffisante pour démontrer ${\mathcal{P}(n+1)}$ . Le cas le plus fréquent est celui de la récurrence double, où le pas initial et l’hypothèse de récurrence portent sur deux entiers consécutifs.

Proposition (récurrence de pas 2)
Soit

{\mathcal{P}}

une propriété portant sur les entiers naturels.
Soit

{n_{0}}

un entier naturel. On suppose que

{\mathcal{P}(n_{0})}

{\mathcal{P}(n_{0}+1)}

sont vraies.
On suppose que pour tout

{n\ge n_{0}}

, l’implication « ${(\mathcal{P}(n)\;\text{et}\;\mathcal{P}(n+1))\Rightarrow\mathcal{P}(n+2)}$ » est vraie.
Alors la proposition

{\mathcal{P}(n)}

est vraie pour tout

{n\ge n_{0}}

Il reste une autre variante importante, le raisonnement par récurrence forte : pour prouver

{\mathcal{P}(n+1)}

, on peut en effet utiliser tout ou partie des hypothèses

{\mathcal{P}(n_{0}),\mathcal{P}(n_{0}+1),\ldots,\mathcal{P}(n)}

Proposition (récurrence forte)
Soit

{\mathcal{P}}

une propriété portant sur les entiers naturels.
Soit

{n_{0}\in\mathbb{N}}

. On suppose

{\mathcal{P}(n_{0})}

vraie.
On suppose que pour tout

{n\ge n_{0}}

, l’implication

{(\mathcal{P}(n_{0})\;\text{et}\;\mathcal{P}(n_{0}+1)\cdots\;\text{et}\;\mathcal{P}(n))\Rightarrow\mathcal{P}(n+1)}

est vraie. Alors

{\mathcal{P}(n)}

est vraie pour tout

{n\ge n_{0}}

Voici enfin quelques conseils pour « réussir » un raisonnement par récurrence:

Pour voir la suite de ce contenu, vous devez :

avoir une souscription active sur mathprepa
et être connecté au site

Pour poursuivre votre exploration, vous pouvez :

revenir à la page d'accueil
ou tester la page d'extraits libres
ou consulter le plan du site

Page précédente : quantificateurs et rédaction
Page suivante : parties d’un ensemble