Hypothèse de récurrence : la formule et un exemple

Ce que dit la formule

Dans l'hérédité, on suppose que $P (n)$ P(n) est vraie pour un certain $n$ n : c'est l'hypothèse de récurrence. On l'utilise pour démontrer $P (n + 1)$ P(n+1).

On part en général de l'expression au rang $n + 1$ n+1, et on fait apparaître l'expression du rang $n$ n pour appliquer l'hypothèse.

Exemple

Hypothèse :

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

1 + … + n = (n(n+1))/2. Alors

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

1 + … + n + (n+1) = (n(n+1))/2 + (n+1) = ((n+1)(n+2))/2, qui est

P (n + 1)

P(n+1).

Piège à éviter

On utilise l'hypothèse

P (n)

P(n), on ne la redémontre pas : c'est ce qui rend la récurrence efficace.

Les autres formules de le raisonnement par récurrence

Principe de récurrence →

[P (n_{0}) vraie] et [P (n) \Rightarrow P (n + 1)] ⟹ P (n) vraie pour tout n \geq n_{0}

[ P(n₀) vraie ] et [ P(n) ⇒ P(n+1) ] ⇒ P(n) vraie pour tout n ≥ n₀

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 →