Raisonnement par récurrence

L'ordre de ℕ, l'axiome du plus petit élément, et les principes de récurrence qui s'en déduisent.

L'ordre de ℕ¶

Remarque (ℕ, ≤) est totalement ordonné¶

ℕ muni de ≤ est un ensemble totalement ordonné, et ≤ est compatible avec la somme et le produit : c'est l'ordre des réels, restreint aux entiers naturels.

Axiome Plus petit élément¶

Toute partie non vide de ℕ admet un plus petit élément.

Théorème Plus grand élément¶

Toute partie non vide et majorée de ℕ admet un plus grand élément. (Le cours l'admet aussi comme axiome ; il se déduit du précédent.)

Démonstration.

Soit A une partie non vide et majorée de ℕ. L'ensemble de ses majorants est une partie non vide de ℕ : d'après l'axiome du plus petit élément, il a un plus petit élément m.

Supposons m ∉ A. Comme A n'est pas vide, il contient un a, et a < m, donc m > 0. Alors tout a ∈ A vérifie a ≤ m − 1 : m − 1 serait un majorant plus petit que m, ce qui est impossible.

Donc m ∈ A : m est le plus grand élément de A.

Récurrence simple¶

Théorème Principe de récurrence simple¶

Soit P(n) une propriété dépendant de n ∈ ℕ telle que P(0) soit vraie et ∀n ∈ ℕ, P(n) ⟹ P(n + 1). Alors pour tout entier naturel n, P(n) est vraie.

Démonstration.

Supposons la conclusion fausse : il existe n₀ tel que ¬P(n₀). On considère alors A = {k ∈ ℕ | ¬P(k)}.

0 ∉ A, et d'autre part A est une partie non vide de ℕ (n₀ ∈ A). D'après l'axiome qui précède, A admet un plus petit élément k₀, et k₀ > 0.

k₀ − 1 ∉ A, donc P(k₀ − 1) est vraie. Or ∀n ∈ ℕ, P(n) ⟹ P(n + 1), donc P(k₀) est vraie : c'est une contradiction, car k₀ ∈ A.

Corollaire Récurrence à partir d'un rang a¶

Soit a ∈ ℤ et P(n) une propriété dépendant de l'entier n ≥ a, telle que P(a) et ∀n ≥ a, P(n) ⟹ P(n + 1). Alors pour tout entier n ≥ a, P(n) est vraie.

Exemple : Comparer une puissance de 2 et un carré.

Démonstration.

On pose Q(m) = P(m + a) pour m ∈ ℕ, et on applique le théorème de récurrence à Q(m).

Exemple Comparer une puissance de 2 et un carré¶

Montrons que ∀n ≥ 4, 2ⁿ ≥ n².

Illustre : Récurrence à partir d'un rang a.

Solution.

Initialisation : pour n = 4, 2ⁿ = 16 et n² = 16.

Hérédité : supposons 2ⁿ ≥ n² avec n ≥ 4. Alors

2^{n + 1}=2 × 2ⁿ≥2n²(hypothèse de récurrence)≥(n + 1)²(voir ci-dessous)

En effet, 2n² − (n + 1)² = n² − 2n − 1. Le trinôme x² − 2x − 1 a pour discriminant 8, et pour racines 1 − 2 et 1 + 2, qui est strictement inférieure à 3 : il est donc strictement positif en n, puisque n ≥ 4.

Récurrence forte¶

Corollaire Récurrence forte (ou multiple)¶

Soit P(n) une assertion qui dépend de l'entier naturel n, telle que P(0) et ∀n ∈ ℕ, (∀k ∈ ⟦0, n⟧, P(k)) ⟹ P(n + 1), c'est-à-dire P(0) ∧ … ∧ P(n) ⟹ P(n + 1). Alors ∀n ∈ ℕ, P(n).

Exemples : Produit de nombres premiers, Somme de puissances de 2, Une suite sous-additive.

Démonstration.

On applique la récurrence simple à Q(n) : « P(0) ∧ … ∧ P(n) ». Q(0) est P(0), et si Q(n) est vraie, l'hypothèse donne P(n + 1), donc Q(n + 1). Ainsi Q(n), donc P(n), est vraie pour tout n.

Exemple Produit de nombres premiers¶

Tout entier n ≥ 2 s'écrit comme produit de nombres premiers.

Illustre : Récurrence forte (ou multiple).

Solution.

Notons P(n) : « n s'écrit comme produit de nombres premiers ».

Initialisation : 2 est un nombre premier.

Hérédité : supposons P(2), …, P(n) avec n ≥ 2, et considérons n + 1. 1er cas : n + 1 est premier. 2e cas : il existe des entiers a et b compris entre 2 et n tels que n + 1 = ab ; comme on a P(a) et P(b), n + 1 est un produit de nombres premiers : on a P(n + 1).

Conclusion : par le principe de récurrence forte, on en déduit la propriété voulue.

Exemple Somme de puissances de 2¶

Tout entier naturel n ≠ 0 s'écrit comme somme de puissances de 2 distinctes.

Illustre : Récurrence forte (ou multiple).

Solution.

Initialisation : 1 = 1.

Hérédité : supposons la propriété vraie du rang 1 au rang n, et considérons n + 1.

1er cas : n + 1 est une puissance de 2. 2e cas : il existe k ∈ ℕ tel que 2^k < n + 1 < 2^{k + 1}. Alors n + 1 = 2^k + r avec 0 < r < 2^k, et r ≤ n : r est une somme de puissances de 2 distinctes, qui sont toutes strictement inférieures à 2^k. En leur ajoutant 2^k, on écrit n + 1 comme somme de puissances de 2 distinctes.

Exemple Une suite sous-additive¶

Soit (a_n)_{n ≥ 1} une suite de réels telle que pour tous entiers naturels non nuls i et j, a_{i + j} ≤ a_i + a_j. Montrons que pour tout n ∈ ℕ^*, ∑nk=1 a_kk ≥ a_n.

Illustre : Récurrence forte (ou multiple).

Solution.

Initialisation : a₁ ≥ a₁.

Hérédité : supposons la propriété vraie aux rangs 1, 2, …, n. En ajoutant ces n inégalités, chaque a_kk apparaît n − k + 1 fois :

∑nk=1 (n − k + 1)a_kk≥∑nk=1 a_k

On ajoute ∑nk=1 a_k de part et d'autre, en écrivant la seconde somme à l'envers :

(n + 1)∑nk=1 a_kk≥∑nk=1 (a_k + a_{n + 1 − k})≥na_{n + 1}(car a_{n + 1} ≤ a_k + a_{n + 1 − k})

On ajoute a_{n + 1} de part et d'autre : (n + 1)∑n + 1k=1 a_kk ≥ (n + 1)a_{n + 1}, et on divise par n + 1.

Exemple : Petite application : parties entières.

Exemple Petite application : parties entières¶

Montrons que ∀x ∈ ℝ₊, ∀n ∈ ℕ, ∑nk=1 ⌊kx⌋k ≤ ⌊nx⌋.

Illustre : Une suite sous-additive.

Solution.

La suite (−⌊nx⌋)_{n ≥ 1} est sous-additive, car ⌊ix⌋ + ⌊jx⌋ ≤ ⌊(i + j)x⌋ : on applique l'exemple précédent, puis on change de signe. (Pour n = 0, la somme est vide.)