Partie 3

Récurrence double, récurrence forte, analyse-synthèse et ensemble ℕ

La récurrence simple ne suffit pas toujours : certaines propriétés ont besoin de deux rangs pour démarrer, d'autres de tous les rangs précédents. On referme ensuite le chapitre en revenant sur la structure même de \(\mathbb{N}\) — son ordre, et le principe du plus petit élément, qui est au fond une autre façon d'énoncer la récurrence.

Récurrence double

Propriété

Soit \(P(n)\) une proposition qui dépend d'un entier \(n\in\mathbb{N}\). On suppose que :

1) \(P(0)\) et \(P(1)\) sont vraies ;

2) \(\forall n\in\mathbb{N},\quad P(n) \text{ et } P(n+1) \Longrightarrow P(n+2)\).

Alors \(P(n)\) est vraie pour tout \(n\in\mathbb{N}\).

Exemple

Énoncé

Soit \((u_n)_{n\geq0}\) définie par \(u_0=0\), \(u_1=1\) et, pour tout \(n\in\mathbb{N}\), \(u_{n+2}=3u_{n+1}-2u_n\). Montrer que \(\forall n\in\mathbb{N},\ u_n=2^n-1\).

Pourquoi deux initialisations ?

La relation \(u_{n+2}=3u_{n+1}-2u_n\) a besoin des deux rangs précédents pour calculer le suivant : une seule valeur de départ ne suffirait pas à amorcer le calcul.

Récurrence forte

Propriété

Soit \(P(n)\) une proposition qui dépend d'un entier \(n\geq n_0\) (\(n_0\in\mathbb{N}\)). On suppose que :

1) \(P(n_0)\) est vraie ;

2) \(\forall n\geq n_0,\quad P(n_0)\wedge P(n_0+1)\wedge\cdots\wedge P(n) \Longrightarrow P(n+1)\).

Alors \(P(n)\) est vraie pour tout \(n\geq n_0\).

Exemple 1 — décomposition binaire d'un entier

Énoncé

Montrer que \(\forall n\in\mathbb{N}^*,\ \exists!\,(p,q)\in\mathbb{N}^2, \quad n=2^p(2q+1)\).

Exemple 2 — tout entier ≥ 2 admet un diviseur premier

Énoncé

Montrer que tout entier \(n\geq2\) admet au moins un diviseur premier.

Le raisonnement par analyse-synthèse

Principe

Analyse : on suppose qu'un objet \(x\) vérifie la propriété voulue, et on en tire des contraintes de plus en plus précises sur \(x\), jusqu'à ne plus laisser qu'un nombre restreint de candidats possibles.

Synthèse : on reprend chaque candidat trouvé et on vérifie, indépendamment de l'analyse, qu'il satisfait bien la propriété de départ.

La clé à retenir

Analyse = unicité · Synthèse = existence

L'analyse seule ne prouve rien : elle réduit seulement le champ des possibles. Sans la synthèse, un candidat resterait une simple conjecture — c'est elle qui transforme la piste en preuve.

Où l'utiliser

C'est la méthode de référence pour les équations fonctionnelles : on ne sait pas a priori à quoi ressemble la fonction cherchée, alors l'analyse en dévoile la forme (souvent en évaluant l'équation en des points bien choisis, comme \(0\), \(1\), ou en dérivant), et la synthèse confirme que cette forme convient. Les quatre applications ci-dessous en sont des exemples classiques.

Applications — équations fonctionnelles

Quatre équations résolues par analyse-synthèse : l'analyse évalue l'équation en des points bien choisis pour deviner \(f\), puis la synthèse vérifie.

Application 1 · équation de Cauchy

Énoncé

Déterminer toutes les fonctions \(f:\mathbb{R}\to\mathbb{R}\) dérivables telles que, pour tous \(x,y\in\mathbb{R}\) :

\[ f(x+y)=f(x)+f(y) \]

Application 2 · équation mêlant somme et produit

Énoncé

Déterminer toutes les fonctions \(f:\mathbb{R}\to\mathbb{R}\) telles que, pour tous \(x,y\in\mathbb{R}\) :

\[ f(x)f(y)-f(xy)=x+y \]

Application 3 · substitution \(x\mapsto 1-x\)

Énoncé

Déterminer toutes les fonctions \(f:\mathbb{R}\to\mathbb{R}\) vérifiant, pour tout \(x\in\mathbb{R}\) :

\[ f(x)+x\,f(1-x)=1+x \]

Application 4 · morphismes de \(\mathbb{C}\) fixant les réels

Énoncé

Déterminer toutes les fonctions \(f:\mathbb{C}\to\mathbb{C}\) telles que :

1)\(\forall x\in\mathbb{R},\ f(x)=x\) ;

