Théorie > Algèbre > Suites

Prérequis

Résumé

Les suites interviennent souvent dans les problèmes d'algèbre, que ce soit dans leur énoncé ou de manière plus cachée. Dans tous les cas, il faut être capable d'analyser une suite de nombres et d'en trouver les propriétés pour résoudre ces problèmes.

Ce chapitre a été écrit par N. Radu et mis en ligne le 8 décembre 2014.

1. Définition

Une suite est simplement une succession d'éléments indicée par les nombres naturels (le premier indice étant parfois $0$, parfois $1$) :
$$a_0, a_1, a_2, \ldots, a_{n-1}, a_n, a_{n+1}, \ldots$$ On note généralement une telle suite par $(a_n)_{n \in \mathbb{N}}$ si le premier indice est $0$ et par $(a_n)_{n \in \mathbb{N}_0}$ si le premier indice est $1$. On raccourcit souvent la notation en notant simplement $(a_n)$. La plupart du temps, les éléments $a_n$ sont réels, mais il n'est bien sûr pas interdit qu'il s'agisse de nombres complexes ou même de choses plus particulières. On pourrait par exemple avoir une suite de polynômes (chaque $a_n$ serait un polynôme).

Lorsque l'on introduit une suite particulière, on ne donne évidemment pas les éléments un par un. Il y a en fait plusieurs manières de donner une suite :

  1. On peut définir une suite en donnant une formule dépendant de $n$. Par exemple :

    • Les premiers éléments de la suite $(a_n)_{n \in \mathbb{N}}$ définie par $a_n = n^2 + 1$ sont $1, 2, 5, 10, 17, 26, \ldots$

    • Les premiers éléments de la suite $(a_n)_{n \in \mathbb{N}}$ définie par $a_n = \frac{n}{2^n}$ sont $0, \frac{1}{2}, \frac{1}{2}, \frac{3}{8}, \frac{1}{4}, \frac{5}{32}, \ldots$

    • On peut aussi définir la suite de polynômes $(P_n)_{n \in \mathbb{N}}$ avec $P_n(x) = x^n+x^{n-1}+\ldots+x+1$.

  2. On peut définir une suite en donnant la valeur des premiers éléments ainsi qu'une relation de récurrence. Par exemple :

    • La suite $(F_n)_{n \in \mathbb{N}}$ définie par $F_0 = 0$, $F_1 = 1$ et $F_n = F_{n-1}+F_{n-2}$ pour $n \geq 2$ est la suite de Fibonacci dont les premiers éléments sont
      $$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots$$

    • La suite $(a_n)_{n \in \mathbb{N}}$ définie par $a_0 = 1$, $a_1 = 2$ et $a_n = a_{n-1}a_{n-2} - 3$ pour $n \geq 2$ a pour premiers éléments
      $$1, 2, -1, -5, 2, -13, -29, 374, \ldots$$

  3. On peut également utiliser une des deux méthodes précédentes mais de manière un peu plus énigmatique, en ne donnant pas explicitement une formule.

    • La suite $(a_n)_{n \in \mathbb{N}_0}$ définie par $a_n = $ nombre de puissances $n$-èmes parfaites positives ayant exactement $n$ chiffres et contenant le dernier chiffre de $n$. On peut trouver les premiers éléments de cette suite (mais il ne semble a priori pas évident de trouver la formule générale) :
      $$1, 1, 1, 2, 1 \ldots$$

    • La suite $(c_n)_{n \in \mathbb{N}}$ de nombres entiers définie par $c_0 = 0$ et, pour $n \geq 1$, $c_n = 1 + d$ où $d$ est le dernier chiffre de $c_0+c_1+ \ldots+ c_{n-1}$ a pour premiers éléments
      $$0, 1, 2, 4, 8, 6, 2, 4, 8, 6, \ldots$$

2. Suites récurrentes linéaires

Connaître une suite $(a_n)$ uniquement grâce à une relation de récurrence n'est pas toujours satisfaisant. On préfère souvent connaître la suite de manière précise, c'est-à-dire avoir une formule pour $a_n$ dépendant de $n$. On peut parfois deviner cette formule en regardant les premiers termes de la suite, auquel cas vérifier que la formule est correcte est très simple : il suffit de vérifier qu'elle l'est pour les premiers termes et montrer par récurrence (grâce à la relation) qu'elle est en fait correcte pour tous les termes. Il n'est cependant parfois pas évident de deviner la formule générale (et il pourrait a priori ne pas exister de formule simple).

