Récurrence double

←

SommaireRécurrence double

→

L'essentiel du cours

22 cartes

Montrer :

Définition

La récurrence double est un raisonnement par récurrence dont l'hérédité établit

P(n+2)

à partir des deux rangs qui le précèdent,

n

n+1

. On la choisit quand le passage au rang suivant a besoin de deux rangs consécutifs, typiquement pour une suite donnée par deux termes initiaux et une relation exprimant

u_{n+2}

en fonction de

u_{n+1}

et de

u_n

(thème « Définir un objet par récurrence »). Elle comporte trois temps : la double initialisation, l'hérédité à deux rangs et la conclusion.

u_{n+2} = f\left(u_{n+1}, u_n\right)

le signal : chaque terme dépend des deux précédents

P(n) \text{ et } P(n+1) \Longrightarrow P(n+2)

le pas d'une récurrence double

Propriété

Principe de récurrence double

Soit

n_0 \in \mathbb{N}

et, pour tout entier

n \geqslant n_0

, une proposition

P(n)

. Si

P(n_0)

P(n_0+1)

sont vraies, et si pour tout entier

n \geqslant n_0

, «

P(n)

P(n+1)

» implique

P(n+2)

, alors

P(n)

est vraie pour tout entier

n \geqslant n_0

. Mécanisme :

P(n_0)

P(n_0+1)

donnent

P(n_0+2)

, puis

P(n_0+1)

P(n_0+2)

donnent

P(n_0+3)

, et ainsi de suite, chaque nouveau rang s'appuyant sur les deux derniers acquis.

\Big( P(n_0) \wedge P(n_0+1) \wedge \forall n \geqslant n_0,\ \big( P(n) \wedge P(n+1) \Rightarrow P(n+2) \big) \Big) \Rightarrow \forall n \geqslant n_0,\ P(n)

deux initialisations et une hérédité à deux rangs donnent tous les rangs

Définition

Double initialisation

La double initialisation consiste à vérifier

P(n_0)

P(n_0+1)

, les deux premiers rangs, qui sont consécutifs. Les deux sont nécessaires : appliquée au premier rang

n = n_0

, l'hérédité réclame à la fois

P(n_0)

P(n_0+1)

pour produire

P(n_0+2)

. Lorsque

n_0

est le premier rang de la suite, chaque vérification repose sur les termes initiaux donnés par l'énoncé, que la relation de récurrence ne produit pas ; si la propriété n'est à établir qu'à partir d'un rang plus grand, on calcule d'abord par la relation les termes de rangs

n_0

n_0+1

P(n_0) \text{ et } P(n_0+1)

deux rangs de départ qui se suivent

Définition

Hérédité à deux rangs

L'hérédité à deux rangs consiste à fixer un entier

n \geqslant n_0

, à supposer

P(n)

P(n+1)

vraies, puis à démontrer

P(n+2)

. La conjonction «

P(n)

P(n+1)

» s'appelle l'hypothèse de récurrence ; elle porte sur cet entier

n

fixé, jamais sur tous les entiers. Comme

n

est quelconque, on a ainsi prouvé l'implication pour tout

n \geqslant n_0

\forall n \geqslant n_0,\ \big( P(n) \wedge P(n+1) \big) \Rightarrow P(n+2)

ce qu'établit l'hérédité, un entier quelconque étant fixé

Vocabulaire

Relation de récurrence, hypothèse de récurrence

La relation de récurrence est la définition de la suite, par exemple

u_{n+2} = 3u_{n+1} - 2u_n

; on l'invoque par « par définition de la suite » ou « d'après la relation de récurrence ». L'hypothèse de récurrence est ce que l'on suppose dans l'hérédité, «

P(n)

P(n+1)

» ; on l'invoque rang par rang : « d'après

P(n+1)

», « d'après

P(n)

». « Soit

n \in \mathbb{N}

tel que … » fixe l'entier, « Montrons que » annonce le but, « par récurrence double » nomme le principe dans la conclusion, et « en particulier » tire

P(n)

d'une propriété plus forte comme «

P(n)

P(n+1)

».

\text{Soit } n \in \mathbb{N} \text{ tel que } P(n) \text{ et } P(n+1) \text{ soient vraies.}

fixer l'entier et poser l'hypothèse de récurrence

Méthode

Rédiger la double initialisation

Quand l'utiliser : la suite est donnée par deux termes initiaux et une relation liant les rangs

n

n+1

n+2

, ou l'hérédité que l'on prévoit a besoin de deux rangs précédents.
1) Poser la propriété, sans quantifier

n

à l'intérieur : « Pour tout

n \in \mathbb{N}

, notons

P(n)

la proposition : … »
2) Repérer le premier rang

n_0

de l'énoncé : les rangs à vérifier sont

n_0

n_0+1

, deux rangs qui se suivent.
3) Vérifier le premier rang à partir de la donnée de l'énoncé, en calculant chaque membre à part : « Initialisation. D'une part

u_0 = \dots

, d'autre part

\dots

; donc

P(0)

est vraie. »
4) Vérifier le second rang de la même façon, sans utiliser la relation de récurrence, qui ne donne pas

u_1

: « D'une part

u_1 = \dots

, d'autre part

\dots

; donc

P(1)

est vraie. »
5) Clore l'étape en nommant les deux acquis : « Ainsi

P(0)

P(1)

sont vraies. »
Si la suite ne commence qu'au rang

1

, on vérifie

P(1)

P(2)

, et l'hérédité s'écrit pour

n \geqslant 1

: elle démarre au rang de la première initialisation.
Si la propriété n'est à établir qu'à partir d'un rang

n_0

situé après les termes donnés, les termes de rangs

n_0

n_0+1

ne sont pas des données : on les calcule d'abord par la relation de récurrence, puis on vérifie

P(n_0)

P(n_0+1)

en comparant chaque membre.

\text{Ainsi } P(0) \text{ et } P(1) \text{ sont vraies.}

la phrase qui clôt la double initialisation

Méthode

Rédiger l'hérédité à deux rangs

Quand l'utiliser : pour obtenir le résultat au rang

n+2

, il faut ce que l'on sait aux rangs

n

n+1

; typiquement, la relation de récurrence exprime

u_{n+2}

à l'aide de

u_{n+1}

et de

u_n

.
1) Fixer l'entier, poser l'hypothèse et annoncer le but : « Hérédité. Soit

n \in \mathbb{N}

tel que

P(n)

P(n+1)

soient vraies. Montrons que

P(n+2)

est vraie. » Jamais « pour tout

n

» dans l'hypothèse : ce serait supposer le résultat (thème « Récurrence simple »).
2) Écrire le but en toutes lettres : « Il s'agit de montrer que … », en remplaçant

n

par

n+2

dans

P

.
3) Partir du terme de rang

n+2

et appliquer la relation de récurrence : « Par définition de la suite,

u_{n+2} = \dots

»
4) Remplacer

u_{n+1}

puis

u_n

en citant, pour chacun, la partie de l'hypothèse qui le fournit : « D'après

P(n+1)

, … ; d'après

P(n)

, … »
5) Calculer ou majorer jusqu'au but exact, puis clore : « Donc

P(n+2)

est vraie. »
6) Conclure : «

P(0)

P(1)

sont vraies et, pour tout

n \in \mathbb{N}

P(n)

P(n+1)

entraînent

P(n+2)

; par récurrence double,

P(n)

est vraie pour tout

n \in \mathbb{N}

. »
Forme décalée, tout aussi correcte : « Soit

n \geqslant 1

tel que

P(n-1)

P(n)

soient vraies. Montrons

P(n+1)

. » La condition

n \geqslant 1

garantit que le rang

n-1

existe.

\text{Soit } n \in \mathbb{N} \text{ tel que } P(n) \text{ et } P(n+1) \text{ soient vraies. Montrons } P(n+2).

la première ligne de l'hérédité

\text{Soit } n \geqslant 1 \text{ tel que } P(n-1) \text{ et } P(n) \text{ soient vraies. Montrons } P(n+1).

la même hérédité, décalée d'un rang

Exemple

Rédaction modèle : une formule explicite par récurrence double

