La récurrence et ses variantes

Démarrons aujourd’hui notre étude de raisonnements mathématiques avec une méthode que certains d’entre vous connaissent sans doute déjà : la démonstration par récurrence. Le fondement de cette méthode sera expliqué ici puis nous vous en présenterons ses différentes variantes. Nous vous indiquerons pour quel type de questions utiliser l’une ou l’autre des variantes de la récurrence. De plus, au travers d’exemples, nous vous exposerons également la façon de rédiger correctement une récurrence.
A cette occasion, nous pointerons du doigt les erreurs fréquentes, à ne pas commettre.

La démonstration par récurrence s’applique dans le cadre suivant :
Soit P(n) une propriété dépendant de l’entier naturel n. Supposons que l’on vous demande de montrer que :
 – P(n) est vraie pour tous les entiers naturels n.
 – Ou bien que P(n) est vraie pour tous les entiers n supérieurs à un certain entier naturel fixé : n0.

Le principe de la démonstration par récurrence repose sur le cinquième axiome de Péano, que vous nous avons présenté en début de semaine :
Si un ensemble d’entiers naturels contient 0 et le successeur de chacun de ses éléments, alors cet ensemble est égal à N tout entier.

Expliquons à présent le principe, lequel se décompose en deux étapes.
On commence tout d’abord par montrer que la propriété P(n) est vraie lorsque n vaut 0.
C’est ce que l’on appelle l’initialisation de la récurrence.
Comme nous le verrons dans les exercices, cette première étape correspond généralement à une simple vérification numérique.
Puis l’on transmet cette propriété de proche en proche d’un entier naturel k à son successeur : l’entier k+1. Autrement dit, on prouve que pour tout entier naturel k, P(k) implique P(k+1). Cette seconde étape s’appelle la propagation ou l’hérédité.
Ainsi, de n=0, la propriété se transmet à n=1, puis de n=1 à n=2. Plus généralement , pour un entier k quelconque, la propriété se propage de l’entier n=k-1 à l’entier n=k, puis de n=k à n=k+1, et ce procédé continue indéfiniment. Tous les entiers seront ainsi atteints.

Évoquons ici une légère variante.
Soit n0 un entier naturel fixé. Si l’on vous demande de démontrer que la propriété P(n) est vraie pour tout entier n supérieur à n0, l’initialisation se fait en montrant que P(n0) est vraie.
L’hérédité consistera alors à prouver l’implication P(k) implique P(k+1) pour tout entier k supérieur ou égal à n0.
Passons à un exemple pour voir la méthode en action et apprendre à rédiger correctement la récurrence.
Montrons que pour tout entier naturel n et tout réel x positif, (1+x) puissance n est supérieur ou égal à 1+nx.
Le premier travail consiste à identifier puis à poser la propriété P(n).
Il s’agit ici de « pour tout réel x positif, (1+x) puissance n supérieur à 1+nx. » Noter que l’on ne doit surtout pas inclure le « pour tout n dans N » dans l’expression de P(n) : ce serait une faute majeure de raisonnement, faute que l’on retrouve souvent dans les copies.
Ecrire P(n) signifie que l’on regarde la propriété à un rang n donné.
En revanche, il est indispensable de préciser dans P(n) le domaine de validité des autres variables.
Dans notre exemple, on doit donc inclure dans P(n) : « pour tout x dans R puissance +. » P(n) étant posée, débutons la récurrence proprement dite.
– Première étape : on initialise en vérifiant que la propriété est vraie pour n=0. Pour tout réel x de R puissance +, on calcule (1+x) puissance 0 qui vaut 1 et est donc bien supérieur ou égal à 1+0.x. La propriété P(0) est donc vérifiée.
 – Passons à la seconde étape : l’hérédité.
Supposons la propriété vraie pour un entier naturel k quelconque. Montrons, par implication, que la propriété est alors vraie au rang k+1. Pour tout réel x positif, on écrit (1+x) puissance (k+1) sous la forme (1+x) puissance k fois (1+x).
Or, par hypothèse de récurrence P(k), on sait que (1+x) puissance k est supérieur à 1+kx. En multipliant membre à membre cette inégalité par 1+x qui est positif, on trouve (1+x) puissance (k+1) supérieur à (1+kx).(1+x) autrement dit (1+x) puissance (k+1) supérieur à 1+(k+1).x+k.x puissance 2.
Or, comme kx puissance 2 est positif, cette dernière quantité est supérieure à 1+(k+1)x Ceci prouve la propriété pour l’entier k+1.
 – Par le principe de récurrence, on peut conclure que pour tout n entier naturel et tout x réel positif, (1+x) puissance n est supérieur ou égal à 1+nx.

