Raisonnement par récurrence

1. Le principe de récurrence

Principe de récurrence : Soit P(n) une propriété dépendant d'un entier n. Pour démontrer que P(n) est vraie pour tout entier n n_0, il suffit de vérifier :

Initialisation : P(n_0) est vraie.
Hérédité : pour tout n n_0, si P(n) est vraie alors P(n+1) est vraie.

Si ces deux conditions sont remplies, alors P(n) est vraie pour tout entier n n_0.

Analogie des dominos : Le principe de récurrence fonctionne comme une file infinie de dominos :

L'initialisation fait tomber le premier domino.
L'hérédité garantit que chaque domino qui tombe entraîne la chute du suivant.
Donc tous les dominos tombent.

Attention : Les deux étapes sont indispensables :

Sans initialisation, l'hérédité seule ne prouve rien (les dominos ne démarrent jamais).
Sans hérédité, l'initialisation seule ne donne la propriété qu'en un seul point.

2. Rédaction rigoureuse d'une récurrence

Méthode : rédiger une démonstration par récurrence : Voici le plan de rédaction à suivre scrupuleusement :

1. Énoncer la propriété : « Pour tout n n_0, posons P(n) : … »

2. Initialisation : « Pour n = n_0 : … ». Calculer chaque membre et vérifier l'égalité (ou l'inégalité). Conclure : « P(n_0) est vraie. »

3. Hérédité : « Soit n n_0 fixé. Supposons P(n) vraie (hypothèse de récurrence). Montrons que P(n+1) est vraie. » Puis effectuer le calcul en utilisant l'hypothèse de récurrence. Conclure : « P(n+1) est vraie. »

4. Conclusion : « Par le principe de récurrence, P(n) est vraie pour tout n n_0. »

Erreurs classiques à éviter :