Soit $(u_n)$ la suite définie par $u_0 = 2$ , $u_1 = 3$ et, pour tout $n \in \mathbb{N}$ , $u_{n+2} = 3u_{n+1} - 2u_n$ . Montrer que pour tout $n \in \mathbb{N}$ , $u_n = 2^n + 1$ .
Pour tout

n \in \mathbb{N}

, notons

P(n)

la proposition :

u_n = 2^n + 1

.
Initialisation. D'une part

u_0 = 2

, d'autre part

2^0 + 1 = 2

; donc

P(0)

est vraie.
D'une part

u_1 = 3

, d'autre part

2^1 + 1 = 3

; donc

P(1)

est vraie.
Ainsi

P(0)

P(1)

sont vraies.
Hérédité. Soit

n \in \mathbb{N}

tel que

P(n)

P(n+1)

soient vraies. Montrons que

P(n+2)

est vraie, c'est-à-dire que

u_{n+2} = 2^{n+2} + 1

.
Par définition de la suite,

u_{n+2} = 3u_{n+1} - 2u_n

.
Or

u_{n+1} = 2^{n+1} + 1

d'après

P(n+1)

, et

u_n = 2^n + 1

d'après

P(n)

.
Donc

u_{n+2} = 3\left(2^{n+1} + 1\right) - 2\left(2^n + 1\right) = 3 \cdot 2^{n+1} + 3 - 2^{n+1} - 2 = 2 \cdot 2^{n+1} + 1 = 2^{n+2} + 1

.
Ainsi

P(n+2)

est vraie.
Conclusion.

P(0)

P(1)

sont vraies et, pour tout

n \in \mathbb{N}

P(n)

P(n+1)

entraînent

P(n+2)

; par récurrence double, pour tout

n \in \mathbb{N}

u_n = 2^n + 1

.
À retenir : chacun des termes

u_{n+1}

u_n

est remplacé en citant la partie de l'hypothèse qui le fournit, et le calcul s'arrête exactement sur le but annoncé.

Exemple

Rédaction modèle : majorer la suite de Fibonacci

Soit $(F_n)$ la suite définie par $F_0 = 0$ , $F_1 = 1$ et, pour tout $n \in \mathbb{N}$ , $F_{n+2} = F_{n+1} + F_n$ . Montrer que pour tout $n \in \mathbb{N}$ , $F_n \leqslant 2^n$ .
Pour tout

n \in \mathbb{N}

, notons

P(n)

la proposition :

F_n \leqslant 2^n

.
Initialisation.

F_0 = 0

2^0 = 1

; comme

0 \leqslant 1

P(0)

est vraie.

F_1 = 1

2^1 = 2

; comme

1 \leqslant 2

P(1)

est vraie.
Ainsi

P(0)

P(1)

sont vraies.
Hérédité. Soit

n \in \mathbb{N}

tel que

P(n)

P(n+1)

soient vraies. Montrons que

P(n+2)

est vraie, c'est-à-dire que

F_{n+2} \leqslant 2^{n+2}

.
Par définition de la suite,

F_{n+2} = F_{n+1} + F_n

.
D'après

P(n+1)

F_{n+1} \leqslant 2^{n+1}

; d'après

P(n)

F_n \leqslant 2^n

.
En ajoutant membre à membre ces deux inégalités de même sens,

F_{n+1} + F_n \leqslant 2^{n+1} + 2^n

, c'est-à-dire

F_{n+2} \leqslant 3 \cdot 2^n

.
Or

3 \leqslant 4

2^n > 0

, donc

3 \cdot 2^n \leqslant 4 \cdot 2^n = 2^{n+2}

.
Par transitivité,

F_{n+2} \leqslant 2^{n+2}

, donc

P(n+2)

est vraie.
Conclusion.

P(0)

P(1)

sont vraies et, pour tout

n \in \mathbb{N}

P(n)

P(n+1)

entraînent

P(n+2)

; par récurrence double, pour tout

n \in \mathbb{N}

F_n \leqslant 2^n

.
À retenir : on ajoute membre à membre les deux inégalités fournies par l'hypothèse, puis on justifie à part la dernière majoration, car

2^{n+1} + 2^n

vaut

3 \cdot 2^n

et non

2^{n+2}

Piège

N'initialiser qu'un seul rang

Ligne fautive : « Initialisation.

u_0 = 2 = 2^0 + 1

, donc

P(0)

est vraie. », suivie d'une hérédité qui suppose

P(n)

P(n+1)

.
Appliquée à

n = 0

, cette hérédité réclame

P(1)

, qui n'a jamais été établie : la chaîne ne démarre pas. L'oubli n'est pas de pure forme : la suite

(v_n)

définie par

v_0 = 2

v_1 = 4

v_{n+2} = 3v_{n+1} - 2v_n

passe la même initialisation au rang

0

et exactement le même calcul d'hérédité, pourtant

v_1 = 4

alors que

2^1 + 1 = 3

.
Version correcte : « Initialisation.

u_0 = 2 = 2^0 + 1

, donc

P(0)

est vraie ;

u_1 = 3 = 2^1 + 1

, donc

P(1)

est vraie. »

Piège

Initialiser aux rangs 0 et 2 en sautant le rang 1

Ligne fautive : « Initialisation.

P(0)

P(2)

sont vraies. », suivie de l'hérédité «

P(n)

P(n+1)

entraînent

P(n+2)

».
L'hérédité ne progresse qu'à partir de deux rangs consécutifs : à

n = 0

comme à

n = 1

, elle réclame

P(1)

, jamais démontrée, et aucun nouveau rang ne s'en déduit. Contre-exemple : la suite définie par

u_0 = 1

u_1 = -1

u_{n+2} = u_n u_{n+1}^2

, avec

P(n)

u_n > 0

. La proposition

P(0)

est vraie,

P(2)

aussi car

u_2 = 1

, et l'hérédité est juste, puisque

u_n > 0

u_{n+1} > 0

donnent

u_n u_{n+1}^2 > 0

; pourtant

u_1 = -1

.
Version correcte : initialiser aux deux rangs qui se suivent, « Initialisation. … donc

P(0)

est vraie ; … donc

P(1)

est vraie. »

Piège

Supposer un seul rang, puis utiliser le rang d'avant

Ligne fautive : « Soit

n \geqslant 1

tel que

P(n)

soit vraie. Montrons

P(n+1)

. On a

u_{n+1} = 3u_n - 2u_{n-1} = 3\left(2^n + 1\right) - 2\left(2^{n-1} + 1\right)

. »
Remplacer

u_{n-1}

par

2^{n-1} + 1

, c'est utiliser

P(n-1)

, qui n'a pas été supposée : la preuve repose sur une hypothèse absente. Le calcul aboutit pourtant à

2^{n+1} + 1

, ce qui rend la faute invisible à qui ne relit que les calculs.
Version correcte : « Soit

n \in \mathbb{N}

tel que

P(n)

P(n+1)

soient vraies. Montrons

P(n+2)

. », ou sous forme décalée : « Soit

n \geqslant 1

tel que

P(n-1)

P(n)

soient vraies. Montrons

P(n+1)

. »

Piège

Viser le rang n + 1 au lieu du rang n + 2

Ligne fautive : « Soit

n \in \mathbb{N}

tel que

P(n)

P(n+1)

soient vraies. Montrons

P(n+1)

u_{n+1} = 3u_n - 2u_{n-1} = \dots

P(n+1)

fait déjà partie de l'hypothèse : la « démontrer » ne fait pas avancer d'un rang, et le calcul fait en plus intervenir

u_{n-1}

, rang non supposé et même inexistant pour

n = 0

. Le décalage vient du réflexe de la récurrence simple, où le but est le rang qui suit le seul rang supposé.
Version correcte : « Soit

n \in \mathbb{N}

tel que

P(n)

P(n+1)

soient vraies. Montrons

P(n+2)

: par définition de la suite,

u_{n+2} = 3u_{n+1} - 2u_n

. » Le but est le rang qui suit les deux rangs supposés.

Propriété

Réduction à une récurrence simple

Pour tout

n \geqslant n_0

, on pose

Q(n)

: «

P(n)

P(n+1)

». D'une part,

Q(n_0)

est exactement la double initialisation. D'autre part,

Q(n+1)

s'écrit «

P(n+1)

P(n+2)

», et

P(n+1)

figure déjà dans

Q(n)

: l'implication