Dans un cas assez général, celui des suites linéaires récurrentes, il existe en fait une méthode pour trouver quelle est la formule qui se cache derrière la suite initialement définie par récurrence. On parle de suite linéaire récurrente d'ordre $p$ pour désigner une suite $(a_n)_{n \in \mathbb{N}}$ à valeur dans $\mathbb{C}$ (il peut en fait s'agir d'un corps commutatif quelconque) définie par une relation de récurrence de la forme suivante :
$$\left\{ \begin{array}{l}
a_0, a_1, \ldots, a_{p-1} \text{ sont fixés,}\\
a_{n+p} = c_0 a_n + c_1 a_{n+1} + \ldots + c_{p-1} a_{n+p-1} \text{ pour } n \geq 0.
\end{array}\right.$$
Exemples :
  • La suite $(a_n)$ définie par $a_0 = 0$, $a_1 = -1$, $a_2 = 5$ et $a_{n+3} = 3a_{n+2}-4a_n$ (pour $n \geq 0$) dont les premiers termes sont
    $$0, -1, 5, 15, 49, \ldots$$ est une suite linéaire récurrente d'ordre $3$.

  • La suite de Fibonacci $(F_n)$ (définie par $F_0 = 0$, $F_1 = 1$ et $F_{n+2} = F_{n+1} + F_n$ pour $n \geq 0$) est une suite linéaire récurrente d'ordre $2$.

La méthode pour trouver la formule générale derrière de telles suites est d'utiliser le résultat suivant, dont nous ne donnons pas la démonstration.

Théorème
Soit $(a_n)$ une suite de nombres complexes telle que
$$a_{n+p} = c_0 a_n + c_1 a_{n+1} + \ldots + c_{p-1} a_{n+p-1} \ \text{ pour } n \geq 0$$ (pour certains $c_0, c_1, \ldots, c_{p-1} \in \mathbb{C}$ fixés). Considérons le polynôme
$$P(x) = x^p - c_{p-1} x^{p-1} - c_{p-2} x^{p-2} - \ldots - c_1 x - c_0,$$ appelé polynôme caractéristique associé à la suite $(a_n)$. Si $r_1, r_2, \ldots, r_k$ sont les $k$ racines distinctes de $P$, de multiplicités respectives $m_1, m_2, \ldots, m_k$, alors il existe des polynômes $Q_1, Q_2, \ldots, Q_k \in \mathbb{C}[x]$ avec $\deg Q_i \leq m_i - 1$ tels que
$$a_n = Q_1(n) \cdot r_1^n + Q_2(n) \cdot r_2^n + \ldots + Q_k(n) \cdot r_k^n \ \text{ pour } n \geq 0.$$

Ce résultat nous donne donc une formule pour $a_n$ comme espéré. Il reste cependant que l'on ne connaît pas les polynômes $Q_1, \ldots, Q_k$, mais l'idée est de les trouver en exploitant les conditions initiales (c'est-à-dire les valeurs de $a_0, a_1, \ldots, a_{p-1}$).

Revenons au premier exemple ci-dessus. Nous considérions la suite $(a_n)$ définie par $a_0 = 0$, $a_1 = -1$, $a_2 = 5$ et
$$a_{n+3} = 3a_{n+2} - 4a_n \ \text{ pour } n \geq 0.$$ La première étape est de trouver le polynôme caractéristique. Pour ce faire, on met simplement tous les termes de l'égalité précédente dans le membre de gauche, puis on remplace $a_{n+i}$ par $x^i$ pour tout $i$. On obtient donc le polynôme
$$P(x) = x^3 - 3x^2 + 4.$$ Pour obtenir la formule générale pour $a_n$, il nous faut connaître les racines de $P$. Comme nous l'avons déjà dit précédemment, il n'est pas toujours facile de déterminer les racines d'un polynôme. Si le degré du polynôme (qui est égal à l'ordre de la suite linéaire récurrente) est $2$ alors on peut toujours les trouver. Lorsque le degré est plus élevé, on peut parfois deviner certaines racines et ainsi se ramener à un polynôme de plus petit degré pour déterminer les racines encore inconnues. Ici, on peut par exemple tester les petites valeurs entières et on se rend très vite compte que $-1$ est une racine de $P$. On peut donc le factoriser (par exemple par Horner) et obtenir
$$P(x) = (x+1)(x^2-4x+4).$$ Le polynôme quotient est visiblement un carré parfait, on a donc
$$P(x) = (x+1)(x-2)^2.$$ Les racines de $P$ sont donc $-1$ (de multiplicité $1$) et $2$ (de multiplicité $2$). Le résultat nous apprend donc qu'on a deux polynômes $Q_1$ et $Q_2$ dont les degrés sont strictement inférieurs à $1$ et $2$ respectivement et tels que
$$a_n = Q_1(n) \cdot (-1)^n + Q_2(n) \cdot 2^n.$$ Vu les degrés des polynômes, on peut écrire $Q_1(x) = A$ et $Q_2(x) = Bx + C$ pour $A, B, C \in \mathbb{C}$, et on a ainsi
$$a_n = A \cdot (-1)^n + (Bn + C) \cdot 2^n.$$ Il ne reste alors plus qu'à déterminer les valeurs de $A$, $B$ et $C$. Pour ce faire, on utilise les valeurs de $a_0, a_1$ et $a_2$, qui nous donnent justement trois équations pour trouver trois inconnues :
$$\left\{\begin{align}
0 = a_0 & = A + C \\
-1 = a_1 & = -A+2B+2C \\
5 = a_2 &= A + 8B + 4C
\end{align}\right.$$ En résolvant ce système, on trouve $A = 1, B = 1$ et $C = -1$. On a donc finalement la formule générale
$$a_n = (-1)^n + (n-1) \cdot 2^n.$$ On vérifiera toujours pour éviter les erreurs que les termes suivants ($a_3 = 15, a_4 = 49, \ldots$) vérifient également cette formule. Remarquons qu'il n'aurait pas été facile de deviner cette formule et que cette méthode est dès lors assez puissante, pourvu que l'on sache trouver les racines du polynôme caractéristique relatif à la suite qui nous intéresse.

3. Suite de Fibonacci

Formule générale

Tout le monde connaît la relation de récurrence définissant la suite de Fibonacci :
$$F_{n+2} = F_{n+1} + F_n,$$ mais la formule générale pour $F_n$ est bien moins connue. Au vu du point théorique précédent concernant les suites linéaires récurrentes, et comme il s'agit ici d'une suite linéaire récurrente d'ordre $2$, il est cependant certain qu'une formule existe bel et bien pour $F_n$. Cela peut sembler étrange : si une formule simple existait, alors la suite de Fibonacci semblerait bien moins intéressante ! Voyons ce qu'il en est.

Le polynôme caractéristique associé à la suite de Fibonacci est
$$P(x) = x^2 - x - 1.$$ Le discriminant de ce polynôme est $\Delta = 1^2 -4 \cdot 1 \cdot (-1) = 5$ et les racines de $P$ sont donc
$$\frac{1 + \sqrt{5}}{2} \quad \text{et} \quad \frac{1 - \sqrt{5}}{2}.$$ Les polynômes $Q_1$ et $Q_2$ intervenant dans la méthode doivent donc être de degré $0$, d'où il existe $A, B \in \mathbb{C}$ tels que
$$F_n = A \cdot \left(\frac{1+\sqrt{5}}{2}\right)^n + B \cdot \left(\frac{1-\sqrt{5}}{2}\right)^n.$$ Pour déterminer $A$ et $B$, on utilise $F_0 = 0$ et $F_1 = 1$, ce qui nous donne
$$\left\{\begin{align}
0 = F_0 &= A+B \\[1mm]
1 = F_1 &= A \cdot \left(\frac{1+\sqrt{5}}{2}\right) + B \cdot \left(\frac{1-\sqrt{5}}{2}\right)
\end{align}\right.$$ On a donc $B = -A$ et en substituant dans la deuxième égalité on a
$$\begin{align}
& A \cdot \left(\frac{1+\sqrt{5}}{2}\right) -A \cdot \left(\frac{1-\sqrt{5}}{2}\right) = 1 \\[1mm]
\Leftrightarrow \ & A \cdot \sqrt{5} = 1 \\[1mm]
\Leftrightarrow \ & A = \frac{1}{\sqrt 5}
\end{align}$$ On a donc la formule finale suivante, appelée formule de Binet :

Formule de Binet
$$F_n = \frac{1}{\sqrt 5} \cdot \left(\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right).$$

On comprend mieux pourquoi cette formule est méconnue : elle n'est pas réellement jolie et ne permet donc pas de s'en faire une grande intuition. On peut d'ailleurs regretter l'apparition de $\sqrt{5}$ dans celle-ci : nous savons par définition que $F_n$ sera toujours un nombre entier, mais la formule générale fait pourtant intervenir un nombre irrationnel. Cette formule va cependant nous permettre de trouver certaines propriétés intéressantes de la suite de Fibonacci.

Nombre d'or dans la suite de Fibonacci

Le nombre d'or est généralement défini comme le rapport $\frac{a}{b}$ entre deux longueurs $a > b$ tel que le rapport entre la somme des deux longueurs et la plus grande soit égal au rapport entre la plus grande et la plus petite. Autrement dit, $a$ et $b$ doivent vérifier $a > b$ et
$$\frac{a+b}{a} = \frac{a}{b}.$$ Le nombre d'or est alors simplement $\phi = \frac{a}{b} > 1$, et il est facile de trouver sa valeur puisqu'en remplaçant $a$ par $\phi \cdot b$ dans l'équation précédente on obtient
$$ \begin{align}
& \frac{\phi+1}{\phi} = \phi \\[1mm]
\Leftrightarrow \ & \phi^2 - \phi - 1 = 0
\end{align}$$ Les solutions sont donc les racines du polynôme $P(x) = x^2 - x - 1$ qui est exactement le polynôme caractéristique relatif à la suite de Fibonacci. Nous avions calculé les deux racines, et le nombre d'or est celle d'entre-elle qui est supérieure à $1$ :
$$\phi = \frac{1+\sqrt{5}}{2} \approx 1.618034$$ On peut en fait facilement remarquer que l'autre racine est égale à $-\phi^{-1}$. Ceci nous donne une formule un peu plus compacte pour $F_n$ :

Formule de Binet (avec le nombre d'or)
$$F_n = \frac{1}{\sqrt 5} \left(\phi^n - (-\phi)^{-n}\right).$$

En fait, vu que $\phi > 1$, le terme $(-\phi)^{-n}$ dans cette formule tend très rapidement vers $0$. Cela signifie que pour $n$ assez grand, on a
$$F_n \approx \frac{\phi^n}{\sqrt{5}}.$$ En fait, les premières valeurs de la suite $\displaystyle\left(\frac{\phi^n}{\sqrt{5}}\right)$ sont (arrondies à deux décimales après la virgule) :
$$0.45, 0.72, 1.17, 1.89, 3.07, 4.96, 8.02, 12.98, 21.01, 33.99, 55.00, \ldots$$ ce qui se rapproche ostensiblement des vraies valeurs de $(F_n)$ :
$$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots$$ Une conséquence assez connue de cette constatation est que le quotient de deux nombres de Fibonacci consécutifs tend vers le nombre d'or (plus on va loin dans la suite) :
$$\frac{F_{n+1}}{F_n} \to \phi.$$

4. Périodicité et convergence

Lorsque dans un problème, une certaine suite intervient, il est bon quelque soit la façon dont elle est définie d'explorer ses propriétés éventuelles. Pour ce faire, il est primordial d'écrire (autant que possible) les premiers éléments de la suite pour s'en faire une bonne intuition.

Périodicité

Définition
On dit qu'une suite $(a_n)$ est périodique si il existe un certain $p \in \mathbb{N}_0$ et un certain $N \in \mathbb{N}$ tel qu'on ait
$$a_{n+p} = a_n \ \text{ pour tout } n \geq N.$$ Le plus petit $p$ pour lequel un tel $N$ existe est appelé la période de la suite.

Remarquer qu'une suite est périodique est très intéressant puisqu'on peut alors connaître précisément tous les éléments de la suite.

Intéressons-nous par exemple à la suite $(c_n)$ définie par $c_0 = 0$ et, pour $n \geq 1$, $c_n = 1+d$ où $d$ est le dernier chiffre de $c_0 + c_1 + \ldots + c_{n-1}$. La première chose à faire est bien sûr de regarder les premiers termes de cette suite. Ceux-ci sont
$$0, 1, 2, 4, 8, 6, 2, 4, 8, 6, 2, \ldots$$ Il semblerait que la suite soit périodique de période $4$, puisque les quatre éléments $2, 4, 8, 6$ semblent se répéter continuellement. La deuxième étape est alors de le prouver. Dans notre exemple, on peut le montrer par récurrence. Supposons que les éléments $2, 4, 8, 6$ se répètent en permanence à partir de $c_2$ et jusque $c_n$ (ce qui est le cas pour $n = 10$ au vu du calcul des premiers éléments) et montrons qu'on a alors $c_{n+1} = c_{n-3}$, ce qui suffira. Par définition, on sait que
$$c_{n+1} = 1 + d,$$ où $d$ est le dernier chiffre de $c_0 + c_1 + \ldots + c_n$. Mais on sait aussi que les chiffres $2, 4, 8, 6$ se répètent jusque $c_n$, ce qui signifie que les quatre nombres $c_n, c_{n-1}, c_{n-2}$ et $c_{n-3}$ sont exactement $2, 4, 6$ et $8$ (dans un autre ordre), d'où
$$c_n + c_{n-1} + c_{n-2} + c_{n-3} = 2+4+6+8=20.$$ On en déduit que $d$ est également le dernier chiffre de $c_0 + c_1 + \dots + c_{n-4}$, ce qui signifie qu'il s'agit du même chiffre que celui intervenant dans la définition de $c_{n-3}$. On a donc $c_{n+1} = c_{n-3}$ comme voulu, et la suite est bel et bien périodique de période $4$.

Convergence

Définition
On dit qu'une suite $(a_n)$ de nombres complexes tend (ou converge) vers $a \in \mathbb{C}$ si la suite $|a_n - a|$ est de plus en plus proche de $0$. De manière plus rigoureuse, on demande que pour tout $\varepsilon > 0$, il existe un certain $N \in \mathbb{N}_0$ tel que
$$|a_n - a| < \varepsilon \ \text{ pour tout } n \geq N.$$ On écrit alors $a_n \to a$.

Nous avons déjà vu un exemple sans le montrer rigoureusement, puisqu'on a dit que la suite de Fibonacci était telle que
$$\frac{F_{n+1}}{F_n} \to \phi.$$ Cette définition peut sembler surtout utile pour une suite de nombres réels (non entiers), mais elle a aussi un sens lorsqu'on s'intéresse à une suite de nombres entiers. Dans un tel cas, une suite $(a_n)$ tend vers $a$ s'il existe un certain $N \in \mathbb{N}$ tel que
$$a_n = a \ \text{ pour tout } n \geq N,$$ c'est-à-dire si elle finit par être constamment égale à $a$.

Regardons cette-fois la suite $(a_n)_{n \in \mathbb{N}_0}$ définie par $a_n = $ nombre de puissances $n$-èmes parfaites positives ayant exactement $n$ chiffres et contenant le dernier chiffre de $n$, dont les premiers éléments sont
$$1, 1, 1, 2, 1, \ldots$$ Lorsqu'on calcule les premiers termes de la suite (ce qui n'est cette fois-ci pas totalement évident), on se rend vite compte qu'il y a de moins en moins de puissances $n$-èmes parfaites ayant exactement $n$ chiffres lorsque $n$ grandit (même sans la condition sur le dernier chiffre de $n$). Cela vient du fait que de telles puissances sont forcément de la forme $t^n$ avec $t < 10$ (car $10^n$ contient déjà $n+1$ chiffres). Mais $t$ ne doit pas non plus être trop petit puisqu'alors $t^n$ ne contient pas assez de chiffres. Par exemple, pour $n = 3$ on doit avoir $t \geq 5$ et pour $n = 5$, $t \geq 7$. On pourrait donc logiquement penser qu'il y aura même un moment où plus aucune puissance $n$-ème parfaite n'aura exactement $n$ chiffres ! Cela arrivera si
$$9^n < 10^{n-1},$$ ce que l'on peut réécrire
$$\left(\frac{9}{10}\right)^n < \frac{1}{10}.$$ Or, cette dernière inégalité devient toujours clairement vraie à partir d'un certain $N$. Nous venons donc montrer que la suite $(a_n)$ tend vers $0$, puisqu'elle devient constamment égale à $0$ pour les $n \geq N$.