La démonstration par récurrence

Ah, la démonstration par récurrence ! Elle a fait pâlir plus d’un élève de lycée… Et pourtant, ce principe de démonstration est assez intuitif, et surtout facile à appliquer, une fois bien compris. Reprenons donc depuis le début.

 

La démonstration par récurrence, ou le principe des dominos

Oublions un instant le formalisme mathématique, et revenons à une dimension plus “manuelle”.

Imaginons un axe sur lequel seraient alignés une infinité de dominos, posés verticalement. Numérotons ces dominos dans l’ordre : 0, 1, 2, 3 etc. L’objectif est de faire tomber tous les dominos.

Pour cela, il faut que deux conditions soient réunies :

  1. Les dominos doivent être placés suffisamment près les uns des autres, de sorte que si le domino numéro n tombe, alors le domino suivant (le numéro n+1) tombe également.
  2. Il faut faire tomber le domino numéro 0 (sinon il ne se passe rien du tout…) !

Si ces deux conditions sont réunies, alors c’est gagné : tous les dominos tombent !

 

 

Intuitif, non ? Eh bien il s’agit exactement du principe de la démonstration par récurrence. Essayons de le comprendre en reformulant cet exemple des dominos en termes mathématiques.

La démonstration par récurrence sert à démontrer des propriétés qui portent sur les entiers naturels, c’est-à-dire des propriétés de la forme : “Pour tout n ∈ N, blablabla” . Dans notre exemple ci-dessus, la propriété à démontrer serait : “Pour tout n ∈ N, le domino numéro n tombe.” .

On note H(n) une telle propriété au rang n. Dans notre exemple, on aurait donc :

H(n) : “Le domino numéro n tombe.”

La démonstration par récurrence consiste :

  1. D’abord, à vérifier que la propriété est vraie au rang 0 (i.e. on vérifie que H(0) est vraie). Dans notre exemple des dominos, cela revient à vérifier que le premier domino (le domino numéro 0) tombe. Cette étape s’appelle l’initialisation.
  2. Ensuite, à vérifier que si la propriété est vraie à un rang n, alors elle sera aussi vraie au rang n+1 (i.e. on vérifie que si H(n) est vraie, alors H(n+1) est aussi vraie). Dans notre exemple, cela revient à constater que, si le domino numéro n tombe, comme la distance entre les dominos est suffisamment petite, alors le domino numéro n+1 tombe également. Cette étape s’appelle l’hérédité.

Si ces deux étapes sont vérifiées, alors la propriété sera vraie pour tous les entiers naturels (on aura démontré que pour tout n ∈ NH(n) est vraie). Dans notre exemple, cela revient à dire que tous les dominos tombent (car pour tout n ∈ N, le domino numéro n tombe). C’est la conclusion du raisonnement par récurrence.

 

Méthodologie : rédiger efficacement une démonstration par récurrence

Il faut penser à tenter une démonstration par récurrence lorsqu’on est en présence d’une propriété qui se “propage” de proche en proche sur les entiers naturels (comme la chute de nos dominos…). Toutefois, il n’est pas toujours facile d’identifier de telles propriétés… Il faut donc toujours avoir en tête que l’on dispose de la démonstration par récurrence dans notre “boite à outils mathématiques”, et envisager de l’utiliser si l’on nous demande de démontrer une propriété portant sur les entiers naturels qui ne nous semble pas facile à prouver de manière “directe”.

Une fois identifiée une démonstration à faire par récurrence, il faut :

  1. Énoncer clairement la propriété H(n) pour tout n ∈ N.
  2. Faire l’initialisation : on démontre H(0).
  3. Démontrer l’hérédité. Soit nN, on suppose que H(n) est vraie, et on en déduit que H(n+1) est vraie.
  4. Conclure avec une phrase du type : “D’après le principe de récurrence, la propriété est vraie pour tout n ∈ N“.

 

À toi de jouer !

Exercice 1

On définit la suite  par :

Démontrer que pour tout n ∈ N :

 

Exercice 2

(emprunté à Jean-Louis Rouget)

Démontrer que pour tout n ∈ N,  est un entier divisible par 3.

 

Corrigés

Tu trouveras les corrigés de ces deux exercices ici : Correction ex 1 et 2.

 

Pour aller un peu plus loin : la récurrence “à partir d’un certain rang”

Si tu as bien compris les deux premiers paragraphes de cet article et si tu as réussi à faire les deux exercices du paragraphe ci-dessus, tu es armé·e pour répondre à l’essentiel des questions que l’on pourrait te poser autour de la démonstration par récurrence.

Cependant, ce principe de démonstration peut être légèrement adapté pour démontrer des propriétés non plus sur l’ensemble des entiers naturels, mais à partir d’un certain rang seulement. Mais le principe est exactement le même, comme tu vas vite le comprendre en reprenant notre exemple des dominos.

Imaginons en effet que l’on ne souhaite plus faire tomber tous les dominos, mais seulement les dominos dont les numéros sont supérieurs ou égaux à 11. Facile, non ? Il suffit que :

  1. Les dominos dont les numéros sont supérieurs ou égaux à 11 soient placés suffisamment près les uns des autres, de sorte que si le domino numéro n tombe, alors le domino suivant (le numéro n+1) tombe également, pour n ≥ 11.
  2. On fasse tomber le domino numéro 11 (et non plus le domino numéro 0) !

Si ces deux conditions sont réunies, alors c’est gagné : tous les dominos dont les numéros sont supérieurs ou égaux à 11 tombent !

Si l’on formalise ceci mathématiquement on obtient la méthodologie suivante.

Pour démontrer par récurrence qu’une propriété H est vraie à partir d’un certain rang qu’on notera N, il faut :

  1. Énoncer clairement la propriété H(n) pour tout nN.
  2. Faire l’initialisation au rang N : on démontre H(N).
  3. Démontrer l’hérédité. Soit ≥ Non suppose que H(n) est vraie, et on en déduit que H(n+1) est vraie.
  4. Conclure avec une phrase du type : ” D’après le principe de récurrence, la propriété est vraie pour tout nN “.

 

Encore à toi de jouer !

Exercice 3

(emprunté à Jean-Louis Rouget)

Démontrer que pour tout entier n ≥ 6,

 

Corrigé

Tu trouveras le corrigé de cet exercice ici : Correction ex 3.

 

Te voilà maintenant armé·e pour affronter tous les exercices de niveau Bac nécessitant une démonstration par récurrence ! Si tu veux aller plus loin et aborder les concepts de récurrence double et de récurrence forte (qui ne sont pas explicitement au programme de lycée, mais qui constituent des notions mathématiques importantes abordées dans les études supérieures scientifiques), Major Bac t’explique ces deux concepts dans cet autre article. Mais si tu préfères pour le moment te concentrer sur les exercices de niveau Bac, la bonne compréhension et la maitrise des notions abordées dans l’article que tu viens de lire sont amplement suffisantes !

Pour aller plus loin : les deux types de raisonnements par récurrence.

Poursuis ta lecture sur ces sujets

Après une prépa MPSI/MP au lycée Louis le Grand, j'ai intégré le département de Mathématiques de l'ENS de Rennes, où j'ai passé deux ans (L3 et M1).