Q(n) \Rightarrow Q(n+1)

équivaut donc à l'hérédité double. Une récurrence simple sur

Q

donne

Q(n)

pour tout

n \geqslant n_0

, donc en particulier

P(n)

: le principe de récurrence double est une conséquence du principe de récurrence simple.

Q(n) : P(n) \text{ et } P(n+1)

la propriété qui transforme la récurrence double en récurrence simple

\big( Q(n) \Rightarrow Q(n+1) \big) \Longleftrightarrow \big( P(n) \wedge P(n+1) \Rightarrow P(n+2) \big)

les deux hérédités disent la même chose

Méthode

Reformuler une récurrence double en récurrence simple

Quand l'utiliser : on ne veut invoquer que le principe de récurrence simple (consigne de l'énoncé, doute sur le schéma à deux rangs), la propriété porte déjà sur deux termes consécutifs, ou l'on doit justifier une récurrence d'ordre

p

.
1) Poser la propriété couplée avec le mot « et » : « Pour tout

n \in \mathbb{N}

, notons

Q(n)

la proposition :

P(n)

P(n+1)

. »
2) Initialiser en vérifiant les deux morceaux : «

P(0)

est vraie car … ;

P(1)

est vraie car … ; donc

Q(0)

est vraie. »
3) Poser l'hérédité simple et déplier le but : « Soit

n \in \mathbb{N}

tel que

Q(n)

soit vraie. Montrons

Q(n+1)

, c'est-à-dire

P(n+1)

P(n+2)

. »
4) Récupérer le premier morceau sans calcul : «

P(n+1)

est vraie, car elle fait partie de

Q(n)

. »
5) Démontrer

P(n+2)

à l'aide de

P(n)

et de

P(n+1)

, toutes deux contenues dans

Q(n)

, puis réunir : « Ainsi

P(n+1)

P(n+2)

sont vraies, donc

Q(n+1)

est vraie. »
6) Conclure en redescendant à

P

: « Par récurrence,

Q(n)

est vraie pour tout

n \in \mathbb{N}

; en particulier,

P(n)

est vraie pour tout

n \in \mathbb{N}

. »

Q(n) : P(n) \text{ et } P(n+1)

la propriété couplée, avec une conjonction

\text{Soit } n \in \mathbb{N} \text{ tel que } Q(n) \text{ soit vraie. Montrons } P(n+1) \text{ et } P(n+2).

l'hérédité simple, but déplié

Exemple

Rédaction modèle : un encadrement par récurrence simple sur deux rangs couplés

Soit $(u_n)$ la suite définie par $u_0 = 1$ , $u_1 = 2$ et, pour tout $n \in \mathbb{N}$ , $u_{n+2} = \frac{u_{n+1} + u_n}{2}$ . Montrer que pour tout $n \in \mathbb{N}$ , $1 \leqslant u_n \leqslant 2$ .
Pour tout

n \in \mathbb{N}

, notons

P(n)

la proposition :

1 \leqslant u_n \leqslant 2

, et

Q(n)

la proposition :

P(n)

P(n+1)

.
Initialisation.

u_0 = 1

1 \leqslant 1 \leqslant 2

, donc

P(0)

est vraie ;

u_1 = 2

1 \leqslant 2 \leqslant 2

, donc

P(1)

est vraie. Ainsi

Q(0)

est vraie.
Hérédité. Soit

n \in \mathbb{N}

tel que

Q(n)

soit vraie. Montrons

Q(n+1)

, c'est-à-dire

P(n+1)

P(n+2)

P(n+1)

est vraie, car elle fait partie de

Q(n)

.
Montrons

P(n+2)

. Par définition de la suite,

u_{n+2} = \frac{u_{n+1} + u_n}{2}

.
D'après

Q(n)

1 \leqslant u_n \leqslant 2

1 \leqslant u_{n+1} \leqslant 2

.
En ajoutant membre à membre ces deux encadrements,

2 \leqslant u_{n+1} + u_n \leqslant 4

.
En divisant par

2

, qui est strictement positif,

1 \leqslant \frac{u_{n+1} + u_n}{2} \leqslant 2

, c'est-à-dire

1 \leqslant u_{n+2} \leqslant 2

; donc

P(n+2)

est vraie.
Ainsi

P(n+1)

P(n+2)

sont vraies, donc

Q(n+1)

est vraie.
Conclusion.

Q(0)

est vraie et, pour tout

n \in \mathbb{N}

Q(n)

entraîne

Q(n+1)

; par récurrence,

Q(n)

est vraie pour tout

n \in \mathbb{N}

. En particulier, pour tout

n \in \mathbb{N}

1 \leqslant u_n \leqslant 2

.
À retenir : dans l'hérédité sur

Q

, le morceau

P(n+1)

se récupère dans l'hypothèse et seul

P(n+2)

se démontre, puis la conclusion redescend de

Q

P

Piège

Définir Q(n) par une implication au lieu d'une conjonction

Ligne fautive : « Pour tout

n \in \mathbb{N}

, notons

Q(n)

la proposition : si

P(n)

, alors

P(n+1)

. »
Établir cette propriété pour tout

n

ne fournit aucun

P(n)

, car une implication est vraie dès que sa prémisse est fausse : si

P(n)

est fausse pour tout

n

, alors

Q(n)

est vraie pour tout

n

. La conclusion « en particulier,

P(n)

est vraie » devient injustifiée, et l'hérédité ne dispose plus de

P(n)

ni de

P(n+1)

comme acquis.
Version correcte : « Pour tout

n \in \mathbb{N}

, notons

Q(n)

la proposition :

P(n)

P(n+1)

. »

Définition

Récurrence d'ordre p

Soient

p \geqslant 1

n_0

deux entiers naturels et, pour tout entier

n \geqslant n_0

P(n)

une proposition. Une récurrence d'ordre

p

vérifie les

p

premiers rangs

P(n_0), P(n_0+1), \dots, P(n_0+p-1)

, puis démontre, pour tout

n \geqslant n_0

, que les propositions

P(n), P(n+1), \dots, P(n+p-1)

entraînent

P(n+p)

. L'ordre

1

est la récurrence simple, l'ordre

2

la récurrence double. Elle se ramène à une récurrence simple sur

Q(n)

: «

P(n)

P(n+1)

et … et

P(n+p-1)

».

P(n) \wedge P(n+1) \wedge \dots \wedge P(n+p-1) \Rightarrow P(n+p)

l'hérédité : les derniers rangs consécutifs donnent le suivant

Q(n) : P(n) \wedge P(n+1) \wedge \dots \wedge P(n+p-1)

la propriété qui la ramène à une récurrence simple

Propriété

Autant d'initialisations que de rangs supposés

Une récurrence dont l'hérédité suppose

p

rangs consécutifs exige

p

initialisations consécutives : une pour la simple, deux pour la double, trois pour l'ordre

3

. L'ordre se lit dans l'hérédité : c'est l'écart entre le rang visé et le plus ancien rang qu'elle utilise ; si l'obtention du rang

n+p

fait appel au rang

n

et à aucun rang antérieur, il vaut

p

, même si des rangs intermédiaires ne servent pas, et

u_{n+3} = u_{n+2} + u_n

appelle ainsi une récurrence d'ordre

3

. Si seul le rang précédent sert, une récurrence simple suffit. Si l'hérédité a besoin de tous les rangs précédents, ou d'un rang dont l'écart avec le rang visé n'est pas fixé, on passe à la récurrence forte (thème « Récurrence forte »).

P(n_0), \dots, P(n_0+p-1)

autant de rangs de départ que de rangs dans l'hypothèse

u_{n+3} = u_{n+2} + u_n

le plus ancien rang utilisé est trois crans en arrière : ordre trois

Exemple

Rédaction modèle : une récurrence d'ordre 3

Soit $(u_n)$ la suite définie par $u_0 = 1$ , $u_1 = 2$ , $u_2 = 4$ et, pour tout $n \in \mathbb{N}$ , $u_{n+3} = u_{n+2} + u_{n+1} + 2u_n$ . Montrer que pour tout $n \in \mathbb{N}$ , $u_n = 2^n$ .
Pour tout

n \in \mathbb{N}

, notons

P(n)

la proposition :

u_n = 2^n

.
Initialisation.

u_0 = 1 = 2^0