Oublier d'énoncer P(n) clairement avant de commencer.
Confondre « P(n) est vraie pour tout n » (ce qu'on veut prouver) avec « supposons P(n) vraie pour un n fixé » (hypothèse de récurrence).
Ne pas utiliser l'hypothèse de récurrence dans l'étape d'hérédité.
Vérifier P(n+1) directement sans partir de l'hypothèse P(n) — ce n'est pas une récurrence !
Oublier la conclusion : il faut toujours terminer par la phrase de conclusion.

3. Récurrence simple : exemples variés

3.1 Récurrence et sommes

Exemple 1 : Somme des carrés : Montrer que pour tout n 1 : _{k=1}^{n} k^2 = n(n+1)(2n+1){6}.

Posons P(n) : « _{k=1}^{n} k^2 = n(n+1)(2n+1){6} ».

Initialisation (n = 1) : _{k=1}^{1} k^2 = 1 et 1 2 3{6} = 1. P(1) est vraie. ✓

Hérédité : supposons P(n) vraie pour un n 1 fixé. Alors :

[formule]

C'est bien P(n+1). ✓

Conclusion : par récurrence, P(n) est vraie pour tout n 1.

3.2 Récurrence et divisibilité

Exemple 2 : Divisibilité : Montrer que pour tout n 0 : 4^n - 1 est divisible par 3.

Posons P(n) : « 3 (4^n - 1) » (c'est-à-dire 4^n - 1 est un multiple de 3).

Initialisation (n = 0) : 4^0 - 1 = 0 = 3 0. P(0) est vraie. ✓

Hérédité : supposons P(n) vraie, c'est-à-dire 4^n - 1 = 3k pour un certain k Z.

4^{n+1} - 1 = 4 4^n - 1 = 4(4^n - 1) + 4 - 1 = 4 3k + 3 = 3(4k + 1)

Donc 4^{n+1} - 1 est divisible par 3. P(n+1) est vraie. ✓

Conclusion : par récurrence, 3 (4^n - 1) pour tout n 0.

Méthode : récurrence et divisibilité : Pour montrer que a^n - b^n est divisible par (a - b), on écrit :

[formule]

On utilise l'hypothèse de récurrence sur a^n - b^n et on factorise.

3.3 Récurrence et inégalités

Exemple 3 : Inégalité : Montrer que pour tout n 5 : 2^n > n^2.

Posons P(n) : « 2^n > n^2 ».

Initialisation (n = 5) : 2^5 = 32 et 5^2 = 25. On a bien 32 > 25. P(5) est vraie. ✓

Hérédité : supposons 2^n > n^2 pour un n 5 fixé.

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

Il suffit de montrer que 2n^2 (n+1)^2 = n^2 + 2n + 1, c'est-à-dire n^2 - 2n - 1 0.

Or n^2 - 2n - 1 = (n-1)^2 - 2 (5-1)^2 - 2 = 14 > 0 pour n 5.

Donc 2^{n+1} > 2n^2 (n+1)^2. P(n+1) est vraie. ✓

Conclusion : par récurrence, 2^n > n^2 pour tout n 5.

3.4 Récurrence et suites récurrentes

Exemple 4 : Suite récurrente : Soit (u_n) définie par u_0 = 1 et u_{n+1} = 2u_n + 3. Montrer que pour tout n 0 : u_n = 4 2^n - 3.

Posons P(n) : « u_n = 4 2^n - 3 ».

Initialisation (n = 0) : u_0 = 1 et 4 2^0 - 3 = 4 - 3 = 1. P(0) est vraie. ✓

Hérédité : supposons u_n = 4 2^n - 3.

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

P(n+1) est vraie. ✓

Conclusion : par récurrence, u_n = 4 2^n - 3 pour tout n 0.

4. Récurrence forte (récurrence double)

Récurrence forte / récurrence double : Lorsque l'hérédité nécessite de connaître deux rangs consécutifs (par exemple pour une suite définie par u_{n+2} = f(u_n, u_{n+1})), on utilise la récurrence forte :

Initialisation : vérifier P(n_0) et P(n_0 + 1).
Hérédité : supposer P(n) et P(n+1) vraies pour un n n_0 fixé, puis montrer P(n+2).

Si ces conditions sont vérifiées, P(n) est vraie pour tout n n_0.

Exemple 5 : Suite de Fibonacci : La suite de Fibonacci est définie par F_0 = 0, F_1 = 1 et F_{n+2} = F_{n+1} + F_n.

Montrer que pour tout n 0 : F_n 2^n.

Posons P(n) : « F_n 2^n ».

Initialisation :

P(0) : F_0 = 0 1 = 2^0 ✓
P(1) : F_1 = 1 2 = 2^1 ✓

Hérédité : supposons P(n) et P(n+1) vraies pour un n 0 fixé, c'est-à-dire F_n 2^n et F_{n+1} 2^{n+1}.

F_{n+2} = F_{n+1} + F_n 2^{n+1} + 2^n = 2 2^n + 2^n = 3 2^n 4 2^n = 2^{n+2}

Donc F_{n+2} 2^{n+2}. P(n+2) est vraie. ✓

Conclusion : par récurrence forte, F_n 2^n pour tout n 0.

Quand utiliser la récurrence forte ? : La récurrence forte est nécessaire lorsque :

La suite est définie par une relation de récurrence d'ordre 2 : u_{n+2} = f(u_n, u_{n+1})
La propriété au rang n+2 dépend à la fois des rangs n et n+1
On a besoin de deux hypothèses pour conclure

Dans ce cas, il faut deux initialisations au lieu d'une seule.

5. Variantes et compléments

Récurrence à partir d'un rang quelconque : Le principe de récurrence fonctionne à partir de n'importe quel rang n_0 Z. Il suffit d'initialiser à n_0 et de montrer l'hérédité pour n n_0.

Il arrive souvent que la propriété ne soit vraie qu'à partir d'un certain rang : n 2, n 3, etc.

Méthode : trouver le bon rang d'initialisation :

Vérifier pour quelles valeurs de n la propriété a un sens (par exemple, n! n'est défini que pour n 0).
Tester les premières valeurs pour identifier le rang à partir duquel la propriété est vraie.
Initialiser au bon rang n_0.

Exemple 6 : Inégalité avec factorielle : Montrer que pour tout n 4 : n! > 2^n.

Posons P(n) : « n! > 2^n ».

Initialisation (n = 4) : 4! = 24 et 2^4 = 16. On a 24 > 16. P(4) est vraie. ✓

Hérédité : supposons n! > 2^n pour un n 4 fixé.

(n+1)! = (n+1) n! > (n+1) 2^n

Or n+1 5 > 2, donc (n+1) 2^n > 2 2^n = 2^{n+1}.

Ainsi (n+1)! > 2^{n+1}. P(n+1) est vraie. ✓

Conclusion : par récurrence, n! > 2^n pour tout n 4.

À retenir

Résumé :

Principe de récurrence : pour montrer P(n) pour tout n n_0, on vérifie P(n_0) (initialisation) et on montre P(n) P(n+1) (hérédité)
Rédaction : toujours énoncer P(n), faire l'initialisation par calcul, écrire l'hypothèse de récurrence, montrer P(n+1), puis conclure
Applications : la récurrence sert à prouver des formules de sommes, des propriétés de divisibilité, des inégalités, et des propriétés de suites récurrentes
Récurrence forte : quand l'hérédité nécessite deux rangs (P(n) et P(n+1) pour montrer P(n+2)), on initialise à deux rangs consécutifs
Erreurs à éviter : ne pas oublier d'énoncer P(n), toujours utiliser l'hypothèse de récurrence dans l'hérédité, ne pas oublier la conclusion
Rang d'initialisation : la récurrence peut démarrer à n'importe quel rang n_0 ; il faut choisir le bon rang selon la propriété