Les suites et séries/Les suites récurrentes linéaires

Les suites vues dans le premier chapitre sont des suites récurrentes, qui calculent chaque terme en fonction du précédent. Certaines suites vont cependant un peu plus loin et calculent chaque terme en fonction des deux précédents, des trois précédents, voire de tous les termes précédents ! Le cas les plus simples vont se contenter d'additionner les termes précédents. D'autres suites vont encore plus généraliser les fonctions précédentes, on ajoutant une caractéristique des suites géométriques : l'usage d'une multiplication par une constante. Pour cela, les termes sont tous additionnés, mais seulement après avoir été multipliés par une constante. Ces suites sont les suites récurrentes linéaires. On peut les voir comme une généralisation des suites arithmético-géométriques, ce qui transparaît dans leur définition.

Les propriétés générales des suites récurrentes linéaires

Le suites récurrentes linéaires sont décrites par une équation de récurrence qui a la forme suivante :

$u_{n}=u_{n-1}\times a_{n-1}+u_{n-2}\times a_{n-2}+u_{n-3}\times a_{n-3}+...+u_{n-k}\times a_{n-k}$

Le nombre $k$ de l'équation précédente est le nombre de termes précédents utilisés pour calculer le prochain. Il porte un nom : c'est l'ordre de la suite, ou encore son degré.

Au passage, les suites arithmético-géométriques sont des suites récurrentes linéaires d'ordre 1. Et en conséquence, les suites géométriques et arithmétiques en sont aussi : les suites géométriques sont des suites récurrentes linéaires d'ordre 1, les suites arithmétiques et constantes sont d'ordre 0. Dans la suite du cours, nous allons surtout nous concentrer sur les suites d'un ordre supérieur, au moins égal à 2.

Les opérations sur les suites récurrentes linéaires

Les suites récurrentes linéaires peuvent être additionnées, soustraites, multipliées et divisées, tout comme les autres suites. À ce propos, il est facile de prouver que, pour des suites récurrentes linéaires $(u_{n})$ et $(v_{n})$ :

$(u_{n})+(v_{n})$ est une suite récurrente linéaire ;

$\lambda \cdot (u_{n})$ est une suite récurrente linéaire ;

$(u_{n})*(v_{n})$ est une suite récurrente linéaire.

Prenons par exemple la multiplication d'une suite récurrente linéaire par une constante.

Démonstration

Pour cela, prenons une suite $(u_{n})$ et multiplions par une constante. Regardons ce qui se passe au niveau de la relation de récurrence. Par définition, la relation de récurrence de la suite $(u_{n})$ est de la forme : $u_{n}=u_{n-1}\times a_{n-1}+u_{n-2}\times a_{n-2}+u_{n-3}\times a_{n-3}+...+u_{n-k}\times a_{n-k}$ Multiplions maintenant par $\lambda$ : $\lambda \cdot u_{n}=\lambda \cdot (u_{n-1}\times a_{n-1}+u_{n-2}\times a_{n-2}+u_{n-3}\times a_{n-3}+...+u_{n-k}\times a_{n-k})$ Développons : $\lambda \cdot u_{n}=u_{n-1}\times (\lambda \cdot a_{n-1})+u_{n-2}\times (\lambda \cdot a_{n-2})+u_{n-3}\times (\lambda \cdot a_{n-3})+...+u_{n-k}\times (\lambda \cdot a_{n-k})$ On voit que le terme de droite peut se mettre sous la forme suivante, qui est la relation de récurrence d'une suite récurrente linéaire : $u_{n}=u_{n-1}\times b_{n-1}+u_{n-2}\times b_{n-2}+u_{n-3}\times b_{n-3}+...+u_{n-k}\times b_{n-k}$

Des développements similaires permettent de prouver la même chose, mais pour l'addition ou la multiplication de deux suites récurrentes linéaires. En sachant cela, on peut démontrer que l'ensemble des suites récurrentes linéaires respecte toutes les conditions pour être qualifié d'espace vectoriel.