u_1 = 2 = 2^1

u_2 = 4 = 2^2

; donc

P(0)

P(1)

P(2)

sont vraies.
Hérédité. Soit

n \in \mathbb{N}

tel que

P(n)

P(n+1)

P(n+2)

soient vraies. Montrons que

P(n+3)

est vraie, c'est-à-dire que

u_{n+3} = 2^{n+3}

.
Par définition de la suite,

u_{n+3} = u_{n+2} + u_{n+1} + 2u_n

.
D'après

P(n+2)

u_{n+2} = 2^{n+2}

; d'après

P(n+1)

u_{n+1} = 2^{n+1}

; d'après

P(n)

u_n = 2^n

.
Donc

u_{n+3} = 2^{n+2} + 2^{n+1} + 2 \cdot 2^n = 4 \cdot 2^n + 2 \cdot 2^n + 2 \cdot 2^n = 8 \cdot 2^n = 2^{n+3}

.
Ainsi

P(n+3)

est vraie.
Conclusion.

P(0)

P(1)

P(2)

sont vraies et, pour tout

n \in \mathbb{N}

P(n)

P(n+1)

P(n+2)

entraînent

P(n+3)

; par récurrence d'ordre

3

, pour tout

n \in \mathbb{N}

u_n = 2^n

.
À retenir : une relation qui remonte trois rangs en arrière appelle trois initialisations consécutives et une hypothèse portant sur trois rangs consécutifs.

Propriété

Récurrence double et récurrence de pas 2

Une récurrence de pas 2 démontre

P(n) \Rightarrow P(n+2)

: son hérédité n'utilise qu'un rang. Initialisée au seul rang

0

, elle n'atteint que les rangs pairs ; il faut aussi

P(1)

pour atteindre les rangs impairs. La récurrence double exige elle aussi

P(0)

P(1)

, mais pour une autre raison : son premier pas, l'hérédité appliquée à

n = 0

, utilise les deux. Dans les deux schémas, on initialise aux rangs

n_0

n_0+1

, jamais aux rangs

n_0

n_0+2

P(n) \Rightarrow P(n+2)

pas de 2 : un seul rang supposé, un rang sauté

P(n) \wedge P(n+1) \Rightarrow P(n+2)

récurrence double : deux rangs consécutifs supposés

Formulaire

Schémas de récurrence à un, deux ou p rangs

Simple : initialiser

P(n_0)

; supposer

P(n)

; montrer

P(n+1)

.
Double : initialiser

P(n_0)

P(n_0+1)

; supposer

P(n)

P(n+1)

; montrer

P(n+2)

(Double, forme décalée : même initialisation ; pour

n \geqslant n_0+1

, supposer

P(n-1)

P(n)

; montrer

P(n+1)

).
Double, par réduction : avec

Q(n)

: «

P(n)

P(n+1)

», initialiser

Q(n_0)

; supposer

Q(n)

; montrer

Q(n+1)

.
Ordre

p

: initialiser

P(n_0), \dots, P(n_0+p-1)

; supposer

P(n), \dots, P(n+p-1)

; montrer

P(n+p)

.
Forte : initialiser

P(n_0)

; supposer

P(k)

pour tout entier

k

tel que

n_0 \leqslant k \leqslant n

; montrer

P(n+1)

(thème « Récurrence forte »).

P(n_0),\ P(n_0+1) \quad ; \quad P(n) \wedge P(n+1) \Rightarrow P(n+2)

récurrence double : deux départs, deux rangs supposés

n \geqslant n_0+1 : \ P(n-1) \wedge P(n) \Rightarrow P(n+1)

forme décalée de l'hérédité double

P(n_0), \dots, P(n_0+p-1) \quad ; \quad P(n) \wedge \dots \wedge P(n+p-1) \Rightarrow P(n+p)

récurrence d'ordre quelconque

Exercices

Exercice 1Application

Lire le schéma de récurrence avant de rédiger

Pour chacun des énoncés a) à d), on ne demande pas la démonstration. Indiquer : (i) les rangs dont dépend le rang visé par l'hérédité, et le type de récurrence qui en découle ; (ii) les initialisations à rédiger ; (iii) la première ligne de l'hérédité, suivie du but écrit en toutes lettres.
a)

u_0 = 1

et, pour tout

n \in \mathbb{N}

u_{n+1} = 2u_n + 1

. Montrer que pour tout

n \in \mathbb{N}

u_n = 2^{n+1} - 1

.
b)

v_1 = 1

v_2 = 3

et, pour tout entier

n \geqslant 1

v_{n+2} = v_{n+1} + 2v_n

. Montrer que pour tout entier

n \geqslant 1

v_n

est un entier impair.
c)

w_0 = 0

w_1 = 1

w_2 = 2

et, pour tout

n \in \mathbb{N}

w_{n+3} = w_{n+2} + w_{n+1} - w_n

. Montrer que pour tout

n \in \mathbb{N}

w_n = n

.
d)

s_0 = 1

s_1 = 2

s_2 = 3

et, pour tout

n \in \mathbb{N}

s_{n+3} = s_{n+2} + s_n

. Montrer que pour tout

n \in \mathbb{N}

s_n \geqslant 1

.
e) Pour l'énoncé d), un camarade propose de n'initialiser que

P(0)

P(2)

, « puisque la relation ne fait intervenir que les rangs

n

n + 2

», et d'écrire l'hérédité : pour tout

n \in \mathbb{N}

P(n)

P(n+2)

entraînent

P(n+3)

. Montrer que sa récurrence bloque dès le deuxième pas.

Voir le corrigé

a) (i)

u_{n+1}

ne dépend que de

u_n

: récurrence simple.
(ii) Initialiser

P(0)

seulement.
(iii) « Soit

n \in \mathbb{N}

tel que

P(n)

soit vraie. Montrons

P(n+1)

, c'est-à-dire

u_{n+1} = 2^{n+2} - 1

. »
b) (i)

v_{n+2}

dépend de

v_{n+1}

et de

v_n

: récurrence double. Les deux rangs servent :

P(n+1)

donne l'imparité de

v_{n+1}

, et

P(n)

garantit que

v_n

est un entier, donc que

2v_n

est un entier pair.
(ii) La suite commence au rang

1

: initialiser

P(1)

P(2)

.
(iii) « Soit

n \geqslant 1

tel que

P(n)

P(n+1)

soient vraies. Montrons

P(n+2)

, c'est-à-dire que

v_{n+2}

est un entier impair. » L'entier

n

part de

1

, le rang de la première initialisation ; pour

n = 0

, le terme

v_0

n'existe pas.
c) (i)

w_{n+3}

dépend de

w_{n+2}

, de

w_{n+1}

et de

w_n

: récurrence d'ordre $3$ .
(ii) Initialiser

P(0)

P(1)

P(2)

.
(iii) « Soit

n \in \mathbb{N}

tel que

P(n)

P(n+1)

P(n+2)

soient vraies. Montrons

P(n+3)

, c'est-à-dire

w_{n+3} = n + 3

. »
d) (i)

s_{n+3}

dépend de

s_{n+2}

et de

s_n

. Ce qui fixe l'ordre, c'est l'écart entre le rang visé et le rang le plus ancien utilisé, ici

3

: récurrence d'ordre $3$ , bien que deux termes seulement figurent dans la relation.
(ii) Initialiser

P(0)

P(1)

P(2)

, trois rangs consécutifs.
(iii) « Soit

n \in \mathbb{N}

tel que

P(n)

P(n+1)

P(n+2)

soient vraies. Montrons

P(n+3)

, c'est-à-dire

s_{n+3} \geqslant 1

. » Le calcul n'utilisera que

P(n+2)

P(n)

: une hypothèse de récurrence peut ne pas servir en entier.
e) Au premier pas,

n = 0

, l'hérédité du camarade donne

P(3)

à partir de

P(0)

et de

P(2)

.
Au deuxième pas,

n = 1

, elle réclame

P(1)

P(3)

; or

P(1)

n'a jamais été établie, donc ce pas ne peut pas être franchi.
Les pas suivants dépendent de celui-là : le pas

n = 2

réclame

P(4)

, que seul le pas

n = 1

fournirait, et chaque pas

n \geqslant 2

réclame

P(n+2)

, que seul le pas

