School 47
Se connecter

La démonstration par récurrence : prouver l'infini pas à pas

Terminale · Mathématiques · environ 15 min

Imagine une échelle infinie posée contre un mur. Comment prouver que tu peux atteindre tous les barreaux, alors qu'ils sont en nombre illimité ? Tu ne peux évidemment pas grimper un par un jusqu'à l'infini... Il te suffit de démontrer deux choses : je peux atteindre le premier barreau, et depuis n'importe quel barreau, je sais monter au suivant. Si ces deux faits sont vrais, alors aucun barreau n'est hors de portée !

Suites arithmétique et géométrique Un repère où l'axe horizontal porte le rang n de la suite et l'axe vertical la valeur du terme. Les points bleus d'une suite arithmétique sont parfaitement alignés : on ajoute le même nombre r pour passer d'un terme au suivant. Les points orange d'une suite géométrique montent en s'accélérant, sur une courbe : on multiplie par le même nombre q à chaque étape. La suite arithmétique croît d'un pas constant, la géométrique s'emballe. n uₙ arithmétique : + r géométrique : × q uₙ₊₁ = uₙ + r · uₙ₊₁ = uₙ × q
L'échelle infinie : chaque barreau dépend du précédent, comme uₙ₊₁ dépend de uₙ

C'est exactement l'idée du raisonnement par récurrence, un outil puissant pour démontrer qu'une propriété est vraie pour tous les entiers n à partir d'un certain rang.

Le principe en 3 étapes

Soit P(n) une propriété qui dépend de l'entier n. Pour prouver qu'elle est vraie pour tout n ≥ n₀ :

L'équation : la balance Une balance à deux plateaux. À gauche le plateau porte x + 3, à droite il porte 8 : les deux plateaux sont à la même hauteur, la balance est équilibrée. Résoudre l'équation, c'est faire la même opération des deux côtés pour garder l'équilibre. x + 3 = 8 x + 3 8 on garde toujours l'équilibre
La récurrence : maintenir l'équilibre entre ce qu'on suppose vrai et ce qu'on doit prouver

1. Initialisation : on vérifie que P(n₀) est vraie (le premier barreau).

2. Hérédité : on suppose que P(n) est vraie pour un entier n quelconque (c'est l'hypothèse de récurrence), et on démontre alors que P(n+1) est vraie (je monte au barreau suivant).

3. Conclusion : par le principe de récurrence, P(n) est vraie pour tout n ≥ n₀.

! Les deux étapes sont indispensables. Oublier l'initialisation est une erreur classique !

Exemple 1 : une somme

Montrons que pour tout n ≥ 1 : 1 + 2 + 3 + dots + n = n(n+1)2.

Initialisation (n=1) : à gauche, 1. À droite, 1 × 22 = 1.

Hérédité : supposons 1+2+dots+n = n(n+1)2. Alors :

1+2+dots+n+(n+1) = n(n+1)2 + (n+1) = (n+1)(n2+1) = (n+1)(n+2)2

C'est bien la formule au rang n+1.

Conclusion : la propriété est vraie pour tout n ≥ 1.

Exemple 2 : une inégalité

Montrons que pour tout n ≥ 0 : 2ⁿ ≥ n+1.

Initialisation (n=0) : 2⁰ = 1 et 0+1 = 1, donc 1 ≥ 1.

Hérédité : supposons 2ⁿ ≥ n+1. Alors 2ⁿ⁺¹ = 2 × 2ⁿ ≥ 2(n+1) = 2n+2. Or 2n+2 ≥ n+2 (car n ≥ 0), donc 2ⁿ⁺¹ ≥ (n+1)+1.

Conclusion : vrai pour tout n ≥ 0.

À retenir

  • La récurrence prouve qu'une propriété P(n) est vraie pour tout entier à partir d'un rang n₀.
  • Trois étapes obligatoires : initialisation, hérédité, conclusion.
  • L'hypothèse de récurrence = on suppose P(n) vraie pour passer à P(n+1).
  • Sans initialisation, la démonstration est fausse : on ne saurait pas où commencer l'échelle.
  • Rédige toujours proprement : annonce chaque étape par son nom.

Corrections

Exercice 1 : On suppose que P(n) est vraie pour un entier n fixé quelconque (l'hypothèse de récurrence), et on démontre que P(n+1) est alors vraie. On ne suppose pas que P est vraie pour tous les entiers !

Exercice 2 : Init. (n=1) : 3¹ - 1 = 2, divisible par 2. Hérédité : supposons 3ⁿ - 1 = 2k (k entier). Alors 3ⁿ⁺¹-1 = 3 × 3ⁿ - 1 = 3(2k+1) - 1 = 6k+2 = 2(3k+1), divisible par 2. Conclusion : vrai pour tout n ≥ 1.

Exercice 3 : Init. (n=0) : u₀ = 2 ≥ 2. Hérédité : supposons uₙ ≥ 2. Alors uₙ₊₁ = 2uₙ + 3 ≥ 2 × 2 + 3 = 7 ≥ 2. Conclusion : uₙ ≥ 2 pour tout n ≥ 0.