Le polynôme caractéristique d'une suite récurrente linéaire

Le nombre de termes utilisés pour calculer le prochain porte un nom : c'est l'ordre de la suite, ou encore son degré. Vous avez peut-être remarqué que le terme "ordre" est aussi utilisé pour les polynômes, et ce n'est pas un hasard. Il y a un lien assez franc entre les polynômes et les suites récurrentes linéaires. L'étude de ces dernières se base essentiellement sur l'étude de leur polynôme caractéristique. Celui-ci est un polynôme dont le degré est le même que celui de la suite et dont les coefficients sont les mêmes que ceux de l'équation de récurrence qui définit la suite. En clair, il vaut, pour une suite d'ordre n :

$P(x)=a_{n}\times x^{n}+a_{n-1}\times x^{n-1}++a_{n-2}\times x^{n-2}...+a_{2}\times x^{2}+a_{1}\times x+a_{0}$

Les racines de ce polynôme sont d'une importance capitale pour l'étude de la suite associée. Pour rappel, les racines d'un polynôme $P(x)$ sont les solutions de l'équation $P(x)=0$. Les racines du polynômes caractéristiques permettent de déterminer la limite de la suite, ainsi que son expression paramétrée. Prenons le cas d'une suite récurrente linéaire quelconque. Supposons que le polynôme caractéristique associé a $i$ racines, notées $r_{1}$, $r_{2}$, $r_{3}$, ..., $r_{i}$. Dans ce cas, on sait qu'il existe $i$ coefficients constants $\lambda _{i}$ tels que :

$u_{n}=\lambda _{1}\cdot r_{1}^{n}+\lambda _{2}\cdot r_{2}^{n}+\lambda _{3}\cdot r_{3}^{n}+...+\lambda _{i}\cdot r_{i}^{n}$

Déterminer la valeur des coefficients $\lambda _{i}$ n'est pas si difficile. Il suffit de résoudre un système à n équations, qui s'obtient en testant les $i$ premières valeurs de la suite.

$u_{0}=\lambda _{1}+\lambda _{2}+\lambda _{3}+...+\lambda _{i}$, où $n=0$.

$u_{1}=\lambda _{1}\cdot r_{1}+\lambda _{2}\cdot r_{2}+\lambda _{3}\cdot r_{3}+...+\lambda _{i}\cdot r_{i}$, où $n=1$.

$u_{2}=\lambda _{1}\cdot r_{1}^{2}+\lambda _{2}\cdot r_{2}^{2}+\lambda _{3}\cdot r_{3}^{2}+...+\lambda _{i}\cdot r_{i}^{2}$, où $n=2$.

...

$u_{i}=\lambda _{1}\cdot r_{1}^{i}+\lambda _{2}\cdot r_{2}^{i}+\lambda _{3}\cdot r_{3}^{i}+...+\lambda _{i}\cdot r_{i}^{i}$, où $n=i$.

Les suites récurrentes linéaires d'ordre 2

Dans ce qui va suivre, nous allons surtout étudier les suites d'ordre 2, à savoir celles de la forme suivante :

$u_{n}=a\times u_{n-1}+b\times u_{n-2}$

Le polynôme caractéristique associé à ces suites est :

$r^{2}+ar+b=0$

Les racines de cette équation sont notées $r_{1}$ et $r_{2}$. On se retrouve alors dans deux cas :

• les deux racines sont différentes : la formule paramétrée est alors égale à : $u_{n}=\lambda \cdot r_{1}^{n}+\gamma \cdot r_{2}^{n}$.
• les deux racines sont égales : la formule paramétrée est alors égale à : $u_{n}=(\lambda +\gamma )\times r_{1}^{n}$.

Les constantes $\lambda$ et $\gamma$ sont deux constantes qui se déterminent à partir de la valeur des deux premiers termes de la suite. On a naturellement les conditions suivantes :