n - 1

fournirait.
On n'obtient donc que

P(0)

P(2)

P(3)

. Le rang

1

doit être vérifié à part, comme tout rang que la relation ne produit pas : ici

0

1

2

Exercice 2Application

Compléter une récurrence double sous sa forme décalée

Soit

(u_n)

la suite définie par

u_0 = 0

u_1 = 2

et, pour tout entier

n \geqslant 1

u_{n+1} = 4u_n - 4u_{n-1}

. On veut montrer que pour tout

n \in \mathbb{N}

u_n = n 2^n

. Recopier la rédaction suivante en complétant les emplacements (a) à (h).
Pour tout

n \in \mathbb{N}

, notons

P(n)

la proposition : (a).
Initialisation. D'une part

u_0 = 0

, d'autre part

0 \cdot 2^0 = 0

; donc

P(0)

est vraie. (b)
Hérédité. Soit (c) tel que (d) soient vraies. Montrons que

P(n+1)

est vraie, c'est-à-dire que (e).
Comme

n \geqslant 1

, la relation de récurrence s'applique au rang

n

u_{n+1} = 4u_n - 4u_{n-1}

.
(f)
Donc

u_{n+1} = 4n 2^n - 4(n-1)2^{n-1}

. Comme

4 \cdot 2^{n-1} = 2 \cdot 2^n

, on obtient

u_{n+1} =

(g)

= (n+1)2^{n+1}

, et

P(n+1)

est vraie.
Conclusion. (h)
Répondre enfin à deux questions. Pourquoi l'entier de l'hérédité ne peut-il pas être pris quelconque dans

\mathbb{N}

? Pourquoi l'initialisation porte-t-elle malgré tout sur les rangs

0

1

Voir le corrigé

(a)

u_n = n 2^n

.
(b) D'une part

u_1 = 2

, d'autre part

1 \cdot 2^1 = 2

; donc

P(1)

est vraie. Ainsi

P(0)

P(1)

sont vraies.
(c)

n \geqslant 1

(d)

P(n-1)

P(n)

(e)

u_{n+1} = (n+1)2^{n+1}

(f) Or

u_n = n 2^n

d'après

P(n)

, et

u_{n-1} = (n-1)2^{n-1}

d'après

P(n-1)

.
(g)

4n 2^n - 2(n-1)2^n = (2n+2)2^n

(h)

P(0)

P(1)

sont vraies et, pour tout entier

n \geqslant 1

P(n-1)

P(n)

entraînent

P(n+1)

; par récurrence double, pour tout

n \in \mathbb{N}

u_n = n 2^n

.
Pourquoi

n \geqslant 1

: l'hypothèse porte sur le rang

n - 1

, qui n'existe que si

n \geqslant 1

, et la relation

u_{n+1} = 4u_n - 4u_{n-1}

n'est donnée que pour

n \geqslant 1

. Avec

n = 0

, la ligne (d) parlerait de

P(-1)

et le calcul de

u_{-1}

.
Pourquoi les rangs

0

1

: le premier pas,

n = 1

, réclame

P(0)

P(1)

pour produire

P(2)

, et aucun pas ne produit

P(1)

. C'est la récurrence double «

P(n)

P(n+1)

entraînent

P(n+2)

pour tout

n \in \mathbb{N}

», écrite avec un rang de décalage : ses initialisations sont les mêmes.

Exercice 3Rédaction

Une formule explicite avec un terme de signe alterné

Soit

(u_n)

la suite définie par

u_0 = 0

u_1 = 5

et, pour tout

n \in \mathbb{N}

u_{n+2} = u_{n+1} + 6u_n

. Montrer que pour tout

n \in \mathbb{N}

u_n = 3^n - (-2)^n

Voir le corrigé

Pour tout

n \in \mathbb{N}

, notons

P(n)

la proposition :

u_n = 3^n - (-2)^n

.
Initialisation. D'une part

u_0 = 0

, d'autre part

3^0 - (-2)^0 = 1 - 1 = 0

; donc

P(0)

est vraie.
D'une part

u_1 = 5

, d'autre part

3^1 - (-2)^1 = 3 + 2 = 5

; donc

P(1)

est vraie.
Ainsi

P(0)

P(1)

sont vraies.
Hérédité. Soit

n \in \mathbb{N}

tel que

P(n)

P(n+1)

soient vraies. Montrons que

P(n+2)

est vraie, c'est-à-dire que

u_{n+2} = 3^{n+2} - (-2)^{n+2}

.
Par définition de la suite,

u_{n+2} = u_{n+1} + 6u_n

.
Or

u_{n+1} = 3^{n+1} - (-2)^{n+1}

d'après

P(n+1)

, et

u_n = 3^n - (-2)^n

d'après

P(n)

.
Donc

u_{n+2} = 3^{n+1} - (-2)^{n+1} + 6\left(3^n - (-2)^n\right) = \left(3^{n+1} + 6 \cdot 3^n\right) - \left((-2)^{n+1} + 6(-2)^n\right)

.
D'une part,

3^{n+1} + 6 \cdot 3^n = 3 \cdot 3^n + 6 \cdot 3^n = 9 \cdot 3^n = 3^{n+2}

.
D'autre part,

(-2)^{n+1} = (-2) \cdot (-2)^n

, donc

(-2)^{n+1} + 6(-2)^n = -2(-2)^n + 6(-2)^n = 4(-2)^n = (-2)^2 \cdot (-2)^n = (-2)^{n+2}

.
Donc

u_{n+2} = 3^{n+2} - (-2)^{n+2}

.
Ainsi

P(n+2)

est vraie.
Conclusion.

P(0)

P(1)

sont vraies et, pour tout

n \in \mathbb{N}

P(n)

P(n+1)

entraînent

P(n+2)

; par récurrence double, pour tout

n \in \mathbb{N}

u_n = 3^n - (-2)^n

.
À retenir : les puissances

(-2)^{n+1}

(-2)^{n+2}

sont ramenées à

(-2)^n

par des égalités écrites à part, la base négative restant entre parenthèses, et le calcul s'arrête sur le but exact annoncé au rang

n + 2

Exercice 4Rédaction

Minorer une suite définie par un produit

Soit

(u_n)

la suite définie par

u_0 = 1

u_1 = 2

et, pour tout

n \in \mathbb{N}

u_{n+2} = u_{n+1} u_n + 1

. Montrer que pour tout

n \in \mathbb{N}

u_n \geqslant n + 1

Voir le corrigé

Pour tout

n \in \mathbb{N}

, notons

P(n)

la proposition :

u_n \geqslant n + 1

.
Initialisation.

u_0 = 1

0 + 1 = 1

; comme

1 \geqslant 1

P(0)

est vraie.

u_1 = 2

1 + 1 = 2

; comme

2 \geqslant 2

P(1)

est vraie.
Ainsi

P(0)

P(1)

sont vraies.
Hérédité. Soit

n \in \mathbb{N}

tel que

P(n)

P(n+1)

soient vraies. Montrons que

P(n+2)

est vraie, c'est-à-dire que

u_{n+2} \geqslant n + 3

.
Par définition de la suite,

u_{n+2} = u_{n+1} u_n + 1

.
D'après

P(n)

u_n \geqslant n + 1

; d'après

P(n+1)

u_{n+1} \geqslant n + 2

. En particulier,

u_{n+1} \geqslant n + 2 > 0

.
En multipliant l'inégalité

u_n \geqslant n + 1

par le réel

u_{n+1}

, qui est positif, on obtient

u_{n+1} u_n \geqslant (n+1) u_{n+1}

.
En multipliant l'inégalité

u_{n+1} \geqslant n + 2

par le réel

n + 1

, qui est positif, on obtient

(n+1) u_{n+1} \geqslant (n+1)(n+2)

.
Par transitivité,

u_{n+1} u_n \geqslant (n+1)(n+2)

, donc

u_{n+2} \geqslant (n+1)(n+2) + 1

.
Or

(n+1)(n+2) + 1 - (n+3) = n^2 + 2n = n(n+2)

, qui est positif car

n \geqslant 0

; donc

(n+1)(n+2) + 1 \geqslant n + 3

.
Par transitivité,

u_{n+2} \geqslant n + 3

; ainsi

P(n+2)

est vraie.
Conclusion.

P(0)