Par opposition à cette récurrence dite simple, il existe d’autres formes de récurrence dites fortes.
Celle-ci sont employées lorsque la seule hypothèse P(k) ne suffit pas à prouver P(k+1).
Commençons par exposer le principe de récurrence double.
On veut démontrer que pour tout entier naturel n supérieur ou égal à un entier n0, une propriété P(n) est vraie.
Dans l’étape d’initialisation, on montre que P(n0) mais aussi P(n0+1) sont vérifiées.
Puis, dans l’étape d’hérédité, on montre l’implication suivante
 – si la propriété est vraie pour deux entiers consécutifs k et k+1, avec k supérieur à n0, alors elle est vraie pour l’entier suivant : k+2.
 – Par principe de récurrence double, on conclut alors que la propriété est vérifiée pour tout entier n plus grand que n0.

Enchainons tout de suite avec un exemple.
Soit (un) la suite réelle définie par la donnée de u0=1, u1=2 et par la relation suivante : pour tout entier naturel n, u(n+2)= 5u(n+1)-6un.
 – Il s’agit de montrer que pour tout entier n, un=2 puissance n.
Le premier travail est d’identifier la propriété P(n) à démontrer par récurrence.
Ici, c’est facile : il s’agit de un=2 puissance n .
 – On initialise la propriété pour les entiers n=0 et n=1.
D’après l’énoncé, u0=1 ce qui est bien égal à 2 puissance 0 : donc P(0) est vraie.
Toujours, d’après l’énoncé, u1=2 ce qui est bien égal à 2 puissance 1 : donc P(1) est vraie.
 – Passons à l’hérédité. Supposons la propriété vérifiée pour les entiers k et k+1.
 – Démontrons alors que la propriété est vraie pour l’entier k+2. D’après l’énoncé, u(k+2)= 5u(k+1)-6uk. En utilisant les hypothèses de récurrence P(k) et P(k+1), on transforme ceci en u(k+2)=5.2 puissance {k+1}-6.2 puissance {k} Soit 5.2 puissance {k+1}-3.2.2 puissance k. En factorisant, on obtient 2 puissance {k+1}. [5-3] donc 2 puissance {k+1}.2=2 puissance {k+2}. Ceci prouve que P(k+2) est vérifiée.
 – On conclut qu’en vertu du principe de récurrence double, la propriété P(n) est vraie pour tous les entiers naturels n.

Mais comment repérer que l’on doit faire une récurrence double, et non pas simple ? Ici, c’est relativement facile : voyez dans l’expression de la suite donnée dans l’énoncé, qu’un terme s’exprime en fonction des deux précédents.
Autrement dit, u{n+2} s’écrit en fonction de u{n+1} et de u{n} : c’est ce qui doit vous guider vers une récurrence double.
Le principe de récurrence double peut se généraliser de la façon suivante.
On veut montrer que pour tout entier naturel n supérieur ou égal à n0, une propriété
P(n) est vraie.
Dans l’étape d’initialisation, on montre que P(n0) est vraie.
Puis, dans l’étape d’hérédité, on montre l’implication suivante :
 – si la propriété est vraie pour tous les entiers compris entre n0 et k, alors elle est vraie pour l’entier : k+1.
 – Par principe de récurrence dite forte, on conclut alors que la propriété est vérifiée pour tout entier n plus grand que n0.

Illustrons cette méthode par un exemple. On considère la suite réelle (un) définie par la donnée de son premier terme u0=1 et par la relation suivante : pour tout entier naturel n, u{n+1} est la somme des termes précédents, c’est-à-dire u0+u1+…+un.
On peut noter cette somme avec la notation Sigma que certains d’entre vous connaissent sans doute déjà.
L’exercice consiste à montrer que pour tout entier naturel n non nul, un= 2 puissance {n-1}.
Comme ici, un terme de la suite est exprimé en fonction de TOUS les termes qui le précèdent, on s’oriente vers une récurrence forte.
Comme précédemment, le premier travail consiste à poser la propriété P(n) à démontrer : il s’agit ici de un=2 puissance {n-1}.
 – Passons ensuite à l’étape d’initialisation.
Comme l’énoncé nous indique que l’on doit prouver la propriété pour tout entier dans N*, l’initialisation se fait pour n=1. Toujours d’après l’énoncé, u1=u0=1 qui est bien égal à 2 puissance 0 autrement dit 2 puissance {1-1}.
Ceci prouve que P(1) est vraie.
 – Passons à l’hérédité.
Soit k un entier non nul.
Supposons la propriété vraie pour tous les entiers compris entre 1 et k.
D’après l’énoncé, u{k+1} est égal à la somme de u0, u1, u2… jusqu’à uk.
On sait d’ores et déjà que u0 vaut 1.
Par hypothèses de récurrence P(1), P(2) jusqu’à P(k), cela donne 1+2 puissance 0+2 puissance 1+….2 puissance {k-1}, autrement dit 1+ la somme des 2 puissance j, pour j variant de 0 à k-1.

