Relation de récurrence

En mathématiques , une relation de récurrence est une équation selon laquelle le terme ième d'une suite de nombres est égal à une combinaison des termes précédents. Souvent, seuls les termes précédents de la suite apparaissent dans l'équation, pour un paramètre indépendant de ; ce nombre est appelé l' ordre de la relation. Si les valeurs des premiers nombres de la suite ont été données, le reste de la suite peut être calculé en appliquant l'équation de manière répétée. ${\displaystyle n <semantics> <mrow> <mstyle> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle n}</annotation> </semantics> </math><img src=$ ${\displaystyle k <semantics> <mrow> <mstyle> <mi>k</mi> </mstyle> </mrow> <annotation>{\displaystyle k}</annotation> </semantics> </math><img src=$ ${\displaystyle k <semantics> <mrow> <mstyle> <mi>k</mi> </mstyle> </mrow> <annotation>{\displaystyle k}</annotation> </semantics> </math><img src=$ ${\displaystyle n <semantics> <mrow> <mstyle> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle n}</annotation> </semantics> </math><img src=$ ${\displaystyle k <semantics> <mrow> <mstyle> <mi>k</mi> </mstyle> </mrow> <annotation>{\displaystyle k}</annotation> </semantics> </math><img src=$ ${\displaystyle k <semantics> <mrow> <mstyle> <mi>k</mi> </mstyle> </mrow> <annotation>{\displaystyle k}</annotation> </semantics> </math><img src=$

Dans les récurrences linéaires , le n -ième terme est assimilé à une fonction linéaire des termes précédents. Un exemple célèbre est la récurrence des nombres de Fibonacci , où l'ordre est deux et la fonction linéaire additionne simplement les deux termes précédents. Cet exemple est une récurrence linéaire à coefficients constants , car les coefficients de la fonction linéaire (1 et 1) sont des constantes qui ne dépendent pas de Pour ces récurrences, on peut exprimer le terme général de la suite comme une expression sous forme fermée de . De même, les récurrences linéaires avec des coefficients polynomiaux dépendant de sont également importantes, car de nombreuses fonctions élémentaires courantes et fonctions spéciales ont une série de Taylor dont les coefficients satisfont une telle relation de récurrence (voir fonction holonome ). ${\displaystyle k <semantics> <mrow> <mstyle> <mi>k</mi> </mstyle> </mrow> <annotation>{\displaystyle k}</annotation> </semantics> </math><img src=$ ${\displaystyle F_{n}=F_{n-1}+F_{n-2 <semantics> <mrow> <mstyle> <msub> <mi>F</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>F</mi> <mrow> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>F</mi> <mrow> <mi>n</mi> <mo>−</mo> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle F_{n}=F_{n-1}+F_{n-2}}</annotation> </semantics> </math><img src=$ ${\displaystyle k <semantics> <mrow> <mstyle> <mi>k</mi> </mstyle> </mrow> <annotation>{\displaystyle k}</annotation> </semantics> </math><img src=$ ${\displaystyle n. <semantics> <mrow> <mstyle> <mi>n</mi> <mo>.</mo> </mstyle> </mrow> <annotation>{\displaystyle n.}</annotation> </semantics> </math><img src=$ ${\displaystyle n <semantics> <mrow> <mstyle> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle n}</annotation> </semantics> </math><img src=$ ${\displaystyle n <semantics> <mrow> <mstyle> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle n}</annotation> </semantics> </math><img src=$

Résoudre une relation de récurrence revient à obtenir une solution sous forme fermée : une fonction non récursive de . ${\displaystyle n <semantics> <mrow> <mstyle> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle n}</annotation> </semantics> </math><img src=$

Le concept de relation de récurrence peut être étendu aux tableaux multidimensionnels , c'est-à-dire aux familles indexées par des tuples de nombres naturels .

Définition

Une relation de récurrence est une équation qui exprime chaque élément d'une séquence en fonction des éléments qui la précèdent. Plus précisément, dans le cas où seul l'élément immédiatement précédent est concerné, une relation de récurrence a la forme

0, {toi}_{n} = φ (n, {toi}_{n - 1}) pour n > 0,

0,}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b39e6366097c9c3c9fb8f9f1c4baaa3b927193b5">

où

{\displaystyle \varphi :\mathbb {N} imes X o X <semantics> <mrow> <mstyle> <mi>φ</mi> <mo>:</mo> <mrow> <mi>N</mi> </mrow> <mo>×</mo> <mi>X</mi> <mo>→</mo> <mi>X</mi> </mstyle> </mrow> <annotation>{\displaystyle \varphi :\mathbb {N} \fois X\à X}</annotation> </semantics> </math></span><img src=

est une fonction, où X est un ensemble auquel les éléments d'une séquence doivent appartenir. Pour tout , cela définit une séquence unique avec comme premier élément, appelé la valeur initiale . ${\displaystyle u_{0}\in X <semantics> <mrow> <mstyle> <msub> <mi>toi</mi> <mrow> <mn>0</mn> </mrow> </msub> <mo>∈</mo> <mi>X</mi> </mstyle> </mrow> <annotation>{\displaystyle u_{0}\dans X}</annotation> </semantics> </math><img src=$ ${\displaystyle u_{0 <semantics> <mrow> <mstyle> <msub> <mi>toi</mi> <mrow> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle u_{0}}</annotation> </semantics> </math><img src=$

Il est facile de modifier la définition pour obtenir des séquences commençant à partir du terme d'index 1 ou supérieur.

Ceci définit une relation de récurrence du premier ordre . Une relation de récurrence d' ordre k a la forme

{\displaystyle u_{n}=\varphi (n,u_{n-1},u_{n-2},\ldots ,u_{n-k})\quad { ext{for}}\quad n\geq k, <semantics> <mrow> <mstyle> <msub> <mi>toi</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>=</mo> <mi>φ</mi> <mo>(</mo> <mi>n</mi> <mo>,</mo> <msub> <mi>toi</mi> <mrow> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>toi</mi> <mrow> <mi>n</mi> <mo>−</mo> <mn>2</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>toi</mi> <mrow> <mi>n</mi> <mo>−</mo> <mi>k</mi> </mrow> </msub> <mo>)</mo> <mspace></mspace> <mrow> <mtext>pour</mtext> </mrow> <mspace></mspace> <mi>n</mi> <mo>≥</mo> <mi>k</mi> <mo>,</mo> </mstyle> </mrow> <annotation>{\displaystyle u_{n}=\varphi (n,u_{n-1},u_{n-2},\ldots ,u_{nk})\quad { exte{pour}}\quad n\geq k,}</annotation> </semantics> </math></span><img src=

où est une fonction qui implique k éléments consécutifs de la séquence. Dans ce cas, k valeurs initiales sont nécessaires pour définir une séquence. ${\displaystyle \varphi :\mathbb {N} imes X^{k} o X <semantics> <mrow> <mstyle> <mi>φ</mi> <mo>:</mo> <mrow> <mi>N</mi> </mrow> <mo>×</mo> <msup> <mi>X</mi> <mrow> <mi>k</mi> </mrow> </msup> <mo>→</mo> <mi>X</mi> </mstyle> </mrow> <annotation>{\displaystyle \varphi :\mathbb {N} \fois X^{k}\à X}</annotation> </semantics> </math><img src=$

Exemples

Factorielle

La factorielle est définie par la relation de récurrence

0, n! = n \cdot (n - 1)! pour n > 0,

0,}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bf40ba566fa3597f946022d9d63847e21bffacc7">

et la condition initiale

{\displaystyle 0!=1. <semantics> <mrow> <mstyle> <mn>0</mn> <mo>!</mo> <mo>=</mo> <mn>1.</mn> </mstyle> </mrow> <annotation>{\displaystyle 0!=1.}</annotation> </semantics> </math></span><img src=

Ceci est un exemple de récurrence linéaire à coefficients polynomiaux d'ordre 1, avec le polynôme simple (en n )

{\displaystyle n <semantics> <mrow> <mstyle> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle n}</annotation> </semantics> </math></span><img src=

comme seul coefficient.

Carte logistique

Un exemple de relation de récurrence est la carte logistique définie par

{\displaystyle x_{n+1}=rx_{n}(1-x_{n}), <semantics> <mrow> <mstyle> <msub> <mi>x</mi> <mrow> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mi>l</mi> <msub> <mi>x</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>(</mo> <mn>1</mn> <mo>−</mo> <msub> <mi>x</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>)</mo> <mo>,</mo> </mstyle> </mrow> <annotation>{\displaystyle x_{n+1}=rx_{n}(1-x_{n}),}</annotation> </semantics> </math></span><img src=

pour une constante donnée Le comportement de la séquence dépend considérablement mais reste stable lorsque la condition initiale varie. ${\displaystyle r. <semantics> <mrow> <mstyle> <mi>l</mi> <mo>.</mo> </mstyle> </mrow> <annotation>{\displaystyle r.}</annotation> </semantics> </math><img src=$ ${\displaystyle r, <semantics> <mrow> <mstyle> <mi>l</mi> <mo>,</mo> </mstyle> </mrow> <annotation>{\displaystyle r,}</annotation> </semantics> </math><img src=$ ${\displaystyle x_{0 <semantics> <mrow> <mstyle> <msub> <mi>x</mi> <mrow> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle x_{0}}</annotation> </semantics> </math><img src=$

Nombres de Fibonacci

La récurrence d'ordre deux satisfaite par les nombres de Fibonacci est l'exemple canonique d'une relation de récurrence linéaire homogène à coefficients constants (voir ci-dessous). La suite de Fibonacci est définie à l'aide de la récurrence

{\displaystyle F_{n}=F_{n-1}+F_{n-2 <semantics> <mrow> <mstyle> <msub> <mi>F</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>F</mi> <mrow> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>F</mi> <mrow> <mi>n</mi> <mo>−</mo> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle F_{n}=F_{n-1}+F_{n-2}}</annotation> </semantics> </math></span><img src=

avec des conditions initiales

{\displaystyle F_{0}=0 <semantics> <mrow> <mstyle> <msub> <mi>F</mi> <mrow> <mn>0</mn> </mrow> </msub> <mo>=</mo> <mn>0</mn> </mstyle> </mrow> <annotation>{\displaystyle F_{0}=0}</annotation> </semantics> </math></span><img src=

{\displaystyle F_{1}=1. <semantics> <mrow> <mstyle> <msub> <mi>F</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mn>1.</mn> </mstyle> </mrow> <annotation>{\displaystyle F_{1}=1.}</annotation> </semantics> </math></span><img src=

Explicitement, la récurrence donne les équations

{\displaystyle F_{2}=F_{1}+F_{0 <semantics> <mrow> <mstyle> <msub> <mi>F</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>=</mo> <msub> <mi>F</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>F</mi> <mrow> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle F_{2}=F_{1}+F_{0}}</annotation> </semantics> </math></span><img src=

{\displaystyle F_{3}=F_{2}+F_{1 <semantics> <mrow> <mstyle> <msub> <mi>F</mi> <mrow> <mn>3</mn> </mrow> </msub> <mo>=</mo> <msub> <mi>F</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>F</mi> <mrow> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle F_{3}=F_{2}+F_{1}}</annotation> </semantics> </math></span><img src=

{\displaystyle F_{4}=F_{3}+F_{2 <semantics> <mrow> <mstyle> <msub> <mi>F</mi> <mrow> <mn>4</mn> </mrow> </msub> <mo>=</mo> <msub> <mi>F</mi> <mrow> <mn>3</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>F</mi> <mrow> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle F_{4}=F_{3}+F_{2}}</annotation> </semantics> </math></span><img src=

etc.

Nous obtenons la suite des nombres de Fibonacci, qui commence

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

La récurrence peut être résolue par des méthodes décrites ci-dessous donnant la formule de Binet , qui implique les puissances des deux racines du polynôme caractéristique ; la fonction génératrice de la suite est la fonction rationnelle ${\displaystyle t^{2}=t+1 <semantics> <mrow> <mstyle> <msup> <mi>t</mi> <mrow> <mn>2</mn> </mrow> </msup> <mo>=</mo> <mi>t</mi> <mo>+</mo> <mn>1</mn> </mstyle> </mrow> <annotation>{\displaystyle t^{2}=t+1}</annotation> </semantics> </math><img src=$

{\displaystyle {\frac {t}{1-t-t^{2}}}. <semantics> <mrow> <mstyle> <mrow> <mfrac> <mi>t</mi> <mrow> <mn>1</mn> <mo>−</mo> <mi>t</mi> <mo>−</mo> <msup> <mi>t</mi> <mrow> <mn>2</mn> </mrow> </msup> </mrow> </mfrac> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation>{\displaystyle {\frac {t}{1-t-t^{2}}}.}</annotation> </semantics> </math></span><img src=

Coefficients binomiaux

Un exemple simple de relation de récurrence multidimensionnelle est donné par les coefficients binomiaux , qui comptent les façons de sélectionner des éléments dans un ensemble d' éléments. Ils peuvent être calculés par la relation de récurrence ${\displaystyle { binom {n}{k <semantics> <mrow> <mstyle> <mrow> <mstyle> <mrow> <mrow> <mo>(</mo> </mrow> <mfrac> <mi>n</mi> <mi>k</mi> </mfrac> <mrow> <mo>)</mo> </mrow> </mrow> </mstyle> </mrow> </mstyle> </mrow> <annotation>{\displaystyle { binom {n}{k}}}</annotation> </semantics> </math><img src=$ ${\displaystyle k <semantics> <mrow> <mstyle> <mi>k</mi> </mstyle> </mrow> <annotation>{\displaystyle k}</annotation> </semantics> </math><img src=$ ${\displaystyle n <semantics> <mrow> <mstyle> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle n}</annotation> </semantics> </math><img src=$

{\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}, <semantics> <mrow> <mstyle> <mrow> <mrow> <mrow> <mo>(</mo> </mrow> <mfrac> <mi>n</mi> <mi>k</mi> </mfrac> <mrow> <mo>)</mo> </mrow> </mrow> </mrow> <mo>=</mo> <mrow> <mrow> <mrow> <mo>(</mo> </mrow> <mfrac> <mrow> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> <mrow> <mi>k</mi> <mo>−</mo> <mn>1</mn> </mrow> </mfrac> <mrow> <mo>)</mo> </mrow> </mrow> </mrow> <mo>+</mo> <mrow> <mrow> <mrow> <mo>(</mo> </mrow> <mfrac> <mrow> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> <mi>k</mi> </mfrac> <mrow> <mo>)</mo> </mrow> </mrow> </mrow> <mo>,</mo> </mstyle> </mrow> <annotation>{\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},}</annotation> </semantics> </math></span><img src=

avec les cas de base . L'utilisation de cette formule pour calculer les valeurs de tous les coefficients binomiaux génère un tableau infini appelé triangle de Pascal . Les mêmes valeurs peuvent également être calculées directement par une formule différente qui n'est pas une récurrence, mais qui utilise des factorielles , des multiplications et des divisions, pas seulement des additions : ${\displaystyle { binom {n}{0}}={ binom {n}{n}}=1 <semantics> <mrow> <mstyle> <mrow> <mstyle> <mrow> <mrow> <mo>(</mo> </mrow> <mfrac> <mi>n</mi> <mn>0</mn> </mfrac> <mrow> <mo>)</mo> </mrow> </mrow> </mstyle> </mrow> <mo>=</mo> <mrow> <mstyle> <mrow> <mrow> <mo>(</mo> </mrow> <mfrac> <mi>n</mi> <mi>n</mi> </mfrac> <mrow> <mo>)</mo> </mrow> </mrow> </mstyle> </mrow> <mo>=</mo> <mn>1</mn> </mstyle> </mrow> <annotation>{\displaystyle { binom {n}{0}}={ binom {n}{n}}=1}</annotation> </semantics> </math><img src=$

{\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}. <semantics> <mrow> <mstyle> <mrow> <mrow> <mrow> <mo>(</mo> </mrow> <mfrac> <mi>n</mi> <mi>k</mi> </mfrac> <mrow> <mo>)</mo> </mrow> </mrow> </mrow> <mo>=</mo> <mrow> <mfrac> <mrow> <mi>n</mi> <mo>!</mo> </mrow> <mrow> <mi>k</mi> <mo>!</mo> <mo>(</mo> <mi>n</mi> <mo>−</mo> <mi>k</mi> <mo>)</mo> <mo>!</mo> </mrow> </mfrac> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation>{\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.}</annotation> </semantics> </math></span><img src=

Les coefficients binomiaux peuvent également être calculés avec une récurrence unidimensionnelle :

{\displaystyle {\binom {n}{k}}={\binom {n}{k-1}}(n-k+1)/k, <semantics> <mrow> <mstyle> <mrow> <mrow> <mrow> <mo>(</mo> </mrow> <mfrac> <mi>n</mi> <mi>k</mi> </mfrac> <mrow> <mo>)</mo> </mrow> </mrow> </mrow> <mo>=</mo> <mrow> <mrow> <mrow> <mo>(</mo> </mrow> <mfrac> <mi>n</mi> <mrow> <mi>k</mi> <mo>−</mo> <mn>1</mn> </mrow> </mfrac> <mrow> <mo>)</mo> </mrow> </mrow> </mrow> <mo>(</mo> <mi>n</mi> <mo>−</mo> <mi>k</mi> <mo>+</mo> <mn>1</mn> <mo>)</mo> <mrow> <mo>/</mo> </mrow> <mi>k</mi> <mo>,</mo> </mstyle> </mrow> <annotation>{\displaystyle {\binom {n}{k}}={\binom {n}{k-1}}(n-k+1)/k,}</annotation> </semantics> </math></span><img src=

avec la valeur initiale (la division n'est pas affichée comme une fraction pour souligner qu'elle doit être calculée après la multiplication, pour ne pas introduire de nombres fractionnaires). Cette récurrence est largement utilisée en informatique car elle ne nécessite pas de construire un tableau comme le fait la récurrence bidimensionnelle, et ne fait pas intervenir de très grands entiers comme le fait la formule avec factorielles (si on l'utilise tous les entiers impliqués sont plus petits que le résultat final). ${ extstyle {\binom {n}{0}}=1 <semantics> <mrow> <mstyle> <mrow> <mrow> <mrow> <mo>(</mo> </mrow> <mfrac> <mi>n</mi> <mn>0</mn> </mfrac> <mrow> <mo>)</mo> </mrow> </mrow> </mrow> <mo>=</mo> <mn>1</mn> </mstyle> </mrow> <annotation>{ extstyle {\binom {n}{0}}=1}</annotation> </semantics> </math><img src=$ ${ extstyle {\binom {n}{k}}={\binom {n}{n-k}}, <semantics> <mrow> <mstyle> <mrow> <mrow> <mrow> <mo>(</mo> </mrow> <mfrac> <mi>n</mi> <mi>k</mi> </mfrac> <mrow> <mo>)</mo> </mrow> </mrow> </mrow> <mo>=</mo> <mrow> <mrow> <mrow> <mo>(</mo> </mrow> <mfrac> <mi>n</mi> <mrow> <mi>n</mi> <mo>−</mo> <mi>k</mi> </mrow> </mfrac> <mrow> <mo>)</mo> </mrow> </mrow> </mrow> <mo>,</mo> </mstyle> </mrow> <annotation>{ extstyle {\binom {n}{k}}={\binom {n}{n-k}},}</annotation> </semantics> </math><img src=$

Opérateur de différence et équations de différence

LeL'opérateur de différence est unopérateurqui associedes séquencesà des séquences et, plus généralement,des fonctionsà des fonctions. Il est généralement notéet défini, ennotation fonctionnelle, comme ${\displaystyle \Delta , <semantics> <mrow> <mstyle> <mi>Δ</mi> <mo>,</mo> </mstyle> </mrow> <annotation>{\displaystyle \Delta ,}</annotation> </semantics> </math><img src=$

{\displaystyle (\Delta f)(x)=f(x+1)-f(x). <semantics> <mrow> <mstyle> <mo>(</mo> <mi>Δ</mi> <mi>f</mi> <mo>)</mo> <mo>(</mo> <mi>x</mi> <mo>)</mo> <mo>=</mo> <mi>f</mi> <mo>(</mo> <mi>x</mi> <mo>+</mo> <mn>1</mn> <mo>)</mo> <mo>−</mo> <mi>f</mi> <mo>(</mo> <mi>x</mi> <mo>)</mo> <mo>.</mo> </mstyle> </mrow> <annotation>{\displaystyle (\Delta f)(x)=f(x+1)-f(x).}</annotation> </semantics> </math></span><img src=

Il s’agit donc d’un cas particulier de différences finies .

Lors de l'utilisation de la notation d'index pour les séquences, la définition devient

{\displaystyle (\Delta a)_{n}=a_{n+1}-a_{n}. <semantics> <mrow> <mstyle> <mo>(</mo> <mi>Δ</mi> <mi>a</mi> <msub> <mo>)</mo> <mrow> <mi>n</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>a</mi> <mrow> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>−</mo> <msub> <mi>a</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>.</mo> </mstyle> </mrow> <annotation>{\displaystyle (\Delta a)_{n}=a_{n+1}-a_{n}.}</annotation> </semantics> </math></span><img src=

Les parenthèses autour de et sont généralement omises et doivent être comprises comme le terme d'indice n dans la séquence et non appliquées à l'élément ${\displaystyle \Delta f <semantics> <mrow> <mstyle> <mi>Δ</mi> <mi>f</mi> </mstyle> </mrow> <annotation>{\displaystyle \Delta f}</annotation> </semantics> </math><img src=$ ${\displaystyle \Delta a <semantics> <mrow> <mstyle> <mi>Δ</mi> <mi>a</mi> </mstyle> </mrow> <annotation>{\displaystyle \Delta a}</annotation> </semantics> </math><img src=$ ${\displaystyle \Delta a_{n <semantics> <mrow> <mstyle> <mi>Δ</mi> <msub> <mi>a</mi> <mrow> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle \Delta a_{n}}</annotation> </semantics> </math><img src=$ ${\displaystyle \Delta a, <semantics> <mrow> <mstyle> <mi>Δ</mi> <mi>a</mi> <mo>,</mo> </mstyle> </mrow> <annotation>{\displaystyle \Delta a,}</annotation> </semantics> </math><img src=$ ${\displaystyle \Delta <semantics> <mrow> <mstyle> <mi>Δ</mi> </mstyle> </mrow> <annotation>{\displaystyle \Delta }</annotation> </semantics> </math><img src=$ ${\displaystyle a_{n}. <semantics> <mrow> <mstyle> <msub> <mi>a</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>.</mo> </mstyle> </mrow> <annotation>{\displaystyle a_{n}.}</annotation> </semantics> </math><img src=$

Étant donné la séquence ${\displaystyle a=(a_{n})_{n\in \mathbb {N} }, <semantics> <mrow> <mstyle> <mi>a</mi> <mo>=</mo> <mo>(</mo> <msub> <mi>a</mi> <mrow> <mi>n</mi> </mrow> </msub> <msub> <mo>)</mo> <mrow> <mi>n</mi> <mo>∈</mo> <mrow> <mi>N</mi> </mrow> </mrow> </msub> <mo>,</mo> </mstyle> </mrow> <annotation>{\displaystyle a=(a_{n})_{n\in \mathbb {N} },}</annotation> </semantics> </math><img src=$ la première différence deaest ${\displaystyle \Delta a. <semantics> <mrow> <mstyle> <mi>Δ</mi> <mi>a</mi> <mo>.</mo> </mstyle> </mrow> <annotation>{\displaystyle \Delta a.}</annotation> </semantics> </math><img src=$

Lela deuxième différence est qu'un calcul simple montre que ${\displaystyle \Delta ^{2}a=(\Delta \circ \Delta )a=\Delta (\Delta a). <semantics> <mrow> <mstyle> <msup> <mi>Δ</mi> <mrow> <mn>2</mn> </mrow> </msup> <mi>a</mi> <mo>=</mo> <mo>(</mo> <mi>Δ</mi> <mo>∘</mo> <mi>Δ</mi> <mo>)</mo> <mi>a</mi> <mo>=</mo> <mi>Δ</mi> <mo>(</mo> <mi>Δ</mi> <mi>a</mi> <mo>)</mo> <mo>.</mo> </mstyle> </mrow> <annotation>{\displaystyle \Delta ^{2}a=(\Delta \circ \Delta )a=\Delta (\Delta a).}</annotation> </semantics> </math><img src=$

{\displaystyle \Delta ^{2}a_{n}=a_{n+2}-2a_{n+1}+a_{n}. <semantics> <mrow> <mstyle> <msup> <mi>Δ</mi> <mrow> <mn>2</mn> </mrow> </msup> <msub> <mi>a</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>a</mi> <mrow> <mi>n</mi> <mo>+</mo> <mn>2</mn> </mrow> </msub> <mo>−</mo> <mn>2</mn> <msub> <mi>a</mi> <mrow> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>a</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>.</mo> </mstyle> </mrow> <annotation>{\displaystyle \Delta ^{2}a_{n}=a_{n+2}-2a_{n+1}+a_{n}.}</annotation> </semantics> </math></span><img src=

Plus généralement : la k -ième différence est définie récursivement comme et on a ${\displaystyle \Delta ^{k}=\Delta \circ \Delta ^{k-1}, <semantics> <mrow> <mstyle> <msup> <mi>Δ</mi> <mrow> <mi>k</mi> </mrow> </msup> <mo>=</mo> <mi>Δ</mi> <mo>∘</mo> <msup> <mi>Δ</mi> <mrow> <mi>k</mi> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo>,</mo> </mstyle> </mrow> <annotation>{\displaystyle \Delta ^{k}=\Delta \circ \Delta ^{k-1},}</annotation> </semantics> </math><img src=$

{\displaystyle \Delta ^{k}a_{n}=\sum _{t=0}^{k}(-1)^{t}{\binom {k}{t}}a_{n+k-t}. <semantics> <mrow> <mstyle> <msup> <mi>Δ</mi> <mrow> <mi>k</mi> </mrow> </msup> <msub> <mi>a</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>=</mo> <munderover> <mo>∑</mo> <mrow> <mi>t</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mi>k</mi> </mrow> </munderover> <mo>(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo>)</mo> <mrow> <mi>t</mi> </mrow> </msup> <mrow> <mrow> <mrow> <mo>(</mo> </mrow> <mfrac> <mi>k</mi> <mi>t</mi> </mfrac> <mrow> <mo>)</mo> </mrow> </mrow> </mrow> <msub> <mi>a</mi> <mrow> <mi>n</mi> <mo>+</mo> <mi>k</mi> <mo>−</mo> <mi>t</mi> </mrow> </msub> <mo>.</mo> </mstyle> </mrow> <annotation>{\displaystyle \Delta ^{k}a_{n}=\sum _{t=0}^{k}(-1)^{t}{\binom {k}{t}}a_{n+k-t}.}</annotation> </semantics> </math></span><img src=

Cette relation peut être inversée, donnant

{\displaystyle a_{n+k}=a_{n}+{k \choose 1}\Delta a_{n}+\cdots +{k \choose k}\Delta ^{k}(a_{n}). <semantics> <mrow> <mstyle> <msub> <mi>a</mi> <mrow> <mi>n</mi> <mo>+</mo> <mi>k</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>a</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>+</mo> <mrow> <mrow> <mrow> <mo>(</mo> </mrow> <mfrac> <mi>k</mi> <mn>1</mn> </mfrac> <mrow> <mo>)</mo> </mrow> </mrow> </mrow> <mi>Δ</mi> <msub> <mi>a</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>+</mo> <mo>⋯</mo> <mo>+</mo> <mrow> <mrow> <mrow> <mo>(</mo> </mrow> <mfrac> <mi>k</mi> <mi>k</mi> </mfrac> <mrow> <mo>)</mo> </mrow> </mrow> </mrow> <msup> <mi>Δ</mi> <mrow> <mi>k</mi> </mrow> </msup> <mo>(</mo> <msub> <mi>a</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>)</mo> <mo>.</mo> </mstyle> </mrow> <annotation>{\displaystyle a_{n+k}=a_{n}+{k \choose 1}\Delta a_{n}+\cdots +{k \choose k}\Delta ^{k}(a_{n}).}</annotation> </semantics> </math></span><img src=

UNUne équation aux différences d'ordrekest une équation qui met en jeu leskpremières différences d'une suite ou d'une fonction, de la même manière qu'uneéquation différentielled'ordrekmet en jeu leskpremièresdérivéesd'une fonction.

Les deux relations ci-dessus permettent de transformer une relation de récurrence d'ordre k en une équation aux différences d'ordre k , et inversement, une équation aux différences d'ordre k en relation de récurrence d'ordre k . Chaque transformation est l' inverse de l'autre, et les suites qui sont solution de l'équation aux différences sont exactement celles qui satisfont la relation de récurrence.

Par exemple, l'équation de différence

{\displaystyle 3\Delta ^{2}a_{n}+2\Delta a_{n}+7a_{n}=0 <semantics> <mrow> <mstyle> <mn>3</mn> <msup> <mi>Δ</mi> <mrow> <mn>2</mn> </mrow> </msup> <msub> <mi>a</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>+</mo> <mn>2</mn> <mi>Δ</mi> <msub> <mi>a</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>+</mo> <mn>7</mn> <msub> <mi>a</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>=</mo> <mn>0</mn> </mstyle> </mrow> <annotation>{\displaystyle 3\Delta ^{2}a_{n}+2\Delta a_{n}+7a_{n}=0}</annotation> </semantics> </math></span><img src=

est équivalent à la relation de récurrence

{\displaystyle 3a_{n+2}=4a_{n+1}-8a_{n}, <semantics> <mrow> <mstyle> <mn>3</mn> <msub> <mi>a</mi> <mrow> <mi>n</mi> <mo>+</mo> <mn>2</mn> </mrow> </msub> <mo>=</mo> <mn>4</mn> <msub> <mi>a</mi> <mrow> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>−</mo> <mn>8</mn> <msub> <mi>a</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>,</mo> </mstyle> </mrow> <annotation>{\displaystyle 3a_{n+2}=4a_{n+1}-8a_{n},}</annotation> </semantics> </math></span><img src=

dans le sens où les deux équations sont satisfaites par les mêmes suites.

Comme il est équivalent pour une suite de satisfaire une relation de récurrence ou d'être la solution d'une équation aux différences, les deux termes « relation de récurrence » et « équation aux différences » sont parfois utilisés de manière interchangeable. Voir Équation aux différences rationnelles et Équation aux différences matricielles pour des exemples d'utilisation de « équation aux différences » au lieu de « relation de récurrence »

Les équations aux différences ressemblent aux équations différentielles, et cette ressemblance est souvent utilisée pour imiter les méthodes de résolution d'équations différentiables à appliquer à la résolution d'équations aux différences, et donc aux relations de récurrence.

Les équations de sommation sont liées aux équations de différence comme les équations intégrales sont liées aux équations différentielles. Voir calcul d'échelle de temps pour une unification de la théorie des équations de différence avec celle des équations différentielles.

Des séquences aux grilles

Les relations de récurrence à variable unique ou unidimensionnelles concernent des suites (c'est-à-dire des fonctions définies sur des grilles à une dimension). Les relations de récurrence à plusieurs variables ou n-dimensionnelles concernent des grilles à . Les fonctions définies sur des grilles à . peuvent également être étudiées avec des équations aux différences partielles. ${\displaystyle n <semantics> <mrow> <mstyle> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle n}</annotation> </semantics> </math><img src=$ ${\displaystyle n <semantics> <mrow> <mstyle> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle n}</annotation> </semantics> </math><img src=$

Résoudre

Résolution des relations de récurrence linéaire à coefficients constants

Résolution des relations de récurrence non homogènes du premier ordre à coefficients variables

De plus, pour la relation générale de récurrence linéaire non homogène du premier ordre à coefficients variables :

{\displaystyle a_{n+1}=f_{n}a_{n}+g_{n},\qquad f_{n} eq 0, <semantics> <mrow> <mstyle> <msub> <mi>a</mi> <mrow> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>=</mo> <msub> <mi>f</mi> <mrow> <mi>n</mi> </mrow> </msub> <msub> <mi>a</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>+</mo> <msub> <mi>g</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>,</mo> <mspace></mspace> <msub> <mi>f</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>≠</mo> <mn>0</mn> <mo>,</mo> </mstyle> </mrow> <annotation>{\displaystyle a_{n+1}=f_{n}a_{n}+g_{n},\qquad f_{n} eq 0,}</annotation> </semantics> </math></span><img src=

il existe également une méthode intéressante pour le résoudre :

{\displaystyle a_{n+1}-f_{n}a_{n}=g_{n <semantics> <mrow> <mstyle> <msub> <mi>a</mi> <mrow> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>−</mo> <msub> <mi>f</mi> <mrow> <mi>n</mi> </mrow> </msub> <msub> <mi>a</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>g</mi> <mrow> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle a_{n+1}-f_{n}a_{n}=g_{n}}</annotation> </semantics> </math></span><img src=

{\displaystyle {\frac {a_{n+1}}{\prod _{k=0}^{n}f_{k}}}-{\frac {f_{n}a_{n}}{\prod _{k=0}^{n}f_{k}}}={\frac {g_{n}}{\prod _{k=0}^{n}f_{k <semantics> <mrow> <mstyle> <mrow> <mfrac> <msub> <mi>a</mi> <mrow> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mrow> <munderover> <mo>∏</mo> <mrow> <mi>k</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mi>n</mi> </mrow> </munderover> <msub> <mi>f</mi> <mrow> <mi>k</mi> </mrow> </msub> </mrow> </mfrac> </mrow> <mo>−</mo> <mrow> <mfrac> <mrow> <msub> <mi>f</mi> <mrow> <mi>n</mi> </mrow> </msub> <msub> <mi>a</mi> <mrow> <mi>n</mi> </mrow> </msub> </mrow> <mrow> <munderover> <mo>∏</mo> <mrow> <mi>k</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mi>n</mi> </mrow> </munderover> <msub> <mi>f</mi> <mrow> <mi>k</mi> </mrow> </msub> </mrow> </mfrac> </mrow> <mo>=</mo> <mrow> <mfrac> <msub> <mi>g</mi> <mrow> <mi>n</mi> </mrow> </msub> <mrow> <munderover> <mo>∏</mo> <mrow> <mi>k</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mi>n</mi> </mrow> </munderover> <msub> <mi>f</mi> <mrow> <mi>k</mi> </mrow> </msub> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {\frac {a_{n+1}}{\prod _{k=0}^{n}f_{k}}}-{\frac {f_{n}a_{n}}{\prod _{k=0}^{n}f_{k}}}={\frac {g_{n}}{\prod _{k=0}^{n}f_{k}}}}</annotation> </semantics> </math></span><img src=

{\displaystyle {\frac {a_{n+1}}{\prod _{k=0}^{n}f_{k}}}-{\frac {a_{n}}{\prod _{k=0}^{n-1}f_{k}}}={\frac {g_{n}}{\prod _{k=0}^{n}f_{k <semantics> <mrow> <mstyle> <mrow> <mfrac> <msub> <mi>a</mi> <mrow> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mrow> <munderover> <mo>∏</mo> <mrow> <mi>k</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mi>n</mi> </mrow> </munderover> <msub> <mi>f</mi> <mrow> <mi>k</mi> </mrow> </msub> </mrow> </mfrac> </mrow> <mo>−</mo> <mrow> <mfrac> <msub> <mi>a</mi> <mrow> <mi>n</mi> </mrow> </msub> <mrow> <munderover> <mo>∏</mo> <mrow> <mi>k</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <msub> <mi>f</mi> <mrow> <mi>k</mi> </mrow> </msub> </mrow> </mfrac> </mrow> <mo>=</mo> <mrow> <mfrac> <msub> <mi>g</mi> <mrow> <mi>n</mi> </mrow> </msub> <mrow> <munderover> <mo>∏</mo> <mrow> <mi>k</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mi>n</mi> </mrow> </munderover> <msub> <mi>f</mi> <mrow> <mi>k</mi> </mrow> </msub> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {\frac {a_{n+1}}{\prod _{k=0}^{n}f_{k}}}-{\frac {a_{n}}{\prod _{k=0}^{n-1}f_{k}}}={\frac {g_{n}}{\prod _{k=0}^{n}f_{k}}}}</annotation> </semantics> </math></span><img src=

Laisser

{\displaystyle A_{n}={\frac {a_{n}}{\prod _{k=0}^{n-1}f_{k}}}, <semantics> <mrow> <mstyle> <msub> <mi>A</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>=</mo> <mrow> <mfrac> <msub> <mi>a</mi> <mrow> <mi>n</mi> </mrow> </msub> <mrow> <munderover> <mo>∏</mo> <mrow> <mi>k</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <msub> <mi>f</mi> <mrow> <mi>k</mi> </mrow> </msub> </mrow> </mfrac> </mrow> <mo>,</mo> </mstyle> </mrow> <annotation>{\displaystyle A_{n}={\frac {a_{n}}{\prod _{k=0}^{n-1}f_{k}}},}</annotation> </semantics> </math></span><img src=

Alors

{\displaystyle A_{n+1}-A_{n}={\frac {g_{n}}{\prod _{k=0}^{n}f_{k <semantics> <mrow> <mstyle> <msub> <mi>A</mi> <mrow> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>−</mo> <msub> <mi>A</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>=</mo> <mrow> <mfrac> <msub> <mi>g</mi> <mrow> <mi>n</mi> </mrow> </msub> <mrow> <munderover> <mo>∏</mo> <mrow> <mi>k</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mi>n</mi> </mrow> </munderover> <msub> <mi>f</mi> <mrow> <mi>k</mi> </mrow> </msub> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle A_{n+1}-A_{n}={\frac {g_{n}}{\prod _{k=0}^{n}f_{k}}}}</annotation> </semantics> </math></span><img src=

{\displaystyle \sum _{m=0}^{n-1}(A_{m+1}-A_{m})=A_{n}-A_{0}=\sum _{m=0}^{n-1}{\frac {g_{m}}{\prod _{k=0}^{m}f_{k <semantics> <mrow> <mstyle> <munderover> <mo>∑</mo> <mrow> <mi>m</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <mo>(</mo> <msub> <mi>A</mi> <mrow> <mi>m</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>−</mo> <msub> <mi>A</mi> <mrow> <mi>m</mi> </mrow> </msub> <mo>)</mo> <mo>=</mo> <msub> <mi>A</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>−</mo> <msub> <mi>A</mi> <mrow> <mn>0</mn> </mrow> </msub> <mo>=</mo> <munderover> <mo>∑</mo> <mrow> <mi>m</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <mrow> <mfrac> <msub> <mi>g</mi> <mrow> <mi>m</mi> </mrow> </msub> <mrow> <munderover> <mo>∏</mo> <mrow> <mi>k</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mi>m</mi> </mrow> </munderover> <msub> <mi>f</mi> <mrow> <mi>k</mi> </mrow> </msub> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle \sum _{m=0}^{n-1}(A_{m+1}-A_{m})=A_{n}-A_{0}=\sum _{m=0}^{n-1}{\frac {g_{m}}{\prod _{k=0}^{m}f_{k}}}}</annotation> </semantics> </math></span><img src=

{\displaystyle {\frac {a_{n}}{\prod _{k=0}^{n-1}f_{k}}}=A_{0}+\sum _{m=0}^{n-1}{\frac {g_{m}}{\prod _{k=0}^{m}f_{k <semantics> <mrow> <mstyle> <mrow> <mfrac> <msub> <mi>a</mi> <mrow> <mi>n</mi> </mrow> </msub> <mrow> <munderover> <mo>∏</mo> <mrow> <mi>k</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <msub> <mi>f</mi> <mrow> <mi>k</mi> </mrow> </msub> </mrow> </mfrac> </mrow> <mo>=</mo> <msub> <mi>A</mi> <mrow> <mn>0</mn> </mrow> </msub> <mo>+</mo> <munderover> <mo>∑</mo> <mrow> <mi>m</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <mrow> <mfrac> <msub> <mi>g</mi> <mrow> <mi>m</mi> </mrow> </msub> <mrow> <munderover> <mo>∏</mo> <mrow> <mi>k</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mi>m</mi> </mrow> </munderover> <msub> <mi>f</mi> <mrow> <mi>k</mi> </mrow> </msub> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {\frac {a_{n}}{\prod _{k=0}^{n-1}f_{k}}}=A_{0}+\sum _{m=0}^{n-1}{\frac {g_{m}}{\prod _{k=0}^{m}f_{k}}}}</annotation> </semantics> </math></span><img src=

{\displaystyle a_{n}=\left(\prod _{k=0}^{n-1}f_{k} ight)\left(A_{0}+\sum _{m=0}^{n-1}{\frac {g_{m}}{\prod _{k=0}^{m}f_{k}}} ight) <semantics> <mrow> <mstyle> <msub> <mi>a</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>=</mo> <mrow> <mo>(</mo> <mrow> <munderover> <mo>∏</mo> <mrow> <mi>k</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <msub> <mi>f</mi> <mrow> <mi>k</mi> </mrow> </msub> </mrow> <mo>)</mo> </mrow> <mrow> <mo>(</mo> <mrow> <msub> <mi>A</mi> <mrow> <mn>0</mn> </mrow> </msub> <mo>+</mo> <munderover> <mo>∑</mo> <mrow> <mi>m</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <mrow> <mfrac> <msub> <mi>g</mi> <mrow> <mi>m</mi> </mrow> </msub> <mrow> <munderover> <mo>∏</mo> <mrow> <mi>k</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mi>m</mi> </mrow> </munderover> <msub> <mi>f</mi> <mrow> <mi>k</mi> </mrow> </msub> </mrow> </mfrac> </mrow> </mrow> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation>{\displaystyle a_{n}=\left(\prod _{k=0}^{n-1}f_{k} ight)\left(A_{0}+\sum _{m=0}^{n-1}{\frac {g_{m}}{\prod _{k=0}^{m}f_{k}}} ight)}</annotation> </semantics> </math></span><img src=

Si nous appliquons la formule à et prenons la limite , nous obtenons la formule des équations différentielles linéaires du premier ordre à coefficients variables ; la somme devient une intégrale et le produit devient la fonction exponentielle d'une intégrale. ${\displaystyle a_{n+1}=(1+hf_{nh})a_{n}+hg_{nh <semantics> <mrow> <mstyle> <msub> <mi>a</mi> <mrow> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mo>(</mo> <mn>1</mn> <mo>+</mo> <mi>h</mi> <msub> <mi>f</mi> <mrow> <mi>n</mi> <mi>h</mi> </mrow> </msub> <mo>)</mo> <msub> <mi>a</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>+</mo> <mi>h</mi> <msub> <mi>g</mi> <mrow> <mi>n</mi> <mi>h</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle a_{n+1}=(1+hf_{nh})a_{n}+hg_{nh}}</annotation> </semantics> </math><img src=$ ${\displaystyle h o 0 <semantics> <mrow> <mstyle> <mi>h</mi> <mo>→</mo> <mn>0</mn> </mstyle> </mrow> <annotation>{\displaystyle h o 0}</annotation> </semantics> </math><img src=$

Résolution des relations générales de récurrence linéaire homogène

De nombreuses relations de récurrence linéaire homogènes peuvent être résolues au moyen de la série hypergéométrique généralisée . Des cas particuliers de ces relations conduisent à des relations de récurrence pour les polynômes orthogonaux et de nombreuses fonctions spéciales . Par exemple, la solution de

{\displaystyle J_{n+1}={\frac {2n}{z}}J_{n}-J_{n-1 <semantics> <mrow> <mstyle> <msub> <mi>J</mi> <mrow> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mrow> <mfrac> <mrow> <mn>2</mn> <mi>n</mi> </mrow> <mi>z</mi> </mfrac> </mrow> <msub> <mi>J</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>−</mo> <msub> <mi>J</mi> <mrow> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle J_{n+1}={\frac {2n}{z}}J_{n}-J_{n-1}}</annotation> </semantics> </math></span><img src=

est donné par

{\displaystyle J_{n}=J_{n}(z), <semantics> <mrow> <mstyle> <msub> <mi>J</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>J</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>(</mo> <mi>z</mi> <mo>)</mo> <mo>,</mo> </mstyle> </mrow> <annotation>{\displaystyle J_{n}=J_{n}(z),}</annotation> </semantics> </math></span><img src=

la fonction de Bessel , tandis que

{\displaystyle (b-n)M_{n-1}+(2n-b+z)M_{n}-nM_{n+1}=0 <semantics> <mrow> <mstyle> <mo>(</mo> <mi>b</mi> <mo>−</mo> <mi>n</mi> <mo>)</mo> <msub> <mi>M</mi> <mrow> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>+</mo> <mo>(</mo> <mn>2</mn> <mi>n</mi> <mo>−</mo> <mi>b</mi> <mo>+</mo> <mi>z</mi> <mo>)</mo> <msub> <mi>M</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>−</mo> <mi>n</mi> <msub> <mi>M</mi> <mrow> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mn>0</mn> </mstyle> </mrow> <annotation>{\displaystyle (b-n)M_{n-1}+(2n-b+z)M_{n}-nM_{n+1}=0}</annotation> </semantics> </math></span><img src=

est résolu par

{\displaystyle M_{n}=M(n,b;z) <semantics> <mrow> <mstyle> <msub> <mi>M</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>=</mo> <mi>M</mi> <mo>(</mo> <mi>n</mi> <mo>,</mo> <mi>b</mi> <mo>;</mo> <mi>z</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle M_{n}=M(n,b;z)}</annotation> </semantics> </math></span><img src=

les séries hypergéométriques confluentes . Les suites qui sont les solutions d' équations aux différences linéaires à coefficients polynomiaux sont dites p-récursives . Pour ces équations de récurrence spécifiques, on connaît des algorithmes qui trouvent des solutions polynomiales , rationnelles ou hypergéométriques .

Résolution d'équations aux différences rationnelles du premier ordre

Une équation aux différences rationnelles du premier ordre a la forme . Une telle équation peut être résolue en l'écrivant comme une transformation non linéaire d'une autre variable qui évolue elle-même linéairement. Ensuite, des méthodes standard peuvent être utilisées pour résoudre l'équation aux différences linéaires dans . ${\displaystyle w_{t+1}={ frac {aw_{t}+b}{cw_{t}+d <semantics> <mrow> <mstyle> <msub> <mi>w</mi> <mrow> <mi>t</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mrow> <mstyle> <mfrac> <mrow> <mi>a</mi> <msub> <mi>w</mi> <mrow> <mi>t</mi> </mrow> </msub> <mo>+</mo> <mi>b</mi> </mrow> <mrow> <mi>c</mi> <msub> <mi>w</mi> <mrow> <mi>t</mi> </mrow> </msub> <mo>+</mo> <mi>d</mi> </mrow> </mfrac> </mstyle> </mrow> </mstyle> </mrow> <annotation>{\displaystyle w_{t+1}={ frac {aw_{t}+b}{cw_{t}+d}}}</annotation> </semantics> </math><img src=$ ${\displaystyle w_{t <semantics> <mrow> <mstyle> <msub> <mi>w</mi> <mrow> <mi>t</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle w_{t}}</annotation> </semantics> </math><img src=$ ${\displaystyle x_{t <semantics> <mrow> <mstyle> <msub> <mi>x</mi> <mrow> <mi>t</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle x_{t}}</annotation> </semantics> </math><img src=$ ${\displaystyle x_{t <semantics> <mrow> <mstyle> <msub> <mi>x</mi> <mrow> <mi>t</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle x_{t}}</annotation> </semantics> </math><img src=$

Stabilité

Stabilité des récurrences linéaires d'ordre supérieur

La récurrence linéaire de l'ordre , ${\displaystyle d <semantics> <mrow> <mstyle> <mi>d</mi> </mstyle> </mrow> <annotation>{\displaystyle d}</annotation> </semantics> </math><img src=$

{\displaystyle a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{d}a_{n-d}, <semantics> <mrow> <mstyle> <msub> <mi>a</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>c</mi> <mrow> <mn>1</mn> </mrow> </msub> <msub> <mi>a</mi> <mrow> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>c</mi> <mrow> <mn>2</mn> </mrow> </msub> <msub> <mi>a</mi> <mrow> <mi>n</mi> <mo>−</mo> <mn>2</mn> </mrow> </msub> <mo>+</mo> <mo>⋯</mo> <mo>+</mo> <msub> <mi>c</mi> <mrow> <mi>d</mi> </mrow> </msub> <msub> <mi>a</mi> <mrow> <mi>n</mi> <mo>−</mo> <mi>d</mi> </mrow> </msub> <mo>,</mo> </mstyle> </mrow> <annotation>{\displaystyle a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{d}a_{n-d},}</annotation> </semantics> </math></span><img src=

a l' équation caractéristique

{\displaystyle \lambda ^{d}-c_{1}\lambda ^{d-1}-c_{2}\lambda ^{d-2}-\cdots -c_{d}\lambda ^{0}=0. <semantics> <mrow> <mstyle> <msup> <mi>λ</mi> <mrow> <mi>d</mi> </mrow> </msup> <mo>−</mo> <msub> <mi>c</mi> <mrow> <mn>1</mn> </mrow> </msub> <msup> <mi>λ</mi> <mrow> <mi>d</mi> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo>−</mo> <msub> <mi>c</mi> <mrow> <mn>2</mn> </mrow> </msub> <msup> <mi>λ</mi> <mrow> <mi>d</mi> <mo>−</mo> <mn>2</mn> </mrow> </msup> <mo>−</mo> <mo>⋯</mo> <mo>−</mo> <msub> <mi>c</mi> <mrow> <mi>d</mi> </mrow> </msub> <msup> <mi>λ</mi> <mrow> <mn>0</mn> </mrow> </msup> <mo>=</mo> <mn>0.</mn> </mstyle> </mrow> <annotation>{\displaystyle \lambda ^{d}-c_{1}\lambda ^{d-1}-c_{2}\lambda ^{d-2}-\cdots -c_{d}\lambda ^{0}=0.}</annotation> </semantics> </math></span><img src=

La récurrence est stable , ce qui signifie que les itérés convergent asymptotiquement vers une valeur fixe, si et seulement si les valeurs propres (c'est-à-dire les racines de l'équation caractéristique), qu'elles soient réelles ou complexes, sont toutes inférieures à l'unité en valeur absolue.

Stabilité des récurrences matricielles linéaires du premier ordre

Dans l'équation de différence de matrice du premier ordre

{\displaystyle [x_{t}-x^{*}]=A[x_{t-1}-x^{*}] <semantics> <mrow> <mstyle> <mo>[</mo> <msub> <mi>x</mi> <mrow> <mi>t</mi> </mrow> </msub> <mo>−</mo> <msup> <mi>x</mi> <mrow> <mo>∗</mo> </mrow> </msup> <mo>]</mo> <mo>=</mo> <mi>A</mi> <mo>[</mo> <msub> <mi>x</mi> <mrow> <mi>t</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>−</mo> <msup> <mi>x</mi> <mrow> <mo>∗</mo> </mrow> </msup> <mo>]</mo> </mstyle> </mrow> <annotation>{\displaystyle [x_{t}-x^{*}]=A[x_{t-1}-x^{*}]}</annotation> </semantics> </math></span><img src=

avec vecteur d'état et matrice de transition , converge asymptotiquement vers le vecteur d'état stationnaire si et seulement si toutes les valeurs propres de la matrice de transition (qu'elles soient réelles ou complexes) ont une valeur absolue inférieure à 1. ${\displaystyle x <semantics> <mrow> <mstyle> <mi>x</mi> </mstyle> </mrow> <annotation>{\displaystyle x}</annotation> </semantics> </math><img src=$ ${\displaystyle A <semantics> <mrow> <mstyle> <mi>A</mi> </mstyle> </mrow> <annotation>{\displaystyle A}</annotation> </semantics> </math><img src=$ ${\displaystyle x <semantics> <mrow> <mstyle> <mi>x</mi> </mstyle> </mrow> <annotation>{\displaystyle x}</annotation> </semantics> </math><img src=$ ${\displaystyle x^{* <semantics> <mrow> <mstyle> <msup> <mi>x</mi> <mrow> <mo>∗</mo> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle x^{*}}</annotation> </semantics> </math><img src=$ ${\displaystyle A <semantics> <mrow> <mstyle> <mi>A</mi> </mstyle> </mrow> <annotation>{\displaystyle A}</annotation> </semantics> </math><img src=$

Stabilité des récurrences non linéaires du premier ordre

Considérons la récurrence non linéaire du premier ordre

{\displaystyle x_{n}=f(x_{n-1}). <semantics> <mrow> <mstyle> <msub> <mi>x</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>=</mo> <mi>f</mi> <mo>(</mo> <msub> <mi>x</mi> <mrow> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>)</mo> <mo>.</mo> </mstyle> </mrow> <annotation>{\displaystyle x_{n}=f(x_{n-1}).}</annotation> </semantics> </math></span><img src=

Cette récurrence est localement stable , ce qui signifie qu'elle converge vers un point fixe à partir de points suffisamment proches de , si la pente de au voisinage de est inférieure à l'unité en valeur absolue : c'est-à-dire, ${\displaystyle x^{* <semantics> <mrow> <mstyle> <msup> <mi>x</mi> <mrow> <mo>∗</mo> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle x^{*}}</annotation> </semantics> </math><img src=$ ${\displaystyle x^{* <semantics> <mrow> <mstyle> <msup> <mi>x</mi> <mrow> <mo>∗</mo> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle x^{*}}</annotation> </semantics> </math><img src=$ ${\displaystyle f <semantics> <mrow> <mstyle> <mi>f</mi> </mstyle> </mrow> <annotation>{\displaystyle f}</annotation> </semantics> </math><img src=$ ${\displaystyle x^{* <semantics> <mrow> <mstyle> <msup> <mi>x</mi> <mrow> <mo>∗</mo> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle x^{*}}</annotation> </semantics> </math><img src=$

{\displaystyle |f'(x^{*})|<1. <semantics> <mrow> <mstyle> <mrow> <mo>|</mo> </mrow> <msup> <mi>f</mi> <mo>′</mo> </msup> <mo>(</mo> <msup> <mi>x</mi> <mrow> <mo>∗</mo> </mrow> </msup> <mo>)</mo> <mrow> <mo>|</mo> </mrow> <mo><</mo> <mn>1.</mn> </mstyle> </mrow> <annotation>{\displaystyle |f'(x^{*})|<1.}</annotation> </semantics> </math></span><img src=

Une récurrence non linéaire peut avoir plusieurs points fixes, auquel cas certains points fixes peuvent être localement stables et d'autres localement instables ; pour une valeur f continue, deux points fixes adjacents ne peuvent pas être tous deux localement stables.

Une relation de récurrence non linéaire pourrait également avoir un cycle de période pour . Un tel cycle est stable, ce qui signifie qu'il attire un ensemble de conditions initiales de mesure positive, si la fonction composite ${\displaystyle k <semantics> <mrow> <mstyle> <mi>k</mi> </mstyle> </mrow> <annotation>{\displaystyle k}</annotation> </semantics> </math><img src=$ $1 k > 1$ 1}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5cda43bd4034dc2d04cd562005d0af81d3d2dbc6">

{\displaystyle g(x):=f\circ f\circ \cdots \circ f(x) <semantics> <mrow> <mstyle> <mi>g</mi> <mo>(</mo> <mi>x</mi> <mo>)</mo> <mo>:=</mo> <mi>f</mi> <mo>∘</mo> <mi>f</mi> <mo>∘</mo> <mo>⋯</mo> <mo>∘</mo> <mi>f</mi> <mo>(</mo> <mi>x</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle g(x):=f\circ f\circ \cdots \circ f(x)}</annotation> </semantics> </math></span><img src=

avec les temps d'apparition est localement stable selon le même critère : ${\displaystyle f <semantics> <mrow> <mstyle> <mi>f</mi> </mstyle> </mrow> <annotation>{\displaystyle f}</annotation> </semantics> </math><img src=$ ${\displaystyle k <semantics> <mrow> <mstyle> <mi>k</mi> </mstyle> </mrow> <annotation>{\displaystyle k}</annotation> </semantics> </math><img src=$

{\displaystyle |g'(x^{*})|<1, <semantics> <mrow> <mstyle> <mrow> <mo>|</mo> </mrow> <msup> <mi>g</mi> <mo>′</mo> </msup> <mo>(</mo> <msup> <mi>x</mi> <mrow> <mo>∗</mo> </mrow> </msup> <mo>)</mo> <mrow> <mo>|</mo> </mrow> <mo><</mo> <mn>1</mn> <mo>,</mo> </mstyle> </mrow> <annotation>{\displaystyle |g'(x^{*})|<1,}</annotation> </semantics> </math></span><img src=

où se trouve un point quelconque du cycle. ${\displaystyle x^{* <semantics> <mrow> <mstyle> <msup> <mi>x</mi> <mrow> <mo>∗</mo> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle x^{*}}</annotation> </semantics> </math><img src=$

Dans une relation de récurrence chaotique , la variable reste dans une région délimitée mais ne converge jamais vers un point fixe ou un cycle attractif ; tous les points fixes ou cycles de l'équation sont instables. Voir également carte logistique , transformation dyadique et carte de tente . ${\displaystyle x <semantics> <mrow> <mstyle> <mi>x</mi> </mstyle> </mrow> <annotation>{\displaystyle x}</annotation> </semantics> </math><img src=$

Relation avec les équations différentielles

Lors de la résolution numérique d'une équation différentielle ordinaire , on rencontre généralement une relation de récurrence. Par exemple, lors de la résolution du problème de la valeur initiale

{\displaystyle y'(t)=f(t,y(t)),\ \ y(t_{0})=y_{0}, <semantics> <mrow> <mstyle> <msup> <mi>y</mi> <mo>′</mo> </msup> <mo>(</mo> <mi>t</mi> <mo>)</mo> <mo>=</mo> <mi>f</mi> <mo>(</mo> <mi>t</mi> <mo>,</mo> <mi>y</mi> <mo>(</mo> <mi>t</mi> <mo>)</mo> <mo>)</mo> <mo>,</mo> <mtext> </mtext> <mtext> </mtext> <mi>y</mi> <mo>(</mo> <msub> <mi>t</mi> <mrow> <mn>0</mn> </mrow> </msub> <mo>)</mo> <mo>=</mo> <msub> <mi>y</mi> <mrow> <mn>0</mn> </mrow> </msub> <mo>,</mo> </mstyle> </mrow> <annotation>{\displaystyle y'(t)=f(t,y(t)),\ \ y(t_{0})=y_{0},}</annotation> </semantics> </math></span><img src=

avec la méthode d'Euler et un pas de , on calcule les valeurs ${\displaystyle h <semantics> <mrow> <mstyle> <mi>h</mi> </mstyle> </mrow> <annotation>{\displaystyle h}</annotation> </semantics> </math><img src=$

{\displaystyle y_{0}=y(t_{0}),\ \ y_{1}=y(t_{0}+h),\ \ y_{2}=y(t_{0}+2h),\ \dots <semantics> <mrow> <mstyle> <msub> <mi>y</mi> <mrow> <mn>0</mn> </mrow> </msub> <mo>=</mo> <mi>y</mi> <mo>(</mo> <msub> <mi>t</mi> <mrow> <mn>0</mn> </mrow> </msub> <mo>)</mo> <mo>,</mo> <mtext> </mtext> <mtext> </mtext> <msub> <mi>y</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mi>y</mi> <mo>(</mo> <msub> <mi>t</mi> <mrow> <mn>0</mn> </mrow> </msub> <mo>+</mo> <mi>h</mi> <mo>)</mo> <mo>,</mo> <mtext> </mtext> <mtext> </mtext> <msub> <mi>y</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>=</mo> <mi>y</mi> <mo>(</mo> <msub> <mi>t</mi> <mrow> <mn>0</mn> </mrow> </msub> <mo>+</mo> <mn>2</mn> <mi>h</mi> <mo>)</mo> <mo>,</mo> <mtext> </mtext> <mo>…</mo> </mstyle> </mrow> <annotation>{\displaystyle y_{0}=y(t_{0}),\ \ y_{1}=y(t_{0}+h),\ \ y_{2}=y(t_{0}+2h),\ \dots }</annotation> </semantics> </math></span><img src=

par la récurrence

{\displaystyle \,y_{n+1}=y_{n}+hf(t_{n},y_{n}),t_{n}=t_{0}+nh <semantics> <mrow> <mstyle> <mspace></mspace> <msub> <mi>y</mi> <mrow> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>=</mo> <msub> <mi>y</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>+</mo> <mi>h</mi> <mi>f</mi> <mo>(</mo> <msub> <mi>t</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>,</mo> <msub> <mi>y</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>)</mo> <mo>,</mo> <msub> <mi>t</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>t</mi> <mrow> <mn>0</mn> </mrow> </msub> <mo>+</mo> <mi>n</mi> <mi>h</mi> </mstyle> </mrow> <annotation>{\displaystyle \,y_{n+1}=y_{n}+hf(t_{n},y_{n}),t_{n}=t_{0}+nh}</annotation> </semantics> </math></span><img src=

Les systèmes d'équations différentielles linéaires du premier ordre peuvent être discrétisés de manière exactement analytique en utilisant les méthodes présentées dans l' article sur la discrétisation .

Applications

Biologie mathématique

Certaines des équations différentielles les plus connues trouvent leur origine dans la tentative de modéliser la dynamique des populations . Par exemple, les nombres de Fibonacci ont été utilisés autrefois comme modèle pour la croissance d'une population de lapins.

La carte logistique est utilisée soit directement pour modéliser la croissance de la population, soit comme point de départ pour des modèles plus détaillés de la dynamique de population. Dans ce contexte, les équations aux différences couplées sont souvent utilisées pour modéliser l'interaction de deux ou plusieurs populations . Par exemple, le modèle Nicholson-Bailey pour une interaction hôte - parasite est donné par

{\displaystyle N_{t+1}=\lambda N_{t}e^{-aP_{t <semantics> <mrow> <mstyle> <msub> <mi>N</mi> <mrow> <mi>t</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mi>λ</mi> <msub> <mi>N</mi> <mrow> <mi>t</mi> </mrow> </msub> <msup> <mi>e</mi> <mrow> <mo>−</mo> <mi>a</mi> <msub> <mi>P</mi> <mrow> <mi>t</mi> </mrow> </msub> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle N_{t+1}=\lambda N_{t}e^{-aP_{t}}}</annotation> </semantics> </math></span><img src=

{\displaystyle P_{t+1}=N_{t}(1-e^{-aP_{t}}), <semantics> <mrow> <mstyle> <msub> <mi>P</mi> <mrow> <mi>t</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>=</mo> <msub> <mi>N</mi> <mrow> <mi>t</mi> </mrow> </msub> <mo>(</mo> <mn>1</mn> <mo>−</mo> <msup> <mi>e</mi> <mrow> <mo>−</mo> <mi>a</mi> <msub> <mi>P</mi> <mrow> <mi>t</mi> </mrow> </msub> </mrow> </msup> <mo>)</mo> <mo>,</mo> </mstyle> </mrow> <annotation>{\displaystyle P_{t+1}=N_{t}(1-e^{-aP_{t}}),}</annotation> </semantics> </math></span><img src=

avec représentant les hôtes et les parasites, à l'instant . ${\displaystyle N_{t <semantics> <mrow> <mstyle> <msub> <mi>N</mi> <mrow> <mi>t</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle N_{t}}</annotation> </semantics> </math><img src=$ ${\displaystyle P_{t <semantics> <mrow> <mstyle> <msub> <mi>P</mi> <mrow> <mi>t</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle P_{t}}</annotation> </semantics> </math><img src=$ ${\displaystyle t <semantics> <mrow> <mstyle> <mi>t</mi> </mstyle> </mrow> <annotation>{\displaystyle t}</annotation> </semantics> </math><img src=$

Les équations d'intégrodifférence sont une forme de relation de récurrence importante pour l'écologie spatiale . Ces équations et d'autres équations de différence sont particulièrement adaptées à la modélisation de populations univoltines .

L'informatique

Les relations de récurrence sont également d'une importance fondamentale dans l'analyse des algorithmes . Si un algorithme est conçu de manière à diviser un problème en sous-problèmes plus petits ( diviser pour mieux régner ), son temps d'exécution est décrit par une relation de récurrence.

Un exemple simple est le temps qu'il faut à un algorithme pour trouver un élément dans un vecteur ordonné contenant des éléments, dans le pire des cas. ${\displaystyle n <semantics> <mrow> <mstyle> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle n}</annotation> </semantics> </math><img src=$

Un algorithme naïf recherchera de gauche à droite, un élément à la fois. Le pire scénario possible est lorsque l'élément requis est le dernier, le nombre de comparaisons étant alors de . ${\displaystyle n <semantics> <mrow> <mstyle> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle n}</annotation> </semantics> </math><img src=$

Un meilleur algorithme est appelé recherche binaire . Cependant, il nécessite un vecteur trié. Il vérifie d'abord si l'élément est au milieu du vecteur. Si ce n'est pas le cas, il vérifie si l'élément du milieu est supérieur ou inférieur à l'élément recherché. À ce stade, la moitié du vecteur peut être supprimée et l'algorithme peut être exécuté à nouveau sur l'autre moitié. Le nombre de comparaisons sera donné par

{\displaystyle c_{1}=1 <semantics> <mrow> <mstyle> <msub> <mi>c</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mn>1</mn> </mstyle> </mrow> <annotation>{\displaystyle c_{1}=1}</annotation> </semantics> </math></span><img src=

{\displaystyle c_{n}=1+c_{n/2 <semantics> <mrow> <mstyle> <msub> <mi>c</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>=</mo> <mn>1</mn> <mo>+</mo> <msub> <mi>c</mi> <mrow> <mi>n</mi> <mrow> <mo>/</mo> </mrow> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle c_{n}=1+c_{n/2}}</annotation> </semantics> </math></span><img src=

dont la complexité temporelle sera de . ${\displaystyle O(\log _{2}(n)) <semantics> <mrow> <mstyle> <mi>O</mi> <mo>(</mo> <msub> <mi>log</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mo>(</mo> <mi>n</mi> <mo>)</mo> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle O(\log _{2}(n))}</annotation> </semantics> </math><img src=$

Traitement numérique du signal

Dans le traitement numérique du signal , les relations de récurrence peuvent modéliser la rétroaction dans un système, où les sorties d'un moment donné deviennent des entrées pour un temps futur. Elles apparaissent ainsi dans les filtres numériques à réponse impulsionnelle infinie (RII) .

Par exemple, l'équation d'un filtre en peigne IIR « feedforward » à retard est : ${\displaystyle T <semantics> <mrow> <mstyle> <mi>T</mi> </mstyle> </mrow> <annotation>{\displaystyle T}</annotation> </semantics> </math><img src=$

{\displaystyle y_{t}=(1-\alpha )x_{t}+\alpha y_{t-T}, <semantics> <mrow> <mstyle> <msub> <mi>y</mi> <mrow> <mi>t</mi> </mrow> </msub> <mo>=</mo> <mo>(</mo> <mn>1</mn> <mo>−</mo> <mi>α</mi> <mo>)</mo> <msub> <mi>x</mi> <mrow> <mi>t</mi> </mrow> </msub> <mo>+</mo> <mi>α</mi> <msub> <mi>y</mi> <mrow> <mi>t</mi> <mo>−</mo> <mi>T</mi> </mrow> </msub> <mo>,</mo> </mstyle> </mrow> <annotation>{\displaystyle y_{t}=(1-\alpha )x_{t}+\alpha y_{t-T},}</annotation> </semantics> </math></span><img src=

où est l'entrée à l'instant , est la sortie à l'instant , et contrôle la quantité de signal retardé qui est réinjectée dans la sortie. De cela, nous pouvons voir que ${\displaystyle x_{t <semantics> <mrow> <mstyle> <msub> <mi>x</mi> <mrow> <mi>t</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle x_{t}}</annotation> </semantics> </math><img src=$ ${\displaystyle t <semantics> <mrow> <mstyle> <mi>t</mi> </mstyle> </mrow> <annotation>{\displaystyle t}</annotation> </semantics> </math><img src=$ ${\displaystyle y_{t <semantics> <mrow> <mstyle> <msub> <mi>y</mi> <mrow> <mi>t</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle y_{t}}</annotation> </semantics> </math><img src=$ ${\displaystyle t <semantics> <mrow> <mstyle> <mi>t</mi> </mstyle> </mrow> <annotation>{\displaystyle t}</annotation> </semantics> </math><img src=$ ${\displaystyle \alpha <semantics> <mrow> <mstyle> <mi>α</mi> </mstyle> </mrow> <annotation>{\displaystyle \alpha }</annotation> </semantics> </math><img src=$

{\displaystyle y_{t}=(1-\alpha )x_{t}+\alpha ((1-\alpha )x_{t-T}+\alpha y_{t-2T}) <semantics> <mrow> <mstyle> <msub> <mi>y</mi> <mrow> <mi>t</mi> </mrow> </msub> <mo>=</mo> <mo>(</mo> <mn>1</mn> <mo>−</mo> <mi>α</mi> <mo>)</mo> <msub> <mi>x</mi> <mrow> <mi>t</mi> </mrow> </msub> <mo>+</mo> <mi>α</mi> <mo>(</mo> <mo>(</mo> <mn>1</mn> <mo>−</mo> <mi>α</mi> <mo>)</mo> <msub> <mi>x</mi> <mrow> <mi>t</mi> <mo>−</mo> <mi>T</mi> </mrow> </msub> <mo>+</mo> <mi>α</mi> <msub> <mi>y</mi> <mrow> <mi>t</mi> <mo>−</mo> <mn>2</mn> <mi>T</mi> </mrow> </msub> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle y_{t}=(1-\alpha )x_{t}+\alpha ((1-\alpha )x_{t-T}+\alpha y_{t-2T})}</annotation> </semantics> </math></span><img src=

{\displaystyle y_{t}=(1-\alpha )x_{t}+(\alpha -\alpha ^{2})x_{t-T}+\alpha ^{2}y_{t-2T <semantics> <mrow> <mstyle> <msub> <mi>y</mi> <mrow> <mi>t</mi> </mrow> </msub> <mo>=</mo> <mo>(</mo> <mn>1</mn> <mo>−</mo> <mi>α</mi> <mo>)</mo> <msub> <mi>x</mi> <mrow> <mi>t</mi> </mrow> </msub> <mo>+</mo> <mo>(</mo> <mi>α</mi> <mo>−</mo> <msup> <mi>α</mi> <mrow> <mn>2</mn> </mrow> </msup> <mo>)</mo> <msub> <mi>x</mi> <mrow> <mi>t</mi> <mo>−</mo> <mi>T</mi> </mrow> </msub> <mo>+</mo> <msup> <mi>α</mi> <mrow> <mn>2</mn> </mrow> </msup> <msub> <mi>y</mi> <mrow> <mi>t</mi> <mo>−</mo> <mn>2</mn> <mi>T</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle y_{t}=(1-\alpha )x_{t}+(\alpha -\alpha ^{2})x_{t-T}+\alpha ^{2}y_{t-2T}}</annotation> </semantics> </math></span><img src=

etc.

Économie

Les relations de récurrence, en particulier les relations de récurrence linéaires, sont largement utilisées en économie théorique et empirique. En macroéconomie notamment, on peut développer un modèle de divers grands secteurs de l'économie (le secteur financier, le secteur des biens, le marché du travail, etc.) dans lesquels les actions de certains agents dépendent de variables décalées. Le modèle serait alors résolu pour les valeurs actuelles des variables clés ( taux d'intérêt , PIB réel , etc.) en termes de valeurs passées et actuelles d'autres variables.