P(1)

sont vraies et, pour tout

n \in \mathbb{N}

P(n)

P(n+1)

entraînent

P(n+2)

; par récurrence double, pour tout

n \in \mathbb{N}

u_n \geqslant n + 1

.
À retenir : les deux inégalités fournies par l'hypothèse ne se multiplient pas membre à membre sans contrôle des signes ; on les multiplie une à une par un facteur dont la positivité est écrite.

Exercice 5Rédaction

Des carrés, avec la seule récurrence simple

Soit

(u_n)

la suite définie par

u_0 = 1

u_1 = 4

et, pour tout

n \in \mathbb{N}

u_{n+2} = 2u_{n+1} - u_n + 2

. Montrer que pour tout

n \in \mathbb{N}

u_n = (n+1)^2

, en n'invoquant que le principe de récurrence simple.

Voir le corrigé

Pour tout

n \in \mathbb{N}

, notons

P(n)

la proposition :

u_n = (n+1)^2

, et

Q(n)

la proposition :

P(n)

P(n+1)

.
Montrons par récurrence simple que

Q(n)

est vraie pour tout

n \in \mathbb{N}

.
Initialisation. D'une part

u_0 = 1

, d'autre part

(0+1)^2 = 1

; donc

P(0)

est vraie.
D'une part

u_1 = 4

, d'autre part

(1+1)^2 = 4

; donc

P(1)

est vraie.
Ainsi

Q(0)

est vraie.
Hérédité. Soit

n \in \mathbb{N}

tel que

Q(n)

soit vraie. Montrons

Q(n+1)

, c'est-à-dire

P(n+1)

P(n+2)

P(n+1)

est vraie, car elle fait partie de

Q(n)

.
Montrons

P(n+2)

, c'est-à-dire

u_{n+2} = (n+3)^2

.
Par définition de la suite,

u_{n+2} = 2u_{n+1} - u_n + 2

.
D'après

P(n+1)

, contenue dans

Q(n)

u_{n+1} = (n+2)^2

; d'après

P(n)

, contenue dans

Q(n)

u_n = (n+1)^2

.
Donc

u_{n+2} = 2(n+2)^2 - (n+1)^2 + 2 = 2n^2 + 8n + 8 - n^2 - 2n - 1 + 2 = n^2 + 6n + 9 = (n+3)^2

.
Ainsi

P(n+2)

est vraie.
Comme

P(n+1)

P(n+2)

sont vraies,

Q(n+1)

est vraie.
Conclusion.

Q(0)

est vraie et, pour tout

n \in \mathbb{N}

Q(n)

entraîne

Q(n+1)

; par récurrence simple,

Q(n)

est vraie pour tout

n \in \mathbb{N}

. En particulier,

P(n)

est vraie pour tout

n \in \mathbb{N}

, c'est-à-dire que pour tout

n \in \mathbb{N}

u_n = (n+1)^2

.
À retenir : la consigne interdit le principe de récurrence double, pas l'usage de deux rangs ; on les réunit dans la seule proposition

Q(n)

, puis la conclusion redescend de

Q

P

Exercice 6Trouver l'erreur

Relire une minoration de la suite de Fibonacci

Soit

(F_n)

la suite définie par

F_0 = 0

F_1 = 1

et, pour tout

n \in \mathbb{N}

F_{n+2} = F_{n+1} + F_n

. Un étudiant affirme que pour tout

n \in \mathbb{N}

F_n \geqslant n

, et rédige :
« Pour tout

n \in \mathbb{N}

, notons

P(n)

la proposition :

F_n \geqslant n

.
Initialisation.

F_0 = 0

0 \geqslant 0

, donc

P(0)

est vraie ;

F_1 = 1

1 \geqslant 1

, donc

P(1)

est vraie.
Hérédité. Soit

n \in \mathbb{N}

tel que

P(n)

P(n+1)

soient vraies. Montrons que

P(n+2)

est vraie, c'est-à-dire que

F_{n+2} \geqslant n + 2

.
Par définition de la suite,

F_{n+2} = F_{n+1} + F_n

.
D'après

P(n+1)

F_{n+1} \geqslant n + 1

; d'après

P(n)

F_n \geqslant n

.
En ajoutant membre à membre ces deux inégalités,

F_{n+1} + F_n \geqslant 2n + 1

, c'est-à-dire

F_{n+2} \geqslant 2n + 1

.
Or

2n + 1 \geqslant n + 2

, donc

F_{n+2} \geqslant n + 2

; ainsi

P(n+2)

est vraie.
Conclusion.

P(0)

P(1)

sont vraies et, pour tout

n \in \mathbb{N}

P(n)

P(n+1)

entraînent

P(n+2)

; par récurrence double, pour tout

n \in \mathbb{N}

F_n \geqslant n

. »
Trouver l'erreur et expliquer pourquoi elle invalide la démonstration. L'affirmation est-elle vraie ? Rédiger enfin une démonstration correcte de ce que ce raisonnement permet réellement d'établir.

Voir le corrigé

L'erreur est à la ligne « Or

2n + 1 \geqslant n + 2

». Cette inégalité équivaut à

n \geqslant 1

: elle est fausse pour

n = 0

, où elle s'écrit

1 \geqslant 2

.
Pourquoi elle invalide la preuve. L'hérédité n'est établie que pour

n \geqslant 1

. Or c'est le pas

n = 0

qui doit produire

P(2)

à partir de

P(0)

et de

P(1)

. Sans lui, le premier pas disponible,

n = 1

, réclame

P(1)

P(2)

, et

P(2)

n'est démontrée nulle part : la récurrence ne dépasse pas les rangs initialisés.
L'affirmation est fausse :

F_2 = F_1 + F_0 = 1

1 < 2

. De même,

F_3 = 2 < 3

F_4 = 3 < 4

.
Ce que l'on démontre réellement. L'hérédité rédigée vaut pour tout

n \geqslant 1

; il faut donc l'initialiser à deux rangs consécutifs, supérieurs ou égaux à

1

, où l'inégalité est vraie. Les relations donnent

F_5 = 5

F_6 = 8

, d'où le résultat suivant.
Montrons que pour tout entier

n \geqslant 5

F_n \geqslant n

.
Pour tout entier

n \geqslant 5

, notons

P(n)

la proposition :

F_n \geqslant n

.
Initialisation. Par la relation de récurrence,

F_2 = 1

F_3 = 2

F_4 = 3

F_5 = 5

F_6 = 8

. Comme

5 \geqslant 5

P(5)

est vraie ; comme

8 \geqslant 6

P(6)

est vraie.
Hérédité. Soit

n

un entier supérieur ou égal à

5

tel que

P(n)

P(n+1)

soient vraies. Montrons que

F_{n+2} \geqslant n + 2

.
Par définition de la suite,

F_{n+2} = F_{n+1} + F_n

.
D'après

P(n+1)

F_{n+1} \geqslant n + 1

; d'après

P(n)

F_n \geqslant n

.
En ajoutant membre à membre ces deux inégalités,

F_{n+2} \geqslant 2n + 1

.
Or

2n + 1 - (n + 2) = n - 1

, et

n - 1 \geqslant 4

car

n \geqslant 5

; donc

2n + 1 \geqslant n + 2

.
Par transitivité,

F_{n+2} \geqslant n + 2

; ainsi

P(n+2)

est vraie.
Conclusion.

P(5)

P(6)

sont vraies et, pour tout entier

n \geqslant 5

P(n)

P(n+1)

entraînent

P(n+2)

; par récurrence double, pour tout entier

n \geqslant 5

F_n \geqslant n

. Comme

F_0 = 0

F_1 = 1

, l'inégalité

F_n \geqslant n

est vraie pour tout entier naturel

n

sauf

2

3

4

.
À retenir : chaque inégalité de l'hérédité doit être vraie pour tous les entiers auxquels on l'applique, à commencer par le rang de la première initialisation.

Exercice 7Trouver l'erreur

Relire une formule explicite pour une relation à trois termes

Soit

(t_n)

la suite définie par

t_0 = 0

t_1 = 1

t_2 = 3

et, pour tout

n \in \mathbb{N}

t_{n+3} = 2t_{n+2} + t_{n+1} - 2t_n

. Pour montrer que pour tout

n \in \mathbb{N}

