Principe de récurrence : la formule et un exemple

Ce que dit la formule

Si la propriété est vraie au rang de départ $n_{0}$ n₀ (initialisation) et si, dès qu'elle est vraie à un rang $n$ n, elle l'est aussi au rang $n + 1$ n+1 (hérédité), alors elle est vraie pour tout entier $n \geq n_{0}$ n ≥ n₀.

Image des dominos : faire tomber le premier (initialisation), et s'assurer que chaque domino fait tomber le suivant (hérédité), garantit qu'ils tombent tous.

La rédaction attendue comporte trois parties nettement séparées : l'initialisation, où l'on vérifie la propriété au premier rang ; l'hérédité, où l'on suppose la propriété vraie au rang $n$ n pour la démontrer au rang $n + 1$ n+1 ; et la conclusion.

L'hypothèse de récurrence n'est pas ce que l'on cherche à prouver globalement : on la suppose vraie à un rang donné, uniquement pour en déduire le rang suivant. C'est ce raisonnement qui déroute au départ.

Exemple

Pour démontrer

1 + 2 + \dots + n = \frac{n ( n + 1 )}{2}

1 + 2 + … + n = (n(n+1))/2 : on vérifie au rang

1

1, puis on montre l'hérédité.

Deuxième exemple

Pour démontrer que

2^{n} \geq n + 1

2ⁿ ≥ n+1 pour tout

n \geq 0

n ≥ 0 : au rang

0

1 \geq 1

1 ≥ 1 ✓. Si

2^{n} \geq n + 1

2ⁿ ≥ n+1, alors

2^{n + 1} = 2 \times 2^{n} \geq 2 (n + 1) = 2 n + 2 \geq n + 2

2ⁿ⁺¹ = 2× 2ⁿ ≥ 2(n+1) = 2n+2 ≥ n+2, qui est la propriété au rang

n + 1

n+1.

Piège à éviter

Les deux étapes sont indispensables : sans initialisation, l'hérédité seule ne prouve rien.

Les autres formules de le raisonnement par récurrence

Hypothèse de récurrence →

On suppose P (n) vraie, on d \overset{e}{ˊ} montre P (n + 1)

On suppose P(n) vraie, on démontre P(n+1)

Questions fréquentes

Pourquoi l'initialisation est-elle indispensable ?

Sans elle, l'hérédité ne prouve rien. Une propriété peut être héréditaire tout en étant fausse partout, comme

n = n + 1

n = n+1, qui se transmet d'un rang au suivant sans jamais être vraie.

À quel rang faut-il initialiser ?

Au premier rang pour lequel la propriété est annoncée. Ce n'est pas toujours

0

0 : certaines propriétés ne commencent qu'à partir de

n = 1

n = 1 ou

n = 4

n = 4.

Que suppose-t-on exactement dans l'hérédité ?

Que la propriété est vraie à un rang

n

n quelconque mais fixé, pour en déduire le rang

n + 1

n+1. On ne suppose jamais qu'elle est vraie pour tous les rangs.

Notions liées

Pour aller plus loin, explore les notions du même thème.

Tout sur suites en terminale

Raisonnement par récurrence, limites de suites, suites récurrentes et algorithmes de seuil.

Le cours

Suites : récurrence et limites — cours Terminale spé

Les notions du thème

S'entraîner

Sujets d'examen

Annales Bac Spécialité Maths Terminale

Outils et pages dédiées

Algorithme de seuil en Python

Retrouve la notion complète : définitions, méthodes et exercices corrigés.

Le raisonnement par récurrence →