Raisonnement par récurrence
Ce 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. La récurrence consiste à définir le terme d’une suite de nombres par celui qui le précède. Par exemple, 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. Bien sûr, il faut connaître au moins un terme de la suite pour pouvoir raccrocher la chaîne à quelque chose... Ce type de raisonnement est utilisé dans certaines techniques prévisionnelles et notamment les lissages exponentiels (LES, LED, lissage de Holt, lissage de Winters additif, lissage de Winters multiplicatif). En mathématiques, il est un moyen de définir les suites ou des dérivées successives. 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. Conjecture Une conjecture est une assertion non démontrée, mais sur laquelle on porte de sérieux soupçons. Dans l'étude des suites, le procédé est fréquent. Une représentation graphique ou une propriété algébrique nous laisse supposer quelque chose, par exemple une limite, mais nous n'avons pas d'autre preuve que notre certitude. On part alors de notre hypothèse puis on la démontre grâce à un raisonnement par récurrence. Raisonnement par récurrence L’axiome de récurrence stipule que si une propriété P est vraie en 0 et en 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 :
On pose P(n) : un+1 > un. Initialisation : on calcule le premier terme. u1 = 2. Donc, P(0) est vraie puisque u1 > u0. Hérédité : supposons que P(n) est vrai pour tout entier naturel.
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. Voir un autre exemple en page somme de premiers entiers. La récurrence forte (pour mémoire) 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. 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, ∀ n ∈ N, 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. Le raisonnement par récurrence s'applique également aux séries. Applications Le 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). D'une façon générale, les relations de récurrence sont souvent employées en entreprise et les tableurs trouvent là une application particulièrement adaptée puisqu'il suffit d'un cliquer-glisser sur la formule. Ces relations peuvent s'écarter de la rigueur mathématique et supportent alors quelques aménagements (voir page amortissement des obligations).
|