t_n = 2^n - 1

, une copie rédige :
« Pour tout

n \in \mathbb{N}

, notons

P(n)

la proposition :

t_n = 2^n - 1

.
Initialisation.

t_0 = 0 = 2^0 - 1

, donc

P(0)

est vraie ;

t_1 = 1 = 2^1 - 1

, donc

P(1)

est vraie.
Hérédité. Soit

n \in \mathbb{N}

tel que

P(n)

P(n+1)

P(n+2)

soient vraies. Montrons que

P(n+3)

est vraie, c'est-à-dire que

t_{n+3} = 2^{n+3} - 1

.
Par définition de la suite,

t_{n+3} = 2t_{n+2} + t_{n+1} - 2t_n

.
D'après

P(n+2)

P(n+1)

P(n)

t_{n+3} = 2\left(2^{n+2} - 1\right) + \left(2^{n+1} - 1\right) - 2\left(2^n - 1\right)

.
Donc

t_{n+3} = 2^{n+3} - 2 + 2^{n+1} - 1 - 2^{n+1} + 2 = 2^{n+3} - 1

; ainsi

P(n+3)

est vraie.
Conclusion.

P(0)

P(1)

sont vraies et, pour tout

n \in \mathbb{N}

P(n)

P(n+1)

P(n+2)

entraînent

P(n+3)

; par récurrence d'ordre

3

, pour tout

n \in \mathbb{N}

t_n = 2^n - 1

. »
Le résultat annoncé est exact, mais la démonstration contient une erreur. La trouver, montrer qu'elle n'est pas de pure forme, puis rédiger la démonstration correcte.

Voir le corrigé

L'erreur est dans l'initialisation : seules

P(0)

P(1)

sont vérifiées, alors que l'hérédité suppose trois rangs consécutifs. Au premier pas,

n = 0

, elle réclame

P(0)

P(1)

P(2)

; or

P(2)

n'a jamais été établie. La chaîne ne démarre donc pas, et la conclusion par récurrence d'ordre

3

n'est pas justifiée, bien que le calcul de l'hérédité soit juste.
L'erreur n'est pas de pure forme. Soit

(s_n)

la suite définie par

s_0 = 0

s_1 = 1

s_2 = 4

et la même relation

s_{n+3} = 2s_{n+2} + s_{n+1} - 2s_n

. En remplaçant

t

par

s

, la copie se recopie mot pour mot :

s_0 = 2^0 - 1

s_1 = 2^1 - 1

, et le calcul d'hérédité est identique. Elle « démontrerait » que

s_n = 2^n - 1

pour tout

n

, alors que

s_2 = 4

2^2 - 1 = 3

. Un raisonnement qui conduit, recopié tel quel, à un résultat faux ne démontre rien.
Rédaction correcte.
Pour tout

n \in \mathbb{N}

, notons

P(n)

la proposition :

t_n = 2^n - 1

.
Initialisation.

t_0 = 0 = 2^0 - 1

, donc

P(0)

est vraie ;

t_1 = 1 = 2^1 - 1

, donc

P(1)

est vraie ;

t_2 = 3 = 2^2 - 1

, donc

P(2)

est vraie.
Hérédité. Soit

n \in \mathbb{N}

tel que

P(n)

P(n+1)

P(n+2)

soient vraies. Montrons que

P(n+3)

est vraie, c'est-à-dire que

t_{n+3} = 2^{n+3} - 1

.
Par définition de la suite,

t_{n+3} = 2t_{n+2} + t_{n+1} - 2t_n

.
D'après

P(n+2)

t_{n+2} = 2^{n+2} - 1

; d'après

P(n+1)

t_{n+1} = 2^{n+1} - 1

; d'après

P(n)

t_n = 2^n - 1

.
Donc

t_{n+3} = 2\left(2^{n+2} - 1\right) + \left(2^{n+1} - 1\right) - 2\left(2^n - 1\right) = 2^{n+3} - 2 + 2^{n+1} - 1 - 2^{n+1} + 2 = 2^{n+3} - 1

.
Ainsi

P(n+3)

est vraie.
Conclusion.

P(0)

P(1)

P(2)

sont vraies et, pour tout

n \in \mathbb{N}

P(n)

P(n+1)

P(n+2)

entraînent

P(n+3)

; par récurrence d'ordre

3

, pour tout

n \in \mathbb{N}

t_n = 2^n - 1

.
À retenir : on compte les rangs que suppose l'hérédité, et l'on rédige exactement autant d'initialisations consécutives.

Exercice 8Approfondissement

Récurrences d'ordre p : le principe, ses initialisations, une application

Soit

p \geqslant 1

un entier et

n_0 \in \mathbb{N}

. Pour tout entier

n \geqslant n_0

, soit

P(n)

une proposition. On considère les deux hypothèses suivantes.
(H1) Les propositions

P(n_0), P(n_0+1), \dots, P(n_0+p-1)

sont vraies.
(H2) Pour tout entier

n \geqslant n_0

, si

P(n), P(n+1), \dots, P(n+p-1)

sont vraies, alors

P(n+p)

est vraie.
1) En n'invoquant que le principe de récurrence simple, démontrer que (H1) et (H2) entraînent que

P(n)

est vraie pour tout entier

n \geqslant n_0

.
2) On suppose ici

p \geqslant 2

n_0 = 0

. Soit

j \in \{0, 1, \dots, p-1\}

. Construire une propriété

P

qui vérifie (H2), qui est vraie en chacun des rangs

0, 1, \dots, p-1

distincts de

j

, et qui n'est pas vraie pour tout

n \in \mathbb{N}

. On pourra examiner la proposition «

n \neq j

». Qu'en conclut-on sur l'initialisation d'une récurrence d'ordre

p

?
3) Soit

(u_n)

une suite réelle telle que, pour tout

n \in \mathbb{N}

u_{n+2} = u_{n+1} + 2u_n

. Montrer qu'il existe deux réels

\lambda

\mu

tels que, pour tout

n \in \mathbb{N}

u_n = \lambda 2^n + \mu (-1)^n

Voir le corrigé

1) Pour tout entier

n \geqslant n_0

, notons

Q(n)

la proposition : pour tout

k \in \{0, 1, \dots, p-1\}

P(n+k)

est vraie. Autrement dit,

P(n), P(n+1), \dots, P(n+p-1)

sont vraies.
Montrons par récurrence simple que

Q(n)

est vraie pour tout entier

n \geqslant n_0

.
Initialisation.

Q(n_0)

affirme que

P(n_0), \dots, P(n_0+p-1)

sont vraies : c'est exactement (H1). Donc

Q(n_0)

est vraie.
Hérédité. Soit

n \geqslant n_0

un entier tel que

Q(n)

soit vraie. Montrons

Q(n+1)

, c'est-à-dire que

P(n+1+k)

est vraie pour tout

k \in \{0, 1, \dots, p-1\}

.
Soit

k \in \{0, 1, \dots, p-1\}

. Deux cas se présentent, qui couvrent toutes les valeurs de

k

(si

p = 1

, seul le second existe).
Premier cas :

k \leqslant p-2

. Alors

k + 1 \in \{1, \dots, p-1\}

, donc

P(n+(k+1))

figure dans

Q(n)

: elle est vraie.
Second cas :

k = p-1

. Alors

n + 1 + k = n + p

. Comme

n \geqslant n_0

et que

P(n), \dots, P(n+p-1)

sont vraies d'après

Q(n)

, l'hypothèse (H2) appliquée à cet entier

n

montre que

P(n+p)

est vraie.
Ainsi

P(n+1+k)

est vraie pour tout

k \in \{0, 1, \dots, p-1\}

, donc

Q(n+1)

est vraie.
Conclusion.

Q(n_0)

est vraie et, pour tout entier

n \geqslant n_0

Q(n)

entraîne

Q(n+1)

; par récurrence simple,

Q(n)

est vraie pour tout entier

n \geqslant n_0

. En particulier, en prenant

k = 0

P(n)

est vraie pour tout entier

n \geqslant n_0

.
2) Pour tout

n \in \mathbb{N}

, notons

P(n)

la proposition :

n \neq j

.
Rangs initiaux. Pour tout

k \in \{0, 1, \dots, p-1\}

distinct de

j

P(k)

est vraie. En revanche