D’après la formule donnant la somme des premiers termes d’une suite géométrique, on obtient 1+(1-2 puissance k)/(1-2). u{k+1} vaut donc 1-(1-2 puissance k), c’est-à-dire : 2 puissance k.
On a donc prouvé P(k+1), ce qui achève l’hérédité, et, par là-même, la récurrence.
Nous venons de vous expliquer comment mettre en œuvre une récurrence pour démontrer qu’une propriété P(n) est vraie pour tous les entiers n de N.
Et si l’on veut prouver une propriété pour tous les entiers n de Z, me direz-vous ? Étudions ce cas de figure sur un exercice.
On considère une fonction f de R puissance +* dans R vérifiant les hypothèses f(1)=0 et pour tout couple de réels x et y strictement positifs, f(x.y)=f(x+y).
On demande de montrer premièrement : que pour tout entier naturel n et pour tout réel x strictement positif, f(x puissance n)=nf(x).
Deuxièmement, on demande de propager la relation de N à Z, c’est-à-dire que montrer pour tout entier n dans Z cette fois et pour tout réel x strictement positif, f(x puissance n)=nf(x).
Vous aurez peut être reconnu ici les propriétés de la fonction logarithme népérien ln…
 – La première question se résout par une récurrence simple, en posant pour P(n) la propriété : « pour tout réel x strictement positif, f(x puissance n)=nf(x).
Je vous laissons rédiger la récurrence.
Passons à la seconde question.
Faisons une disjonction de cas.
 – Si l’entier n est dans N, la première question donne la réponse.
 – Si l’entier n est dans Z privé de N, on pose alors m=-n.
 – L’entier m est donc dans N, ce qui va permettre de se ramener à la première question. Expliquons de quelle manière.
 – Soit x un réel strictement positif.
 – On commence par appliquer la relation donnée par l’énoncé à x et à -x.
 – Comme f(1)=0, cela donne 0=f(1)=f(x .1/x)=f(x)+f(1/x).
 – On en déduit que pour tout réel x>0, f(1/x)=-f(x).
 – Ainsi, pour tout x strictement positif, f(x puissance n)=f(x puissance {-m})=f(1/xpuissance m) =-f(x puissance m), d’après ce que l’on vient de démontrer.
 – Par la question 1, comme m est dans N, -f(x puissance m)=-mf(x)=nf(x) : c’est ce qu’il fallait démontrer.
 – On constate donc que l’on ne fait pas de récurrence sur Z mais que l’on propage la relation de N à Z par le changement de variable m=-n. Cette petite astuce est à retenir.

Ceci achève la séquence consacrée aux méthodes de démonstration par récurrence.
A très bientôt.

Ce cours est extrait du module « Introduction au raisonnement mathématique : préparation à l’entrée dans l’enseignement supérieur » de Henri Lemberg et Magali Rocher tous deux docteurs agrégés en mathématiques.

Suites de récurrence

La vidéo d’aujourd’hui traite des suites de récurrence. Une suite récurrente est définie par la relation de récurrence suivante : u(n+1) = f(u(n)), où f : D → R est continue et u(0) ∈ I un intervalle de R. Les suites récurrentes linéaires d’ordre 1 sont les suites géométriques.

Je vous invite à en savoir plus en regardant la vidéo ci-dessous. N’hésitez pas à la partager.

  • Cours en vidéo :
  • Questions, remarques ou commentaires :

N’hésitez pas à donner votre avis ou à poser une question. Pour poster un commentaire, cliquez sur le titre de l’article. S’il y a toujours des incompréhensions même après avoir visionné la vidéo, si vous ne savez toujours pas faire malgré le temps que vous y avez passé, contactez-moi !

Chapitre 6 : Méthodes de raisonnement

Voici une nouvelle vidéo portant sur le chapitre 6 intitulé Langage et Raisonnement de la formation Réussir sa 1ère année de prépa. Nous allons voir ici les différentes méthodes de raisonnement à comprendre et à savoir utiliser pour toutes vos démonstrations.

  • Cours/Vidéo :

  • Questions :

N’hésitez pas à utiliser la barre de commentaires pour poser vos questions ou réagir. Pour poster un commentaire, cliquez sur le titre de l’article.

Chapitre 5 : Étude de suites récurrentes

Voici la première vidéo du chapitre 5 intitulé Séries numériques. Ici, l’idée est de voir comment étudier des suites récurrentes.

  • Cours/Vidéo :

  • Questions :

N’hésitez pas à utiliser la barre de commentaires pour poser vos questions ou réagir. Pour poster un commentaire, cliquez sur le titre de l’article.