2)\(\forall z,z'\in\mathbb{C},\ f(z+z')=f(z)+f(z')\) ;

3)\(\forall z,z'\in\mathbb{C},\ f(zz')=f(z)f(z')\).

L'ensemble ℕ

5.1 — Ordre usuel de ℕ

Propriété

\(\forall m,n\in\mathbb{N},\quad m< n \Longrightarrow m+1\leq n\).

Définitions

Une application \(f:\mathbb{N}\to\mathbb{R}\) est dite croissante (resp. strictement croissante) si :

\[ \forall m,n\in\mathbb{N},\quad m\leq n \Longrightarrow f(m)\leq f(n) \qquad\big(\text{resp. } m < n \Longrightarrow f(m) < f(n)\big) \]

De même, \(f\) est dite décroissante (resp. strictement décroissante) si \( m\leq n \Rightarrow f(m) \geq f(n) \) (resp. \(m < n \Rightarrow f(m)>f(n)\)).

Propriété

Une application \(f:\mathbb{N}\to\mathbb{R}\) est croissante (resp. strictement croissante) si, et seulement si :

\[ \forall n\in\mathbb{N},\quad f(n)\leq f(n+1) \qquad\big(\text{resp. } f(n) < f(n+1)\big) \]

Il suffit donc de comparer chaque terme au suivant, pas à tous les autres.

Exemples

Énoncé

1) \(\displaystyle f(n)=\sum_{k=1}^{n}\frac1k\), \(n\in\mathbb{N}^*\).

2) \(\displaystyle f(n)=\frac{n^n}{n!}\), \(n\in\mathbb{N}^*\).

3) \(\displaystyle f(n)=\frac{1}{n+1}+\frac{1}{n+2}+\cdots+\frac{1}{n+n}\).

Exercice

Énoncé

Soit \(f:\mathbb{N}\to\mathbb{N}\) strictement croissante.

1)Montrer que \(\forall n\in\mathbb{N},\ f(n)\geq n\).

2)Si \(f\) est bijective, montrer que \(f=\mathrm{id}_{\mathbb{N}}\).

5.2 — Principe du plus petit élément

Propriété

Toute partie non vide de \(\mathbb{N}\) admet un plus petit élément.

Remarque

Le principe du plus petit élément est équivalent au principe de récurrence.

Exemple — irrationalité de √2 par descente infinie

Énoncé

Montrer que \(\sqrt2\notin\mathbb{Q}\), en utilisant le principe du plus petit élément (variante de la preuve par l'absurde vue en Partie 2).

Propriété — principe de descente infinie

Il n'existe pas de fonction \(f:\mathbb{N}\to\mathbb{N}\) strictement décroissante.

Propriété

Toute partie non vide et majorée de \(\mathbb{N}\) admet un plus grand élément.

Exemple

Énoncé

Montrer que \(\forall N\in\mathbb{N}^*,\ \exists!\,n\in\mathbb{N}, \quad 2^n\leq N < 2^{n+1}\).

Résumé

Récurrence double : deux initialisations (\(P(0)\) et \(P(1)\)), puis \(P(n)\text{ et }P(n+1)\Rightarrow P(n+2)\) — pour les relations qui utilisent deux rangs précédents.
Récurrence forte : une seule initialisation, mais l'hérédité peut s'appuyer sur tous les rangs de \(n_0\) à \(n\).
Analyse-synthèse : l'analyse restreint les candidats (elle prouve l'unicité), la synthèse vérifie qu'ils conviennent (elle prouve l'existence).
Une fonction \(f:\mathbb{N}\to\mathbb{R}\) est (strictement) croissante si, et seulement si, \(f(n)\leq f(n+1)\) (resp. \(f(n)
Toute partie non vide de \(\mathbb{N}\) admet un plus petit élément ; toute partie non vide et majorée admet un plus grand élément.
Le principe du plus petit élément et le principe de récurrence sont équivalents ; le principe de descente infinie (aucune fonction \(\mathbb{N}\to\mathbb{N}\) strictement décroissante) en découle directement.

« Deux rangs pour démarrer, tous les rangs pour avancer. »