P(j)

est fausse, donc

P

n'est pas vraie pour tout

n \in \mathbb{N}

.
Vérifions (H2). Soit

n \in \mathbb{N}

tel que

P(n), P(n+1), \dots, P(n+p-1)

soient vraies. Montrons que

P(n+p)

est vraie, c'est-à-dire que

n + p \neq j

.
Comme

n \geqslant 0

j \leqslant p - 1

, on a

n + p \geqslant p > p - 1 \geqslant j

, donc

n + p \neq j

P(n+p)

est vraie, et (H2) est vérifiée.
L'hypothèse sur les rangs

n

n+p-1

n'a d'ailleurs pas servi : le seul rang où

P

est fausse,

j

, est inférieur à

p

, si bien que

P(n+p)

est vraie pour tout

n \in \mathbb{N}

.
Conclusion. Pour chaque rang

j

, cette propriété satisfait l'hérédité d'ordre

p

et toutes les initialisations sauf celle du rang

j

, sans être vraie partout. Aucune des

p

initialisations ne peut donc être omise : une récurrence d'ordre

p

exige les

p

rangs consécutifs

P(n_0), \dots, P(n_0+p-1)

. Pour

p = 2

j = 1

, c'est l'initialisation aux seuls rangs

0

2

qui est mise en défaut.
3) Analyse. Soient

\lambda

\mu

deux réels tels que, pour tout

n \in \mathbb{N}

u_n = \lambda 2^n + \mu (-1)^n

. Aux rangs

0

1

, on obtient

\lambda + \mu = u_0

2\lambda - \mu = u_1

.
En ajoutant ces deux égalités,

3\lambda = u_0 + u_1

, donc

\lambda = \frac{u_0 + u_1}{3}

, puis

\mu = u_0 - \lambda = \frac{2u_0 - u_1}{3}

. Seul ce couple peut convenir ; il reste à vérifier qu'il convient.
Synthèse. Posons

\lambda = \frac{u_0 + u_1}{3}

\mu = \frac{2u_0 - u_1}{3}

, réels fixés dans toute la suite. Pour tout

n \in \mathbb{N}

, notons

P(n)

la proposition :

u_n = \lambda 2^n + \mu (-1)^n

. Montrons par récurrence double que

P(n)

est vraie pour tout

n \in \mathbb{N}

.
Initialisation.

\lambda 2^0 + \mu (-1)^0 = \lambda + \mu = \frac{u_0 + u_1 + 2u_0 - u_1}{3} = u_0

, donc

P(0)

est vraie.

\lambda 2^1 + \mu (-1)^1 = 2\lambda - \mu = \frac{2u_0 + 2u_1 - 2u_0 + u_1}{3} = u_1

, donc

P(1)

est vraie.
Ainsi

P(0)

P(1)

sont vraies.
Hérédité. Soit

n \in \mathbb{N}

tel que

P(n)

P(n+1)

soient vraies. Montrons que

P(n+2)

est vraie, c'est-à-dire que

u_{n+2} = \lambda 2^{n+2} + \mu (-1)^{n+2}

.
Par hypothèse sur la suite,

u_{n+2} = u_{n+1} + 2u_n

.
D'après

P(n+1)

u_{n+1} = \lambda 2^{n+1} + \mu (-1)^{n+1}

; d'après

P(n)

u_n = \lambda 2^n + \mu (-1)^n

.
Donc

u_{n+2} = \lambda 2^{n+1} + \mu (-1)^{n+1} + 2\lambda 2^n + 2\mu (-1)^n

.
Or

\lambda 2^{n+1} + 2\lambda 2^n = 2\lambda 2^{n+1} = \lambda 2^{n+2}

, et

\mu (-1)^{n+1} + 2\mu (-1)^n = -\mu (-1)^n + 2\mu (-1)^n = \mu (-1)^n = \mu (-1)^{n+2}

.
Donc

u_{n+2} = \lambda 2^{n+2} + \mu (-1)^{n+2}

; ainsi

P(n+2)

est vraie.
Conclusion.

P(0)

P(1)

sont vraies et, pour tout

n \in \mathbb{N}

P(n)

P(n+1)

entraînent

P(n+2)

; par récurrence double, cas

p = 2

de la question 1),

P(n)

est vraie pour tout

n \in \mathbb{N}

. Les réels

\lambda

\mu

ainsi posés conviennent, ce qui prouve l'existence demandée.
À retenir : une récurrence d'ordre

p

se ramène à une récurrence simple sur les

p

derniers rangs, ses

p

initialisations sont toutes indispensables, et deux constantes se déterminent par analyse sur les deux rangs de départ, la récurrence double assurant la synthèse.

QCM

12 questions : clique sur une réponse pour voir la correction.

Question 1

Soit

(u_n)

la suite définie par ses deux premiers termes

u_0

u_1

et, pour tout

n \in \mathbb{N}

, par

u_{n+2} = u_{n+1} - 3u_n

. Pour démontrer par récurrence double une propriété

P(n)

de tous ses termes, quelles initialisations faut-il rédiger ?

Question 2

La suite

(u_n)

est définie par

u_0

u_1

et une relation exprimant

u_{n+2}

à l'aide de

u_{n+1}

et de

u_n

. Les propositions

P(0)

P(1)

ont été vérifiées. Quelle première ligne d'hérédité est correcte ?

Question 3

Soit

(u_n)

la suite définie par

u_0 = 1

u_1 = 2

et, pour tout entier

n \geqslant 1

u_{n+1} = 4u_n - 4u_{n-1}

. Une copie vérifie

P(0)

P(1)

, où

P(n)

est la proposition «

u_n = 2^n

», puis écrit : « Soit

n \geqslant 1

tel que

P(n)

soit vraie. Montrons

P(n+1)

. On a

u_{n+1} = 4u_n - 4u_{n-1} = 4 \cdot 2^n - 4 \cdot 2^{n-1} = 2^{n+1}

. » Quel reproche est fondé ?

Question 4

Pour ramener une récurrence double sur

P

à une récurrence simple, quelle proposition

Q(n)

faut-il poser ?

Question 5

Pour une suite donnée par

u_0

u_1

et une relation exprimant

u_{n+2}

à l'aide de

u_{n+1}

et de

u_n

, on raisonne par récurrence simple sur

Q(n)

: «

P(n)

P(n+1)

». L'hérédité commence par « Soit

n \in \mathbb{N}

tel que

Q(n)

soit vraie. Montrons

Q(n+1)

. » Que reste-t-il à faire ?

Question 6

Une relation exprime

u_{n+4}

à l'aide de

u_{n+3}

u_{n+2}

u_{n+1}

u_n

, pour tout

n \in \mathbb{N}

. Pour démontrer une propriété

P(n)

de tous les termes par récurrence d'ordre

4

, quelle initialisation faut-il ?

Question 7

Une copie vérifie

P(0)

P(1)

, puis établit que pour tout entier

n \geqslant 1

P(n)

P(n+1)

entraînent

P(n+2)

. Qu'a-t-elle démontré ?

Question 8

La suite

(u_n)_{n \geqslant 1}

est définie par

u_1

u_2

et, pour tout entier

n \geqslant 1

u_{n+2} = 2u_{n+1} + u_n

. Les propositions

P(1)

P(2)

ont été vérifiées. Quelle hérédité convient ?

Question 9

Une copie vérifie seulement

P(0)

, puis démontre que pour tout

n \in \mathbb{N}

P(n)

P(n+1)

entraînent

P(n+2)

. Pourquoi n'en tire-t-elle aucun rang nouveau ?

Question 10

Une copie vérifie

P(0)

, puis démontre que pour tout

n \in \mathbb{N}

P(n)

entraîne

P(n+2)

. Qu'a-t-elle démontré ?

Question 11

Une récurrence simple vient d'établir

Q(0)

et, pour tout

n \in \mathbb{N}

, que

Q(n)

entraîne

Q(n+1)

, où

Q(n)

est la proposition «

P(n)

P(n+1)

». On voulait montrer

P(n)

pour tout

n \in \mathbb{N}

. Quelle conclusion écrire ?

Question 12

Pour démontrer une propriété de tous les termes d'une suite, quelle relation appelle une récurrence double, et non une récurrence simple, d'ordre

3

ou forte ?