Bases mathématiques-L’ensemble des entiers naturels-Principe de récurrence-MPSI
Principe de récurrence
Définition
Bases mathématiques-L’ensemble des entiers naturels-Principe de récurrence-MPSI
Un prédicat sur $\mathbb{N}$ est une application de $\mathbb{N}$ dans l’ensemble des booléens : vrai et faux.
Proposition
Principe de récurrence
Soit $\mathscr{P}$ un prédicat sur $\mathbb{N}$ tel que :
– $\mathscr{P}(0)$ est vrai;
– pour tout $n \in \mathbb{N}$, si $\mathscr{P}(n)$ est vrai, alors $\mathscr{P}(n+1)$ est vrai.
Alors, $\mathscr{P}(n)$ est vrai pour tout $n \in \mathbb{N}$.
En remplaçant la première condition par $\mathscr{P}(m)$ est vrai, on obtient la conclusion $\mathscr{P}(n)$ est vrai pour tout entier $n \geq m$.
Démonstration
Considérons l’ensemble $A=\{n \in \mathbb{N}, \mathscr{P}(n)$ est faux $\}$. Si $A$ est non vide, il admet un plus petit élément $m=\min A$ qui est différent de 0 . Alors, $m-1 \notin A$ et donc par la seconde propriété, $m \notin A$ : contradiction $\operatorname{donc} A$ est vide.
Proposition 1,43. Principe de récurrence forte
Soit $\mathscr{P}$ un prédicat sur $\mathbb{N}$ tel que :
– $\mathscr{P}(0)$ est vrai;
– pour tout $n \in \mathbb{N}$, si $\mathscr{P}(k)$ est vrai pour tout $k \leq n$, alors $\mathscr{P}(n+1)$ est vrai.
Alors, $\mathscr{P}(n)$ est vrai pour tout $n \in \mathbb{N}$.
La preuve est identique à la précédente avec le prédicat $\mathscr{Q}$ tel que $\mathscr{Q}(n)$ est vrai si, et seulement si, $\mathscr{P}(k)$ est vrai pour tout $k \leq n$.
Regardons quelques exemples.
Exemple
Montrons que tout entier supérieur à 2 admet une décomposition comme produit de nombres premiers.
Posons, pour tout $n \geq 2, \mathscr{P}(n):$ « $n$ admet une décomposition en produit de nombres premiers».
– $\mathscr{P}(2)$ est vrai car 2 est un nombre premier.
– Soit $n \geq 2$. Supposons $\mathscr{P}(k)$ vrai pour tout $k \leq n$ et montrons $\mathscr{P}(n+1)$ par disjonction de cas :
– Si $n+1$ est premier, alors $\mathscr{P}(n+1)$ est vrai.
– Si $n+1$ est composé, alors il existe $p$ et $q$ entre 2 et $n$ tels que $n+1=p . q$. Or, par hypothèse de récurrence, $\mathscr{P}(p)$ et $\mathscr{P}(q)$ sont vrais donc $n+1$ est un produit de nombres premiers et $\mathscr{P}(n+1)$ est vrai.
On conclut avec le principe fort de récurrence.
Exemple
Notons, pour tout $n \in \mathbb{N} \backslash\{0\}, S_n$ la somme des cubes des entiers entre 1 et $n$ et montrons par récurrence sur $n \in \mathbb{N} \backslash\{0\}$ que $S_n=\left(\frac{n(n+1)}{2}\right)^2$.
Définissons, pour tout $n \in \mathbb{N} \backslash\{0\}, \mathscr{P}(n): « S_n=\left(\frac{n(n+1)}{2}\right)^2 »$.
– $\mathscr{P}(1)$ est vrai car $1=\left(\frac{1(1+1)}{2}\right)^2$.
– Soit $n \in \mathbb{N} \backslash\{0\}$. Supposons $\mathscr{P}(n)$ vrai et montrons $\mathscr{P}(n+1)$
$$
\begin{aligned}
S_{n+1} & =S_n+(n+1)^3 \\
& =\left(\frac{n(n+1)}{2}\right)^2+(n+1)^3 \\
& =(n+1)^2\left(\frac{n^2}{4}+n+1\right)=\frac{(n+1)^2(n+2)^2}{4} .
\end{aligned}
$$
D’où le résultat.
On conclut avec le principe de récurrence.
Exemple
Soit $\left(F_n\right)_n$ la suite de Fibonacci définie par $F_0=F_1=1$ et, pour tout $n \in \mathbb{N}, F_{n+2}=F_{n+1}+F_n$. Définissons, pour tout $n \in \mathbb{N}, S_n$ la somme des termes de cette suite d’indice inférieur ou égal à $n$. Montrons par récurrence sur $n \in \mathbb{N}$, la propriété $\mathscr{P}(n):$ « $S_n=F_{n+2}-1$ ».
– $\mathscr{P}(0)$ est vrai car $F_0=F_2-F_1=F_2-1$.
– Soit $n \in \mathbb{N}$. Supposons $\mathscr{P}(n)$ vrai et montrons $\mathscr{P}(n+1)$.
$$
\begin{aligned}
S_{n+1} & =S_n+F_{n+1} \\
& =F_{n+2}-1+F_{n+1}=F_{n+3}-1 .
\end{aligned}
$$
On conclut avec le principe de récurrence.
En fait, on remarque que l’on peut procéder « par récurrence» sur d’autres ensembles que $\mathbb{N}$ et que ce principe d’induction sera fort utile en informatique.
