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 :
Le nombre formula_2 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 formula_3 et formula_4 :
Prenons par exemple la multiplication d'une suite récurrente linéaire par une constante.
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 :
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 formula_9 sont les solutions de l'équation formula_10. 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 formula_11 racines, notées formula_12, formula_13, formula_14, ..., formula_15. Dans ce cas, on sait qu'il existe formula_11 coefficients constants formula_17 tels que :
Déterminer la valeur des coefficients formula_17 n'est pas si difficile. Il suffit de résoudre un système à n équations, qui s'obtient en testant les formula_11 premières valeurs de la suite.
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 :
Le polynôme caractéristique associé à ces suites est :
Les racines de cette équation sont notées formula_12 et formula_13. On se retrouve alors dans deux cas :
Les constantes formula_35 et formula_36 sont deux constantes qui se déterminent à partir de la valeur des deux premiers termes de la suite. On a naturellement les conditions suivantes :
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.
Toutes les équations de ce genre ont un rapport avec le nombre d'or formula_40, un nombre égal à formula_41, 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 :
Ce polynôme possède deux racines, la première étant le fameux nombre d'or formula_40 et la seconde son inverse.
Vu qu'il y a deux racines différentes, l'équation paramétrée des suites de Lucas est la suivante :
On peut remarquer que si le rang n est assez grand, le terme : formula_47 tend vers zéro, le dénominateur devant très grand. Dans ce cas, on peut le négliger, ce qui donne :
Maintenant, étudions le rapport entre deux termes consécutifs : formula_49. Ce rapport vaut, par définition :
Si l'on prend la limite, les termes formula_51 et formula_52 s'annulent. Dit autrement, peut remplacer numérateur et dénominateur par l'approximation précédente (formula_53). On obtient alors une formule qui dit que lorsque l'on prend la limite formula_54, le rapport formula_49 tend vers le nombre d'or.
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 formula_49, mais on ne peut pas faire plus sans connaître les deux coefficients formula_35 et formula_36. 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 
Il s'agit du cas particulier où formula_61 et formula_62. Ses premiers termes sont naturellement :
Cette suite respecte bien la relation de récurrence formula_39, ce qui fait qu'on a :
Vous pouvez vérifier cela par vous-même en calculant les premières puissances du nombre d'or :
La suite de Lucas.
La suite de Lucas a pour premiers termes formula_76 et formula_77. On peut alors calculer les coefficients gamma et lambda avec les conditions suivantes :
Ce qui donne :
On a alors la pièce finale, l'équation paramétrée de la suite de Lucas :
La voici :
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 :
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 :
Ce qui donne :
On a alors la pièce finale, l'équation paramétrée de la suite de Fibonacci :
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 formula_89. 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.