• $\lambda +\gamma =u_{0}$ ;
• $\lambda \cdot r_{1}+\gamma \cdot r_{2}=u_{1}$.

Les suites de type "Lucas"

Le cas le plus simple de suite récurrente linéaire d'ordre 2 est celui où chaque terme est la somme des deux précédents.

$u_{n}=u_{n-1}+u_{n-2}$

Toutes les équations de ce genre ont un rapport avec le nombre d'or $\varphi$, un nombre égal à $\varphi \approx 1.61803398874989$, très souvent abordé dans les ouvrages de mathématiques amusantes. Ce lien vient du fait que ce nombre d'or est une des deux racines de l'équation caractéristique. Il apparaît donc naturellement dans la recherche d'une forme paramétrée des suites de Lucas.

La formulation des suites de Lucas fait qu'il s'agit de suites récurrentes linéaires d'ordre 2 dont les coefficient a et b valent tous deux 1. Le polynôme caractéristique de cette récurrence est :

$r^{2}-r-1=0$

Ce polynôme possède deux racines, la première étant le fameux nombre d'or $\varphi$ et la seconde son inverse.

$r_{1}={\frac {1+{\sqrt {5}}}{2}}=\varphi$

$r_{2}={\frac {1-{\sqrt {5}}}{2}}=1-\varphi ={\frac {1}{\varphi }}$

Vu qu'il y a deux racines différentes, l'équation paramétrée des suites de Lucas est la suivante :

$u_{n}=\lambda \cdot \varphi ^{n}+\gamma \cdot {\frac {1}{\varphi ^{n}}}$.

On peut remarquer que si le rang n est assez grand, le terme : ${\frac {1}{\varphi ^{n}}}$ tend vers zéro, le dénominateur devant très grand. Dans ce cas, on peut le négliger, ce qui donne :

$u_{n}\approx \lambda \times \varphi ^{n}$.

Maintenant, étudions le rapport entre deux termes consécutifs : ${\frac {u_{n+1}}{u_{n}}}$. Ce rapport vaut, par définition :

${\frac {u_{n+1}}{u_{n}}}={\frac {\lambda \varphi ^{n+1}+\gamma {\frac {1}{\varphi ^{n+1}}}}{\lambda \varphi ^{n}+\gamma {\frac {1}{\varphi ^{n}}}}}$

Si l'on prend la limite, les termes ${\frac {1}{\varphi ^{n+1}}}$ et ${\frac {1}{\varphi ^{n}}}$ s'annulent. Dit autrement, peut remplacer numérateur et dénominateur par l'approximation précédente ($u_{n}\approx \lambda \times \varphi ^{n}$). On obtient alors une formule qui dit que lorsque l'on prend la limite $n\rightarrow \infty$, le rapport ${\frac {u_{n+1}}{u_{n}}}$ tend vers le nombre d'or.

$\lim _{n\to \infty }{\frac {u_{n+1}}{u_{n}}}={\frac {\lambda \times \varphi ^{n+1}}{\lambda \times \varphi ^{n}}}={\frac {\varphi ^{n+1}}{\varphi ^{n}}}=\varphi$

Les deux résultats précédents sont tout ce qu'on peut déduire de l'étude des suites de Lucas dans le cas général. On peut déterminer leur expression paramétrée et trouver la limite du rapport ${\frac {u_{n+1}}{u_{n}}}$, mais on ne peut pas faire plus sans connaître les deux coefficients $\lambda$ et $\gamma$. Pour aller plus loin, on doit étudier des cas particuliers, où l'on a précisé les deux premiers termes. Or, il existe plusieurs suites avec cette relation récurrente, mais qui différent par leurs deux premiers termes. La plus connue est la suite de Fibonacci, une suite avec une certaine renommée, qui est souvent abordée dans les livres de mathématiques récréatives. Celle-ci est apparue pour la première fois dans un problème de mathématiques récréatives crée par Leonardo Fibonacci, qui donna son nom à cette suite. Ce problème impliquait un problème de lapins qui se reproduisent dans un enclos, ce problème étant assez connu. Une autre suite de ce genre est la suite de Lucas. Mais la plus simple est de loin la suite des puissances du nombre d'or.

