Techniques et concepts de l'entreprise, de la finance et de l'économie 
(et fondements mathématiques)

La récurrence

logo

 

 

 

 

 

 

 

 

 

 

Raisonnement par récurrence

Le terme de récurrence vient d'un verbe latin qui signifie courir en arrière, mais ce n'est pas une raison pour vous sauver. En effet, vous trouverez sur cette page un mode de raisonnement. Non pas le truc qui révolutionne votre façon de penser mais une façon simple d’aborder un certain type de problème mathématique.

En terminale S, on apprend que la récurrence consiste à définir le terme d’une suite par celui qui le précède ; on l'utilise comme moyen de démonstration. Cet outil dépasse d'ailleurs largement l'étude des suites et des séries (pour l'étude des dérivées successives, par exemple). Historiquement, il est possible que le triangle de Pascal ait été son premier support.

Ainsi, une suite arithmétique est définie par une relation de type un = un-1 + r et une suite géométrique par une relation de type un = qun-1.

Utilisation avec tableur

Les tableurs sont un excellent outil pour utiliser une relation de récurrence pas trop alambiquée puisqu'il suffit d'un cliquer-glisser sur la formule (exemples simples en pages suite géométrique avec Excel et limites de suites avec Excel). La relation de récurrence peut aussi être traitée par une calculatrice (voir la page suites arithmétiques et calculatrices).

Utilisation dans les démonstrations

Le raisonnement par récurrence est souvent adapté pour démontrer un résultat dont l'énoncé commence par « pour tout n appartenant à N, on a... »

Raisonnement par récurrence

L’axiome de récurrence stipule que si une propriété P est vraie en 0 et en n ∈ N (qu’on note P(n)) et que cette véracité en n implique que P(n + 1) est également vraie, alors P(n) est vraie quel que soit n. P(n) est dite héréditaire.

Un raisonnement par récurrence réalisé dans les règles de l’art consiste à énoncer la propriété, à établir que cette dernière se vérifie pour la plus petite valeur admise de n (souvent 0 ou 1), c’est-à-dire à initialiser la récurrence puis à démontrer que la propriété est héréditaire. Enfin, on conclut.

Un petit exemple théorique ? Oui ? D’accord.

Prouver que la suite suivante est croissante sur N sachant que u0 = 0 :

exemple de suite

Énonçons la propriété à démontrer : on pose P(n) : un+1 > un.

Initialisation : calculons le premier terme. u1 = 2. Donc, P(0) est vraie puisque u1 > u0.

Hérédité : supposons que P(n) est vraie pour un entier naturel n fixé.

hérédité

Quel que soit n, un+1 > un et P(n + 1) est vraie.

Conclusion : P(0) est vraie et pour tout n entier naturel P(n) est vraie. La suite est croissante.

Deuxième exemple : soit la suite (un) définie sur N par u0 = 5 000 et un+1 = 1,04un + 1 000. Démontrer que pour tout n ∈ N on a un = 30 000 × 1,04n – 25 000 (il s'agit de vérifier le résultat de l'exercice 2 de la page suites arithmético-géométriques).

P(n) : un = 30 000 × 1,04n – 25 000

Initialisation : 30 000 × 1,040 – 25 000 = 5 000 ce qui signifie que P(0) est vraie.

Hérédité : supposons que l'égalité P(n) est vraie pour un entier n.

un+1 = 30 000 × 1,04n+1 – 25 000
⇔ un+1 = 30 000 × 1,04n+1 – 26 000 + 1 000
⇔ un+1 = 30 000 × 1,04 × 1,04n – (25 000 × 1,04) + 1 000
⇔ un+1 = 1,04(30 000 × 1,04n – 25 000) + 1 000
⇔ un+1 = 1,04un + 1 000

Donc P(n) est vraie pour tout entier n.

Vous remarquerez que l'on suppose P(n) vraie pour UN entier et que l'on conclut qu'elle l'est pour TOUT entier.

Voir d'autres exemples : somme de premiers entiers, limites des suites de type qⁿ et complexes et suites au bac S.

Compléments (hors programme de terminale S)

1- La récurrence forte

La démonstration est un peu différente. Comme pour la récurrence simple, on vérifie d’abord que P(0) est vraie. Ensuite, on vérifie que P(n) est vraie jusqu’au rang n, qu’elle est également vraie pour P(n + 1) et donc que la propriété se vérifie pour tout entier naturel.

2- La récurrence d’ordre n (processus discrets)

Si la propriété P(n + 2) dépend à la fois de P(n) et de P(n + 1), nous sommes dans le cadre d’une récurrence d’ordre 2.

Exemple.

Soit la suite (un) définie ainsi : u0 = 1, u1 = 3, un+2 = 4un+1 – 3un.

Montrer que, ∀ nN, un = 3n.

Initialisation : la proposition est vraie pour u0 qui est égal à 30 et pour u1 qui est égal à 31.

Hérédité : considérons la proposition comme vraie. Nous avons donc un qui est égal à 3n et un+1 qui est égal à 3n+1.

Donc, un+2 = (4 × 3n+1) – (3 × 3n) = 3n[(4 × 3) – 3] = 3n × 9 = 3n × 32 = 3n+2.

Nous avons montré par récurrence que P(n + 2) était vraie.

3- Applications statistiques et professionnelles

On peut définir une prévision par régression linéaire simple non par sa droite de tendance de type y = at + b mais comme yn = yn-1 + a (n étant un entier naturel, correspondant ici à une date), c'est-à-dire en utilisant la prévision précédente.

Ce mode de calcul est utilisé dans certaines techniques prévisionnelles, notamment les lissages exponentiels (LES, LED, lissage de Holt, lissage de Winters additif, lissage de Winters multiplicatif). Un lissage exponentiel peut être défini par une relation de récurrence incluant toutes les valeurs de la série chronologique observée et par un premier terme déterminé par le prévisionniste (voir LES).

Dans leurs applications concrètes, ces relations peuvent s'écarter de la rigueur mathématique et supportent alors quelques aménagements (voir la page amortissement des obligations).

 

suites

 

© JY Baudot - Droits d'auteur protégés