Mathématiques > Logique et Raisonnement Mathématique > Types de Raisonnement > Récurrence

La Démonstration par Récurrence

Comprendre et maîtriser la démonstration par récurrence : principe, étapes, exemples et exercices pour le lycée.

Introduction au Principe de Récurrence

La démonstration par récurrence est une méthode de raisonnement puissante utilisée en mathématiques pour prouver qu'une propriété est vraie pour tous les nombres entiers naturels (ou à partir d'un certain rang). Elle est particulièrement utile lorsque la propriété dépend d'un indice entier. Imaginez une rangée infinie de dominos. Si vous poussez le premier domino, et que chaque domino, en tombant, fait tomber le suivant, alors tous les dominos finiront par tomber. C'est l'idée de base de la récurrence.

Les Étapes Clés de la Récurrence

Une démonstration par récurrence se déroule généralement en trois étapes :

1. Initialisation : On montre que la propriété est vraie pour le premier entier (souvent 0 ou 1). C'est comme vérifier que le premier domino peut effectivement être poussé.

2. Hérédité : On suppose que la propriété est vraie pour un entier *k* quelconque (l'hypothèse de récurrence) et on montre qu'elle est alors vraie pour l'entier suivant *k+1*. C'est comme prouver que si un domino tombe, il fera tomber le suivant.

3. Conclusion : Si les deux premières étapes sont vérifiées, alors la propriété est vraie pour tous les entiers à partir du premier entier considéré. C'est comme affirmer que tous les dominos vont tomber.

Exemple Concret : Somme des Entiers de 1 à n

Démontrons par récurrence que pour tout entier naturel *n*, la somme des entiers de 1 à *n* est égale à *n(n+1)/2*. C'est à dire: 1 + 2 + ... + n = n(n+1)/2.

1. Initialisation : Pour *n=1*, on a 1 = 1(1+1)/2 = 1, donc la propriété est vraie pour *n=1*.

2. Hérédité : Supposons que la propriété est vraie pour un entier *k* quelconque. C'est à dire: 1 + 2 + ... + k = k(k+1)/2 (Hypothèse de récurrence). Montrons qu'elle est vraie pour *k+1*. On veut donc montrer que : 1 + 2 + ... + (k+1) = (k+1)(k+2)/2. Partons du membre de gauche et utilisons l'hypothèse de récurrence : 1 + 2 + ... + (k+1) = (1 + 2 + ... + k) + (k+1) = k(k+1)/2 + (k+1) = [k(k+1) + 2(k+1)]/2 = (k+1)(k+2)/2. On a bien montré que si la propriété est vraie pour *k*, elle est vraie pour *k+1*.

3. Conclusion : Par le principe de récurrence, la propriété est vraie pour tout entier naturel *n*.

Variantes et Précautions

Récurrence Forte : Dans certains cas, pour démontrer l'hérédité, il peut être nécessaire de supposer que la propriété est vraie pour tous les entiers jusqu'à *k*, et non seulement pour *k*. On parle alors de récurrence forte.

Attention à l'Initialisation : Il est crucial de bien choisir la valeur initiale pour laquelle on vérifie la propriété. La récurrence ne fonctionne que si l'initialisation est correcte.

La rigueur est essentielle : Chaque étape doit être justifiée rigoureusement pour éviter les erreurs.

Exercices d'Application

Voici quelques exemples d'exercices pour vous entraîner :

1. Démontrer que pour tout entier *n* supérieur ou égal à 1, 12 + 22 + ... + n2 = n(n+1)(2n+1)/6.

2. Démontrer que pour tout entier *n* supérieur ou égal à 0, 2n > n.

3. Démontrer que pour tout entier *n* supérieur ou égal à 3, n2 > 2n + 1.

Ce qu'il faut retenir

  • Principe de la récurrence : Prouver une propriété pour un entier initial et montrer que si elle est vraie pour un entier k, elle est vraie pour k+1.
  • Étapes : Initialisation, Hérédité, Conclusion.
  • Initialisation : Vérifier la propriété pour la plus petite valeur possible de n.
  • Hérédité : Supposer la propriété vraie pour n=k et la démontrer pour n=k+1.
  • Conclusion : Généraliser la propriété pour tous les entiers n à partir de la valeur initiale.
  • Récurrence Forte : Nécessaire lorsque l'hérédité dépend de plusieurs valeurs précédentes.

← Introduction à la Logique Propositionnelle : Propositions et Connecteurs Le Raisonnement par Déduction en Mathématiques →

FAQ

  • Pourquoi l'étape d'initialisation est-elle importante ?

    L'étape d'initialisation est cruciale car elle établit le point de départ de la chaîne de raisonnement. Sans une base solide, la récurrence ne peut pas fonctionner correctement. Imaginez que le premier domino ne puisse pas être poussé : aucun domino ne tombera, même si les suivants sont correctement alignés.
  • Quelle est la différence entre récurrence simple et récurrence forte ?

    Dans la récurrence simple, on suppose que la propriété est vraie pour *k* et on montre qu'elle est vraie pour *k+1*. Dans la récurrence forte, on suppose que la propriété est vraie pour tous les entiers jusqu'à *k*, ce qui peut être nécessaire pour démontrer l'hérédité dans certains cas.