La suite des puissances du nombre d'or

La suite des puissances du nombre d'or est la suite définie par

$u_{n}=\varphi ^{n}$

Il s'agit du cas particulier où $\lambda =1$ et $\gamma =0$. Ses premiers termes sont naturellement :

$u_{0}=\varphi ^{0}=1$ et $u_{1}=\varphi ^{1}=\varphi$

Cette suite respecte bien la relation de récurrence $u_{n}=u_{n-1}+u_{n-2}$, ce qui fait qu'on a :

$\varphi ^{n}=\varphi ^{n-1}+\varphi ^{n-2}$

Vous pouvez vérifier cela par vous-même en calculant les premières puissances du nombre d'or :

$\varphi ^{0}=1$

$\varphi ^{1}=1,6180339887$

$\varphi ^{2}=\varphi ^{1}+\varphi ^{0}=2,6180339887$

$\varphi ^{3}=\varphi ^{2}+\varphi ^{1}=4.2360679775$

$\varphi ^{4}=\varphi ^{3}+\varphi ^{2}=6.85410196625$

$\varphi ^{5}=\varphi ^{4}+\varphi ^{3}=11.0901699437$

$\varphi ^{6}=\varphi ^{5}+\varphi ^{4}=17.94427191$

$\varphi ^{7}=\varphi ^{6}+\varphi ^{5}=29.0344418537$

$\cdots$

La suite de Lucas

La suite de Lucas a pour premiers termes $u_{0}=2$ et $u_{1}=1$. On peut alors calculer les coefficients gamma et lambda avec les conditions suivantes :

• $\lambda +\gamma =2$ ;
• $\lambda r_{1}+\gamma r_{2}=1$.

Ce qui donne :

$\lambda =1$ et $\gamma =-1$

On a alors la pièce finale, l'équation paramétrée de la suite de Lucas :

$u_{n}=\left(\varphi ^{n}+{\frac {1}{\varphi ^{n}}}\right)\approx \varphi ^{n}$

La voici :

$2,1,3,4,7,11,18,29,47,76,123,199,322,521,843,1364,2207,3571,5778,9349,15127,24476,39603,64079,\cdots$

La suite de Fibonacci

La suite de Fibonacci la même relation de récurrence que la suite de Lucas, sauf que ses premiers termes sont respectivement 0 et 1, ce qui donne la suite suivante :

Fibonacci sequence - optional starting with zero

Vu qu'elle a la même relation de récurrence que la suite de Lucas, elle a la même équation caractéristique et a donc les mêmes racines. Seuls les coefficients gamma et lambda changent, eux seuls étant influencés par les deux premiers termes. Dans le cas de la suite de Fibonacci, ceux-ci valent :

• $\lambda +\gamma =0$ ;
• $\lambda r_{1}+\gamma r_{2}=1$.

Ce qui donne :

$\lambda ={\frac {1}{\sqrt {5}}}$ et $\gamma =-{\frac {1}{\sqrt {5}}}$

On a alors la pièce finale, l'équation paramétrée de la suite de Fibonacci :

$u_{n}={\frac {1}{\sqrt {5}}}\left(\varphi ^{n}+{\frac {1}{\varphi ^{n}}}\right)\approx {\frac {\varphi ^{n}}{\sqrt {5}}}$

On voit que chaque terme de la suite de Fibonacci est un multiple du même terme de la suite de Lucas : la seule différence est le facteur ${\frac {1}{\sqrt {5}}}$. Après tout, les deux suites partagent la même relation de récurrence. Pas étonnant que les propriétés de la suite de Lucas se retrouvent donc dans la suite de Fibonnaci.