Séquence constante-récursive - Constant-recursive sequence

En mathématiques , une suite récursive constante ou une suite C-finie est une suite satisfaisant une récurrence linéaire à coefficients constants.

Définition

Un order- d homogène récurrence linéaire à coefficients constants est une équation de la forme

${\displaystyle s(n)=c_{1}s(n-1)+c_{2}s(n-2)+\dots +c_{d}s(nd),}$

où les coefficients d sont des constantes. ${\displaystyle c_{1},c_{2},\dots ,c_{d}}$

Une séquence est une suite récurrente constante s'il y a un order- d homogène récurrence linéaire à coefficients constants qu'il satisfait à tous . ${\style d'affichage s(0),s(1),s(2),\dots }$${\style d'affichage n\geq d}$

De manière équivalente, est constant-récursif si l'ensemble des séquences ${\style d'affichage s(n)_{n\geq 0}}$

${\displaystyle \{s(n+r)_{n\geq 0}:r\geq 0\}}$

est contenu dans un espace vectoriel dont la dimension est finie.

Exemples

séquence de Fibonacci

La suite 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... des nombres de Fibonacci satisfait la récurrence

${\style d'affichage F_{n}=F_{n-1}+F_{n-2}}$

avec conditions initiales

${\style d'affichage F_{0}=0}$

${\style d'affichage F_{1}=1.}$

Explicitement, la récurrence donne les valeurs

${\displaystyle F_{2}=F_{1}+F_{0}=1}$

${\style d'affichage F_{3}=F_{2}+F_{1}=2}$

${\style d'affichage F_{4}=F_{3}+F_{2}=3}$

${\style d'affichage F_{5}=F_{4}+F_{3}=5}$

etc.

séquences de Lucas

La suite 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, ... (suite A000032 dans l' OEIS ) des nombres de Lucas satisfait la même récurrence que la suite de Fibonacci mais avec l'initiale conditions

${\style d'affichage L_{0}=2}$

${\style d'affichage L_{1}=1.}$

Plus généralement, chaque séquence de Lucas est une séquence constante-récursive.

Séquences géométriques

La suite géométrique est constante-récursive, puisqu'elle satisfait la récurrence pour tout . ${\displaystyle a,ar,ar^{2},\dots }$${\style d'affichage s(n)=rs(n-1)}$${\style d'affichage n\geq 1}$

Séquences éventuellement périodiques

Une séquence qui est finalement périodique avec une longueur de période est constante-récursive, car elle satisfait pour tout pour certains . ${\style d'affichage \ell }$${\style d'affichage s(n)=s(n-\ell )}$${\style d'affichage n\geq d}$${\style d'affichage d}$

Suite polynomiale

Pour tout polynôme s ( n ), la séquence de ses valeurs est une séquence constante-récursive. Si le degré du polynôme est d , la séquence satisfait une récurrence d'ordre , avec des coefficients donnés par l'élément correspondant de la transformée binomiale . Les premières équations de ce type sont ${\style d'affichage d+1}$

${\style d'affichage s(n)=1\cdot s(n-1)}$ pour un polynôme de degré 0 (c'est-à-dire constant),

${\displaystyle s(n)=2\cdot s(n-1)-1\cdot s(n-2)}$ pour un polynôme de degré 1 ou moins,

${\displaystyle s(n)=3\cdot s(n-1)-3\cdot s(n-2)+1\cdot s(n-3)}$ pour un polynôme de degré 2 ou moins, et

${\displaystyle s(n)=4\cdot s(n-1)-6\cdot s(n-2)+4\cdot s(n-3)-1\cdot s(n-4)}$ pour un polynôme de degré 3 ou moins.

Une séquence obéissant à l' équation d'ordre d obéit également à toutes les équations d'ordre supérieur. Ces identités peuvent être prouvées de plusieurs manières, notamment via la théorie des différences finies . Chaque équation individuelle peut également être vérifiée en substituant le polynôme degré- d

${\displaystyle s(x)=\sum _{k=0}^{d}a_{k}x^{k},}$

où les coefficients sont symboliques. Toute séquence de valeurs entières, réelles ou complexes peut être utilisée comme conditions initiales pour une séquence constante-récursive d'ordre . Si les conditions initiales reposent sur un polynôme de degré ou moins, alors la séquence constante-récursive obéit également à une équation d'ordre inférieur. ${\displaystyle a_{k}}$${\style d'affichage d+1}$${\style d'affichage d+1}$${\style d'affichage d-1}$

Énumération de mots dans une langue régulière

Soit un langage régulier , et soit le nombre de mots de longueur dans . Alors est constant-récursif. ${\style d'affichage L}$${\style d'affichage s(n)}$${\style d'affichage n}$${\style d'affichage L}$${\style d'affichage s(n)_{n\geq 0}}$

Autres exemples

Les séquences de nombres Jacobsthal , numéros Padovan et numéros Pell sont récursif constant.

Caractérisation en termes de polynômes exponentiels

Le polynôme caractéristique (ou « polynôme auxiliaire ») de la récurrence est le polynôme

${\displaystyle x^{d}-c_{1}x^{d-1}-\dots -c_{d-1}x-c_{d}}$

dont les coefficients sont les mêmes que ceux de la récurrence. Le n ième terme d'une suite constante-récursive peut être écrit en termes de racines de son polynôme caractéristique. Si les racines d sont toutes distinctes, alors le n ième terme de la suite est ${\style d'affichage s(n)}$${\displaystyle r_{1},r_{2},\dots ,r_{d}}$

${\displaystyle s(n)=k_{1}r_{1}^{n}+k_{2}r_{2}^{n}+\dots +k_{d}r_{d}^{n}}$

où les coefficients k _i sont des constantes qui peuvent être déterminées à partir des conditions initiales.

Pour la suite de Fibonacci, le polynôme caractéristique est , dont les racines et apparaissent dans la formule de Binet${\style d'affichage x^{2}-x-1}$${\displaystyle \phi ={\frac {1+{\sqrt {5}}}{2}}}$${\displaystyle {\bar {\phi }}={\frac {1-{\sqrt {5}}}{2}}}$

${\displaystyle F_{n}={\frac {\phi ^{n}-{\bar {\phi }}^{n}}{\sqrt {5}}}.}$

Plus généralement, si une racine r du polynôme caractéristique a une multiplicité m , alors le terme est multiplié par un polynôme de degré en n . Autrement dit, laissez être les racines distinctes du polynôme caractéristique. Puis ${\style d'affichage r^{n}}$${\style d'affichage (m-1)}$${\displaystyle r_{1},\dots ,r_{e}}$

${\displaystyle s(n)=k_{1}(n)r_{1}^{n}+k_{2}(n)r_{2}^{n}+\dots +k_{e}(n) r_{e}^{n}}$

où est un polynôme de degré . Par exemple, si les facteurs polynomiaux caractéristiques comme , avec la même racine r apparaissant trois fois, alors le n ième terme est de la forme ${\style d'affichage k_{i}(n)}$${\style d'affichage m_{i}-1}$${\style d'affichage (xr)^{3}}$

${\displaystyle s(n)=(a+bn+cn^{2})r^{n}.}$

Inversement, s'il existe des polynômes tels que ${\style d'affichage k_{i}(n)}$

${\displaystyle s(n)=k_{1}(n)r_{1}^{n}+k_{2}(n)r_{2}^{n}+\dots +k_{e}(n) r_{e}^{n},}$

alors est constant-récursif. ${\style d'affichage s(n)_{n\geq 0}}$

Caractérisation en termes de fonctions génératrices rationnelles

Une suite est constante-récursive précisément lorsque sa fonction génératrice

${\displaystyle \sum _{n\geq 0}s(n)x^{n}=s(0)+s(1)x^{1}+s(2)x^{2}+s(3 )x^{3}+\cdots }$

est une fonction rationnelle . Le dénominateur est le polynôme obtenu à partir du polynôme auxiliaire en inversant l'ordre des coefficients, et le numérateur est déterminé par les valeurs initiales de la séquence.

La fonction génératrice de la suite de Fibonacci est

${\displaystyle {\frac {x}{1-xx^{2}}}.}$

En général, multiplier une fonction génératrice par le polynôme

${\displaystyle 1-c_{1}x^{1}-c_{2}x^{2}-\dots -c_{d}x^{d}}$

donne une série

${\displaystyle \left(s(0)+s(1)x^{1}+s(2)x^{2}+\cdots \right)\left(1-c_{1}x^{1} -c_{2}x^{2}-\dots -c_{d}x^{d}\right)=\left(b_{0}+b_{1}x^{1}+b_{2}x ^{2}+\cdots \right),}$

où

${\displaystyle b_{n}=s(n)-c_{1}s(n-1)-c_{2}s(n-2)-\dots -c_{d}s(nd).}$

Si satisfait la relation de récurrence ${\style d'affichage s(n)}$

${\displaystyle s(n)=c_{1}s(n-1)+c_{2}s(n-2)+\dots +c_{d}s(nd),}$

alors pour tous . Autrement dit, ${\style d'affichage b_{n}=0}$${\style d'affichage n\geq d}$

${\displaystyle \left(s(0)+s(1)x^{1}+s(2)x^{2}+\cdots \right)\left(1-c_{1}x^{1} -c_{2}x^{2}-\dots -c_{d}x^{d}\right)=\left(b_{0}+b_{1}x^{1}+b_{2}x ^{2}+\dots +b_{d-1}x^{d-1}\right),}$

on obtient donc la fonction rationnelle

${\displaystyle \sum _{n\geq 0}s(n)x^{n}={\frac {b_{0}+b_{1}x^{1}+b_{2}x^{2} +\dots +b_{d-1}x^{d-1}}{1-c_{1}x^{1}-c_{2}x^{2}-\dots -c_{d}x^ {ré}}}.}$

Dans le cas particulier d'une suite périodique vérifiant pour , la fonction génératrice est ${\style d'affichage s(n)=s(nd)}$${\style d'affichage n\geq d}$

${\displaystyle {\begin{aligned}{\frac {s(0)+s(1)x^{1}+\dots +s(d-1)x^{d-1}}{1-x^ {d}}}=&\gauche(s(0)+s(1)x^{1}+\dots +s(d-1)x^{d-1}\right)+\gauche(s( 0)+s(1)x^{1}+\dots +s(d-1)x^{d-1}\right)x^{d}+{}\\&\left(s(0) +s(1)x^{1}+\dots +s(d-1)x^{d-1}\right)x^{2d}+\cdots \end{aligned}}}$

en développant la série géométrique.

La fonction génératrice des nombres de Catalan n'est pas une fonction rationnelle, ce qui implique que les nombres de Catalan ne satisfont pas à une récurrence linéaire à coefficients constants.

Propriétés de fermeture

L'addition ou la multiplication par terme de deux séquences constantes-récursives est à nouveau constante-récursive. Ceci découle de la caractérisation en termes de polynômes exponentiels.

Le produit de Cauchy de deux séquences récursives constantes est récursive constante. Ceci découle de la caractérisation en termes de fonctions génératrices rationnelles.

Séquences satisfaisant des récurrences non homogènes

Une séquence satisfaisant une récurrence linéaire non homogène à coefficients constants est constante-récursive.

C'est parce que la récurrence

${\style d'affichage s(n)=c_{1}s(n-1)+c_{2}s(n-2)+\dots +c_{d}s(nd)+c}$

peut être résolu pour obtenir ${\style d'affichage c}$

${\displaystyle c=s(n)-c_{1}s(n-1)-c_{2}s(n-2)-\dots -c_{d}s(nd).}$

En substituant ceci dans l'équation

${\displaystyle s(n+1)=c_{1}s(n)+c_{2}s(n-1)+\dots +c_{d}s(n+1-d)+c}$

montre que satisfait la récurrence homogène ${\style d'affichage s(n)}$

${\displaystyle s(n+1)=(c_{1}+1)s(n)+(c_{2}-c_{1})s(n-1)+\dots +(c_{d}- c_{d-1})s(n+1-d)-c_{d}s(nd)}$

d'ordre . ${\style d'affichage d+1}$

Généralisations

Une généralisation naturelle est obtenue en relâchant la condition que les coefficients de récurrence soient constants. Si les coefficients sont autorisés à être des polynômes, alors on obtient des séquences holonomiques .

Une séquence régulière satisfait des récurrences linéaires à coefficients constants, mais les récurrences prennent une forme différente. Plutôt que d' être une combinaison linéaire de pour certains entiers proches de , chaque terme d'une séquence régulière est une combinaison linéaire de pour certains entiers dont les représentations de base sont proches de celle de . Les séquences constantes-récursives peuvent être considérées comme des séquences régulières, où la représentation en base 1 de consiste en des copies du chiffre . ${\style d'affichage k}$${\style d'affichage s(n)}$${\style d'affichage s(m)}$${\style d'affichage m}$${\style d'affichage n}$${\style d'affichage s(n)}$${\style d'affichage k}$${\style d'affichage s(m)}$${\style d'affichage m}$${\style d'affichage k}$${\style d'affichage n}$${\style d'affichage 1}$${\style d'affichage n}$${\style d'affichage n}$${\style d'affichage 1}$

Remarques

Les références

• Brousseau, Alfred (1971). Récursion linéaire et séquences de Fibonacci . Association de Fibonacci.
• Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994). Mathématiques concrètes : Une Fondation pour l'Informatique (2 éd.). Addison-Wesley. ISBN 978-0-201-55802-9.

Voir également

• Matrice d'accompagnement

Liens externes

• "Enregistrement de l'index OEIS" . Index OEIS à quelques milliers d'exemples de récurrences linéaires, triés par ordre (nombre de termes) et signature (vecteur de valeurs des coefficients constants)