Sauter au contenu

Mathématiques discrètes Version préliminaire

Section 6.1 Relations de récurrence linéaires homogènes

Dans plusieurs branches des mathématiques, on étudie des objets placés un à la suite de l’autre selon une règle particulière. On peut penser à la suite des entiers positifs pairs \(2,4,6,8,\dots,\) la suite des nombres premiers \(2,3,5,7,11,\dots\) et la suite de Fibbonacci \(1,1,2,3,5,8,13,\dots.\) Dans le cours, nous allons principalement considérer des suites qui seront définies par récurrence.
🔗
Tout d’abord, on donne la définition formelle d’une suite. Par la suite, on considère les suites définies par récurrence. Finalement, on montre comment trouver le terme général des suites satisfaisant une relation de récurrence linéaire homogène.
🔗

Sous-section 6.1.1 Suites et relations de récurrence

Définition 6.1.1.

Une suite est une fonction partant d’un sous-ensemble des entiers (souvent \(\{0,1,2,\dots\}\) ou \(\{1,2,\dots\}\)) vers un ensemble \(S\) quelconque. On utilise la notation \(a_n\) pour représenter l’image de \(n\) par la fonction. On appelle \(a_n\) un terme de la suite. On utilisera la notation \(\{a_n\}\) pour représenter la suite elle-même.
🔗
🔗

Exemple 6.1.2. Une suite qui tend vers 0.

On considère la suite \(\{a_n\}\) où \(a_n=\frac{1}{n}\text{.}\)
🔗
Ainsi, si on écrit les premiers termes de la suite, c’est-à-dire \(a_1,a_2,a_3,a_4,\dots\) on a \(1,\frac{1}{2},\frac{1}{3},\frac{1}{4},\dots\text{.}\)
🔗
🔗
Nous allons maintenant considérer des suites qui seront définies par récurrence. On commence par considérer quelques exemples avant de donner la définition formelle.
🔗

Exemple 6.1.3. Des suites définies par récurrence.

(a)
Soit \(\{a_n\}\) la suite satisfaisant la relation de récurrence \(a_n=a_{n-1}+4\) pour \(n=1,2,3,\dots,\) telle que \(a_0=3.\) Quels sont les termes \(a_1,a_2\) et \(a_3\text{?}\)
🔗
Solution.
On a que \(a_1=a_0+3=3+4=7\text{.}\) Puisqu’on vient de déterminer \(a_1\text{,}\) on peut maintenant obtenir \(a_2=a_1+4=7+4=11.\) Finalement, on a \(a_3=a_2+4=11+4=15\text{.}\)
🔗
🔗
🔗
(b)
Soit \(\{a_n\}\) la suite satisfaisant la relation de récurrence \(a_n=a_{n-1}-a_{n-2}\) pour \(n=2,3,4,\dots,\) telle que \(a_0=2\) et \(a_1=6.\) Quels sont les termes \(a_2,a_3\) et \(a_4\text{?}\)
🔗
Solution.
On a que \(a_2=a_1 - a_0=6-2=4\text{.}\) Ainsi, on peut maintenant obtenir \(a_3=a_2-a_1=4-6=-2.\) Finalement, on a \(a_4=a_3-a_2=-2-4=-6\text{.}\)
🔗
🔗
🔗
🔗

Définition 6.1.4.

Une relation de récurrence pour une suite \(\{a_n\}\) est une expression du terme \(a_n\) en fonction d’un ou plusieurs des termes précédents de la suite, et ce, pour \(n\geq n_0 \in\, \N.\) On dira aussi que la suite \(\{a_n\}\) est une solution à la relation de récurrence.
🔗
🔗

Exemple 6.1.5. La suite de Fibonacci.

Soit \(\{a_n\}\) la suite satisfaisant la relation de récurrence \(a_n=a_{n-1}+a_{n-2}\) pour \(n=2,3,4,\dots,\) telle que \(a_0=1\) et \(a_1=1.\) On appelle cette suite la suite de Fibonacci. Quels sont les termes \(a_2,a_3,a_4,a_5\) et \(a_6\text{?}\)
🔗
Solution.
\(a_2=2,a_3=3,a_4=5,a_5=8\)\(a_6=13\text{.}\)
🔗
🔗

Exemple 6.1.6. La factorielle.

On considère la suite \(\{a_n\}\) telle que \(a_n=n\cdot a_{n-1}\) pour \(n=1,2,3,\dots\) et \(a_0=1\text{.}\) Quelle est la valeur de \(a_n\text{?}\)
🔗
Réponse.
\(a_n=n!\)
🔗
🔗
Il est possible d’utiliser les relations de récurrence afin traiter des problèmes de dénombrement qui seraient très difficiles à résoudre à l’aide des techniques vues précédemment. On donne deux exemples ici, et on explorera d’autres exemples dans les prochaines sections.
🔗

Exemple 6.1.7. Dénombrement avec relation de récurrence: Chaînes binaires.

On note \(S_n\) le nombre de chaînes binaires de longueur \(n\) qui n’ont pas deux \(0\) consécutifs. Il est difficile de déterminer \(S_n\) directement, mais on peut tout de même trouver une relation de récurrence et des conditions initiales pour \(S_n\text{.}\)
🔗
Solution.
Tout d’abord, on remarque que pour \(n=1\text{,}\) les deux seules chaînes binaires de longueur \(1\) ne peuvent pas contenir deux \(0\) consécutifs. Ainsi, \(S_1=2\text{.}\)
🔗
Ensuite, si \(n=2,\) alors il y a une unique chaîne binaire contenant deux \(0\) consécutifs. Ainsi, \(S_2=4-1=3\text{.}\)
🔗
Supposons maintenant que \(n\geq 3\text{.}\) On note \(S_{n,1}\) le nombre de chaînes binaires de longueur \(n\) n’ayant pas deux \(0\) consécutifs et se terminant par un \(1.\) De même, on note \(S_{n,0}\) le nombre de chaînes binaires de longueur \(n\) n’ayant pas deux \(0\) consécutifs et se terminant par un \(0.\) Par le principe de la somme, on a \(S_n=S_{n,1}+S_{n,0}\)
🔗
On remarque que toute chaîne de longueur \(n\) n’ayant pas deux \(0\) consécutifs et se terminant par un \(1\) est formé d’une chaîne de longueur \(n-1\) n’ayant pas deux \(0\) consécutifs. Ainsi, \(S_{n,1}=S_{n-1}\text{.}\)
🔗
D’un autre côté, si on considère une chaîne binaire de longueur \(n\) n’ayant pas deux \(0\) consécutifs et se terminant par un \(0,\) alors cette chaîne doit en fait se terminer par \(10,\) car sinon elle aurait deux \(0\) consécutifs. Ainsi, toute chaîne de longueur \(n\) n’ayant pas deux \(0\) consécutifs et se terminant par un \(10\) est formé d’une chaîne de longueur \(n-2\) n’ayant pas deux \(0\) consécutifs. On a donc \(S_{n,0}=S_{n-2}\text{.}\)
🔗
Par ce qui précède, on a \(S_n=S_{n-1}+S_{n-2},\) avec \(S_1=2\) et \(S_2=3\text{.}\)
🔗
Pour le moment, il est encore difficile de déterminer \(S_n\text{,}\) mais nous allons introduire les outils permettant de résoudre ce genre de problème.
🔗
🔗
🔗

Exemple 6.1.8. Dénombrement avec relation de récurrence: Fonctions surjectives.

Soit \(A\) un ensemble de cardinalité \(n\) et \(B=\{1,2,\dots,k\}\) avec \(n\geq k\text{.}\) On note \(C(n,k)\) le nombre de fonctions surjectives \(f:A\to B\text{.}\) Trouvons une relation de récurrence pour \(C(n,k)\)
Réponse.
\(C(n,k)=k\left(C(n-1,k)+C(n-1,k-1)\right)\)
🔗
🔗
Solution.
On commence par considérer un élément particulier \(a\in\,A\) et on choisit la valeur de \(f(a)\text{.}\) Il y a \(k\) choix possible. Notons \(f(a)=b\in\,B.\) Il reste alors uniquement à déterminer les valeurs de \(f\) sur \(A-\{a\}\text{.}\)
🔗
Par la suite, on sépare la situation en deux cas. Soit \(a\) est la seule préimage de \(b\text{,}\) soit il y a au moins une autre préimage pour \(b\text{.}\)
🔗
Dans le premier cas, la restriction de \(f\) sur \(A-\{a\}\) est une fonction surjective vers l’ensemble \(B-\{b\}\text{.}\) Il y aura donc \(C(n-1,k-1)\) choix possibles.
🔗
Dans le deuxième cas, la restriction de \(f\) sur \(A-\{a\}\) est une fonction surjective vers l’ensemble \(B\text{.}\) Il y aura donc \(C(n-1,k)\) choix possibles.
🔗
Ainsi, par le principe du produit et de la somme, on a \(C(n,k)=k\left(C(n-1,k)+C(n-1,k-1)\right)\text{.}\)
🔗
🔗
🔗
🔗

Sous-section 6.1.2 Relations de récurrence et forme générale

Dans les exemples précédents, nous avons observé qu’il est souvent plus facile de trouver une relation de récurrence pour une suite \(\{a_n\}\) que de trouver sa forme générale. On peut extraire certaines informations sur ces suites à l’aide de la relation de récurrence (limite de la suite, croissance/décroissance, bornes, etc.).
🔗
Cependant, il est souvent très long (même pour un ordinateur) de déterminer le \(n^{\text{ième}}\) terme d’une suite \(\{a_n\}\) lorsque \(n\) est assez grand. Heureusement, on peut utiliser la relation de récurrence afin de nous aider à trouver la forme générale.
🔗
Nous allons montrer quelques exemples pour lesquels on peut facilement trouver le terme général d’une suite à partir de la relation de récurrence. Par la suite, on étudiera une classe particulière de relations de récurrence pour lesquelles on connaît la forme générale. Il s’agit des relations de récurrence linéaires homogènes (à coefficients constants). On étudiera en particulier celles d’ordre \(2\text{.}\)
🔗

Exemple 6.1.9. Forme générale d’une relation de récurrence.

On considère la suite \(\{a_n\}\) telle que \(a_n=a_{n-1} +3\) pour \(n\geq 1\) et \(a_0=4\text{.}\) Quelle est la forme générale de \(a_n\text{?}\)
🔗
Réponse.
\(a_n=4+3n\text{.}\)
🔗
Solution.
On calcule \(a_n\) pour les premières valeurs de \(n,\) mais en essayant de ne pas trop simplifier l’expression. On a
\begin{align*} a_1\amp=a_0+3=4+3\\ a_2\amp=a_1+3=(4+3)+3=4+3(2)\\ a_3\amp=a_2+3=(4+3(2))+3=4+3(3)\\ a_4\amp=a_3+3=(4+3(3))+3=4+3(4)\\ \amp\vdots\\ a_n\amp=a_{n-1}+3=(4+3(n-1))+3=4+3(n). \end{align*}
🔗
🔗
🔗

Exemple 6.1.10. Forme générale d’une relation de récurrence: une deuxième stratégie.

On considère la suite \(\{a_n\}\) telle que \(a_n=(1,11)a_{n-1} \) pour \(n\geq 1\) et \(a_0=100\text{.}\) Quelle est la forme générale de \(a_n\text{?}\)
🔗
Réponse.
\(a_n=100(1,11)^n\text{.}\)
🔗
Solution.
On écrit \(a_n\) en fonction de \(a_{n-1}\text{,}\) c’est-à-dire \(a_n=1,11\cdot a_{n-1}\text{.}\) Par la suite, on développe \(a_{n-1}\) en fonction de \(a_{n-2}\text{.}\) Ici, en remplaçant \(n\) par \(n-1\) dans la relation de récurrence, on a \(a_{n-1}=(1,11)a_{n-2}\text{.}\) On poursuit de cette manière jusqu’à obtenir une expression de \(a_n\) qui dépend uniquement de \(a_0\text{.}\)
\begin{align*} a_n\amp=(1,11)a_{n-1}\\ \amp=(1,11)(1,11)a_{n-2}=(1,11)^2 a_{n-2}\\ \amp=(1,11)^2(1,11)a_{n-3}=(1,11)^3 a_{n-3}\\ \amp=(1,11)^3(1,11)a_{n-4}=(1,11)^4 a_{n-4}\\ \amp\vdots\\ \amp=(1,11)^{n-1}(1,11)a_{0}=(1,11)^n a_{0}=100(1,11)^n \end{align*}
🔗
🔗
🔗
Les deux exemples précédents sont des exemples de relations de récurrence linéaire ( non-homogène pour 6.1.9, et homogène pour 6.1.10). On regarde un dernier exemple, qui sera un peu plus complexe que les précédents.
🔗
Le reste de la section sera dédiée à l’étude des relations de récurrence linéaire homogène, et on gardera en tête la forme de la solution de l’exemple 6.1.10 afin de trouver la forme générale pour ce genre de relations. On étudiera les relations non-homogène dans la prochaine section.
🔗

Exemple 6.1.11.

On considère la suite \(\{a_n\}\) telle que \(a_n=-a_{n-1}a_{n-2} \) pour \(n\geq 2,\) \(a_0=1\) et \(a_1=-1\text{.}\) Quelle est la forme générale de \(a_n\text{?}\)
Réponse.
\(a_n=(-1)^{r_n},\) où \(r_n= n \mod 3\) est le reste de la division de \(n\) par \(3\text{.}\)
🔗
🔗
Solution.
On calcule \(a_n\) pour quelques valeurs de \(n\text{.}\)
\begin{align*} a_2\amp=-a_1a_{0}=-(1)(-1)=1\\ a_3\amp=-a_2a_{1}=-(-1)(1)=1\\ a_4\amp=-a_3a_{2}=-(1)(1)=-1\\ a_5\amp=-a_4a_{3}=-(-1)(1)=1\\ a_6\amp=-a_5a_{4}=-(1)(-1)=1\\ a_7\amp=-a_6a_{5}=-(1)(1)=-1\\ a_8\amp=-a_7a_{6}=-(-1)(1)=1\\ a_9\amp=-a_8a_{7}=-(1)(-1)=1\\ \amp\vdots \end{align*}
Ici, il faut réfléchir un peu plus pour trouver la forme générale en raison du comportement du signe de \(a_n,\) mais on peut se convaincre que \(a_n=(-1)^{r_n},\) où \(r_n= n \mod 3\) est le reste de la division de \(n\) par \(3\text{.}\)
🔗
🔗
🔗
🔗

Sous-section 6.1.3 Relations de récurrence linéaires homogènes

Tel que mentionné, la plupart des relations de récurrence sont difficiles à résoudre. Nous donnons ici les définitions pour certaines de ces relations pour lesquelles on connaît la solution.
🔗

Définition 6.1.12.

Une relation de récurrence linéaire homogène (à coefficient constant) est une relation de la forme:
\begin{equation*} a_n = c_1a_{n-1}+c_{2}a_{n-2}+\cdots + c_ka_{n-k} \end{equation*}
où les \(c_i\) sont des constantes réelles, et \(c_{n-k}\neq 0.\) On dira que cette relation est d’ordre \(k\text{.}\)
🔗

Exemple 6.1.13.

Les relations de récurrence suivantes sont linéaires homogènes
\begin{align*} a_n\amp= a_{n-1}+a_{n-2} \amp\amp \text{ (d'ordre 2)}\\ a_n\amp= (1,11)a_{n-1} \amp\amp\text{ (d'ordre 1)}\\ a_{n+1}\amp= 2a_{n} + 4a_{n-1}+a_{n-3}+a_{n-5}+3a_{n-6} \amp\amp\text{ (d'ordre 7)} \end{align*}
🔗
Voici quelques exemples de relations qui ne sont pas linéaires homogènes (ou n’ont pas des coefficients constants).
🔗

Exemple 6.1.14.

Les relations suivantes ne sont pas linéaires homogènes.
\begin{align*} a_n \amp= a_{n-1}a_{n-2} \text{, elle n'est pas linéaire;} \\ a_n \amp= a_{n-1}+a_{n-2}+5 \text{, elle n'est pas homogène.} \end{align*}
🔗
La relation suivante est linéaire homogène, mais n’est pas à coefficients constants.
\begin{equation*} a_{n}=na_{n-1}+\cos\left(\frac{n\pi}{2}\right)a_{n-2}\text{.} \end{equation*}
🔗
🔗
Le cas le plus simple d’une relation de récurrence linéaire homogène à coefficients constants est celle d’ordre \(1\text{.}\) Elles sont toutes de la forme \(a_n=ka_{n-1}\text{.}\) En appliquant la substitution répétée, on peut trouver la solution
\begin{equation*} a_n=k^n a_0\text{.} \end{equation*}
Le cas d’ordre \(2\) demandera un peu plus d’analyse.
🔗
🔗

Sous-section 6.1.4 Solutions aux équations de récurrence linéaires homogènes d’ordre 2: Cas 1

On a déjà remarqué que, pour une relation de récurrence donnée, il peut y avoir plusieurs suites qui la satisfont. Si on connaît également quelques termes (disons \(a_0,a_1,\dots ,a_k\)) alors la solution devient alors unique.
🔗
On veut trouver la forme générale des solutions pour une relation de récurrence linéaire homogène d’ordre \(2,\) c’est-à-dire une relation de la forme \(a_n=c_1a_{n-1}+c_2a_{n-2}\text{.}\) On s’inspire de l’exemple 6.1.10.
🔗

Exemple 6.1.15. Une première solution à une relation de récurrence linéaire homogène d’ordre 2.

Soit la relation \(a_n=c_1a_{n-1}+c_2a_{n-2}\text{,}\) est-ce possible que la suite au terme général \(a_n=r^n\) soit une solution à cette relation? Si oui, sous quelle(s) condition(s)?
Solution.
On suppose que \(a_n=r_1^n\) est une solution à la relation de récurrence, où \(r_1\neq 0.\) Ici, on rejette le cas \(r_1=0,\) car il s’agit de la solution triviale. En particulier, on a \(a_{n-1}=r_1^{n-1}\) et \(a_{n-2}=r_1^{n-2}\text{.}\) Ainsi, en remplaçant dans l’équation, on a
\begin{align*} r_1^n\amp=c_1r_1^{n-1}+ c_2r_1^{n-2} \\ 0\amp=r_1^n-c_1r_1^{n-1} -c_2r_1^{n-2} = r_1^{n-2}\left(r_1^2-c_1r_1-c_2 \right)\\ 0\amp=r_1^2-c_1r_1-c_2 \text{ car } r_1\neq 0. \end{align*}
Ainsi, on a que si \(r_1\) est une racine du polynôme \(r^2-c_1r-c_2\text{,}\) alors \(a_n= r_1^n\) est effectivement une solution à la relation de récurrence.
🔗
🔗
🔗

Définition 6.1.16. Équation caractéristique.

Soit \(a_n=c_1a_{n-1}+c_2a_{n-2}\) une relation de récurrence, l’équation caractéristique associée à cette relation est l’équation
\begin{equation*} 0=r^2-c_1r-c_2 \end{equation*}
🔗
🔗
Puisque l’équation caractéristique d’une relation de récurrence linéaire d’Ordre 2 est un polynôme d’ordre 2, on risque donc d’obtenir deux solutions différentes à l’aide de l’équation caractéristique. Peut-on en obtenir davantage?
🔗

Exemple 6.1.17. L’équation caractéristique: Un premier cas.

On considère la relation de récurrence \(a_n=a_{n-1}+2a_{n-2}.\) Trouvons (si elles existent) les deux solutions \(r_1\) et \(r_2\) à son équation caractéristique. Vérifions également que la suite \(a_n=3r_1^n+4r_2^n\) satisfait la relation de récurrence.
🔗
Solution.
L’équation caractéristique est obtenue en remplaçant \(a_n\) par \(r^n\text{.}\) On a alors \(0=r^2-r-2=(r-2)(r+1)\text{.}\)
🔗
Ainsi, les deux solutions à cette équation sont \(r_1=2\) et \(r_2=-1.\) En particulier, on a que
\begin{align*} r_1^{n}\amp=r_1^{n-1} +2r_1^{n-2}\\ r_2^{n}\amp=r_2^{n-1} +2r_2^{n-2} \end{align*}
🔗
Pour vérifier que \(a_n=3r_1^n+4r_2^n\) satisfait la relation de récurrence, on doit vérifier que \(a_n=a_{n-1}+2a_{n-2}\text{.}\)
🔗
D’un côté, on a que \(a_n=3r_1^n+4r_2^n\) (c’est ce qu’on a supposé)
🔗
De l’autre côté, on a que
\begin{align*} a_{n-1}+2a_{n-2}\amp= (3r_1^{n-1}+4r_2^{n-1})+2(3r_1^{n-2}+4r_2^{n-2})\\ \amp= (3r_1^{n-1}+3\cdot 2r_1^{n-2})+(4r_2^{n-1}+4\cdot 2r_2^{n-2})\\ \amp= 3(r_1^{n-1}+ 2r_1^{n-2})+4(r_2^{n-1}+ 2r_2^{n-2})\\ \amp= 3r_1^n+4r_2^{n}=a_n \end{align*}
Ainsi, on a bien que \(a_n=3r_1^n+4r_2^n\) satisfait à la relation de récurrence.
🔗
🔗
🔗
En relisant la solution à l’exemple précédent, on constate que les valeurs des constantes devant les \(r_i\) n’ont pas affecté nos démarches. La seule chose qu’on a utilisée, c’est le fait que les \(r_i\) sont des solutions à l’équation caractéristique.
🔗
En fait, on peut même montrer que toutes les solutions seront de cette forme.
🔗

Exemple 6.1.19. Une première solution.

Trouver la suite \(\{a_n\}\) telle que \(a_n=a_{n-1}+2a_{n-2},\) sachant que \(a_0=5\) et \(a_1=11\text{.}\)
🔗
Réponse.
\(a_n=\frac{16}{3}(2)^n+\frac{-1}{3}(-1)^n\)
🔗
Solution.
À l’exemple 6.1.17, on a déjà montré que l’équation caractéristique de cette relation possède \(r_1=2\) et \(r_2=(-1)\) comme solution.
🔗
Par la proposition 6.1.18, on sait que la solution devra avoir la forme
\begin{equation} a_n=\alpha_1r_1^n+\alpha_2r_2^n=\alpha_1(2)^n+\alpha_2(-1)^n\text{.}\tag{6.1.1} \end{equation}
🔗
Ainsi, puisque \(a_0=5\) et \(a_1=11,\) en remplaçant \(n\) par \(0\) et \(1\) dans (6.1.1), on obtient un système d’équations suivant.
\begin{align*} 5\amp= \alpha_1 (2)^0+\alpha_2(-1)^0=\alpha_1+\alpha_2;\\ 11\amp= \alpha_1 (2)^1+\alpha_2(-1)^1=2\alpha_1-\alpha_2. \end{align*}
En résolvant ce système d’équations, on a que \(\alpha_1=\frac{16}{3}\) et \(\alpha_2=\frac{-1}{3}\text{.}\)
🔗
Ainsi, on a que la suite \(\{a_n\}\) est la suite dont le terme général est \(a_n=\frac{16}{3}(2)^n+\frac{-1}{3}(-1)^n\text{.}\)
🔗
🔗
🔗

Exemple 6.1.20. Une deuxième solution.

Trouver la suite \(\{a_n\}\) telle que \(a_n=5a_{n-1}-6a_{n-2},\) sachant que \(a_0=1\) et \(a_1=0\text{.}\)
🔗
Réponse.
\(a_n=3(2)^n-2(3)^n\)
🔗
Solution.
L’équation caractéristique de cette relation est \(0=r^2-5r+6=(r-2)(r-3).\) Ainsi, on pose \(r_1=2\) et \(r_2=3\) les deux solutions à cette équation.
🔗
Par la proposition 6.1.18, on sait que la solution devra avoir la forme
\begin{equation} a_n=\alpha_1r_1^n+\alpha_2r_2^n=\alpha_1(2)^n+\alpha_2(3)^n\text{.}\tag{6.1.2} \end{equation}
🔗
Ainsi, puisque \(a_0=1\) et \(a_1=0,\) en remplaçant \(n\) par \(0\) et \(1\) dans (6.1.2), on obtient le système d’équations suivant.
\begin{align*} 1\amp=\alpha_1+\alpha_2;\\ 0\amp= 2\alpha_1 +3\alpha_2. \end{align*}
En résolvant ce système d’équations, on a que \(\alpha_1=3\) et \(\alpha_2=-2\text{.}\)
🔗
Ainsi, on a que la suite \(\{a_n\}\) est la suite dont le terme général est \(a_n=3(2)^n-2(3)^n\text{.}\)
🔗
🔗
🔗
🔗

Sous-section 6.1.5 Solutions aux équations de récurrence linéaires homogènes d’ordre 2: Cas 2

Jusqu’à maintenant, les équations caractéristiques que l’on a rencontrées avaient des solutions distinctes. Nous allons maintenant regarder le cas où il y a une seule solution.
🔗

Exemple 6.1.21. Équations caractéristiques à une seule racine.

Trouver l’unique racine \(r_1\) à l’Équation caractéristique de la relation de récurrence \(a_n=6a_{n-1}-9a_{n-2}\)
🔗
Vérifier que si \(a_n=nr_1^n,\) alors la suite \(\{a_n\}\) satisfait à la relation de récurrence.
🔗
Solution.
L’équation caractéristique est donnée par \(0=r^2-6r+9=(r-3)^2.\) Ainsi, l’unique solution à cette équation est \(r_1=3.\) Par définition, on a alors que
\begin{equation} r_1^{n}=6r_1^{n-1} -9 r_1^{n-2}.\tag{6.1.3} \end{equation}
On peut le vérifier en remplaçant \(r_1\) par \(3,\) c’est-à-dire en vérifiant que
\begin{equation} 3^{n}=6(3)^{n-1} -9 (3)^{n-2}.\tag{6.1.4} \end{equation}
🔗
Pour vérifier que \(a_n=n(3)^n\) satisfait à la relation de récurrence, on doit vérifier que \(n3^n=6(n-1)3^{n-1}-9(n-2)3^{n-2}\text{.}\)
🔗
Or, on a que
\begin{align*} 6(n-1)3^{n-1}-9(n-2)3^{n-2}\amp= 6n(3)^{n-1}-6(3)^{n-1}-9n(3)^{n-2} +2\cdot 9(3)^{n-2} \\ \amp= \left(6n(3)^{n-1}-9n(3)^{n-2}\right)+ \left( -6(3)^{n-1} +2\cdot 9(3)^{n-2} \right)\\ \amp= n\left(6(3)^{n-1}-9(3)^{n-2}\right)+ \left( -6\cdot 3(3)^{n-2} +2\cdot 9(3)^{n-2} \right)\\ \amp= n\left(3^n\right)+ \left( 0 \right) \text{ par } \knowl{./knowl/xref/eq-caract.html}{\text{(6.1.4)}} \\ \amp= n3^n=a_n. \end{align*}
🔗
🔗
🔗
On a une nouvelle version de la proposition 6.1.18 dans le cas où l’équation caractéristique ne possède qu’une seule racine.
🔗

Exemple 6.1.23. Une première solution.

Trouver la suite \(\{a_n\}\) telle que \(a_n=6a_{n-1}-9a_{n-2},\) sachant que \(a_0=2\) et \(a_1=15\text{.}\)
Réponse.
\(a_n=2(3)^n+3n(3)^n\text{.}\)
🔗
Solution.
À l’exemple 6.1.21, on a déjà montré que l’équation caractéristique de cette relation possède l’unique solution \(r_1=3\text{.}\)
🔗
Par la proposition 6.1.22, on sait que la solution devra avoir la forme
\begin{equation} a_n=\alpha_1r_1^n+\alpha_2nr_1^n=\alpha_1(3)^n+\alpha_2 n(3)^n\text{.}\tag{6.1.5} \end{equation}
🔗
Ainsi, puisque \(a_0=2\) et \(a_1=15,\) en remplaçant \(n\) par \(0\) et \(1\) dans (6.1.5), on obtient le système d’équations suivant.
\begin{align*} 2\amp= \alpha_1(3)^0 +\alpha_2(0)(3)^0=\alpha_1;\\ 15\amp= \alpha_1 (3)^1+\alpha_2(1)(3)^1=3\alpha_1+3\alpha_2. \end{align*}
En résolvant ce système d’équations, on a que \(\alpha_1=2\) et \(\alpha_2=3\text{.}\)
🔗
Ainsi, on a que la suite \(\{a_n\}\) est la suite dont le terme général est \(a_n=2(3)^n+3n(3)^n\text{.}\)
🔗
🔗
🔗

Exemple 6.1.24. Une deuxième solution.

Trouver la suite \(\{a_n\}\) telle que \(a_n=4a_{n-1}-4a_{n-2},\) sachant que \(a_0=0\) et \(a_1=-12\text{.}\)
Réponse.
🔗
Solution.
L’équation caractéristique de cette relation de récurrence est \(0=r^2-4r+4=(r-2)^2.\) L’unique solution à cette équation est \(r_1=2\text{.}\)
🔗
Par la proposition 6.1.22, on sait que la solution devra avoir la forme
\begin{equation} a_n=\alpha_1r_1^n+\alpha_2nr_1^n=\alpha_1(2)^n+\alpha_2 n(2)^n\text{.}\tag{6.1.6} \end{equation}
🔗
Ainsi, puisque \(a_0=0\) et \(a_1=-12,\) en remplaçant \(n\) par \(0\) et \(1\) dans (6.1.6), on obtient un système d’équations suivant.
\begin{align*} 0\amp =\alpha_1;\\ -12\amp=2\alpha_1+2\alpha_2. \end{align*}
En résolvant ce système d’équations, on a que \(\alpha_1=0\) et \(\alpha_2=-6\text{.}\)
🔗
Ainsi, on a que la suite \(\{a_n\}\) est la suite dont le terme général est \(a_n=-6n(2)^n\text{.}\)
🔗
🔗
🔗
🔗

Sous-section 6.1.6 Relations de récurrence linéaires homogènes d’ordre \(k\)

Pour le moment, nous avons étudié les relations linéaires d’ordre \(2,\) mais le traitement effectué peut se faire pour des relations d’ordre \(k\) quelconque. Par exemple, on peut facilement trouver les solutions générales pour des relations d’ordre \(1\) (voir exemple 6.1.10).
🔗
En théorie, la situation n’est pas bien plus compliquée si \(k\geq 3.\) Cependant, il faudra résoudre une équation polynomiale de degré \(k,\) ce qui peut-être très difficile! De plus, pour trouver la solution respectant les conditions initiales, il faut résoudre un système de \(k\) équations à \(k\) inconnues. Ceci n’est pas trop difficile, mais requiert des méthodes que vous verrez dans le cours d’algèbre linéaire.
🔗
On donne ici la généralisation des méthodes pour des relations d’ordre \(k\text{.}\)
🔗

Définition 6.1.25. Équation caractéristique.

Soit
\begin{equation} a_n=c_1a_{n-1}+c_2a_{n-2}+ \cdots +c_ka_{n-k}\tag{6.1.7} \end{equation}
une relation de récurrence d’ordre \(k\) (c’est-à-dire que \(c_k\neq 0\)), l’équation caractéristique associée à cette relation est l’équation
\begin{equation} 0=r^k-c_1r^{k-1}-c_2r^{k-2}-\cdots - c_{k-1}r-c_k \tag{6.1.8} \end{equation}
🔗
🔗
On obtient cette équation en remplaçant \(a_n\) par \(r^n\) dans la relation de récurrence. On voir alors que la suite \(\{a_n\}\) de terme général \(a_n=r_1^n\) satisfait la relation de récurrence (6.1.7) si et seulement si \(r_1\) est une solution à l’équation caractéristique (6.1.8). Si l’équation caractéristique possède \(k\) racines distinctes, on à la proposition suivante.
🔗
🔗

Questions de compréhension de la lecture 6.1.7 Questions de compréhension de la lecture

Ces questions sont à faire avant de venir en classe et à remettre au début du cours.
🔗

1.

Déterminer \(a_2,\,a_3\) et \(a_4\) si:
🔗
(a)
\(a_n=\sin\left(\frac{\pi}{2}+\pi\cdot a_{n-1}\right)a_{n-2}\) pour \(n=2,\,3,\,4,\dots,\) sachant que \(a_0=1\) et \(a_1=-1\)
🔗
🔗
(b)
\(a_n=2a_{n-1}+5a_{n-2}\) pour \(n=2,\,3,\,4,\dots,\) sachant que \(a_0=2\) et \(a_1=3\)
🔗
🔗
(c)
\(a_n=n^2a_{n-1}+na_{n-2}\) pour \(n=2,\,3,\,4,\dots,\) sachant que \(a_0=1\) et \(a_1=-1\)
🔗
🔗
🔗

2.

Pour chacune des relations de récurrences ci-dessous, déterminer l’équation caractéristique et trouver les racines de celle-ci.
🔗
🔗

3.

Pour chacune des relations de récurrences ci-dessous, trouver la solution générale respectant les conditions initiales données.
🔗
(a)
\(a_n=2a_{n-1}+3a_{n-2}\text{,}\) où \(a_0=3\) et \(a_1=5\text{.}\)
🔗
🔗
(b)
\(a_n=10a_{n-1}-25a_{n-2}\text{,}\) où \(a_0=1\) et \(a_1=4\text{.}\)
🔗
🔗
🔗

4.

Noter toute question qui demeure suite à la lecture de la section et la résolution des exercices ci-dessus ou toute précision/clarification à apporter. Note: cette question est facultative.
🔗
🔗
🔗

Exercices 6.1.8 Exercices

À faire en classe

Ces exercices sont faits pour travailler en classe. Ils servent à approfondir les notions de la section et à atteindre les objectifs d’apprentissage plus avancés.
🔗
1.
Déterminer \(a_2,\,a_3\) et \(a_4\) si:
🔗
(a)
\(a_n=a_{n-1}a_{n-2}\) pour \(n=2,\,3,\,4,\dots,\) sachant que \(a_0=4\) et \(a_1=3\)
🔗
Réponse.
\(a_2=12,\ a_3= 36,\ a_4=432\)
🔗
🔗
(b)
\(a_n=a_{n-1}+3a_{n-2}\) pour \(n=2,\,3,\,4,\dots,\) sachant que \(a_0=1\) et \(a_1=2\)
🔗
Réponse.
\(a_2=5,\ a_3=11,\ a_4=26\)
🔗
🔗
(c)
\(a_n=na_{n-1}a_{n-2}\) pour \(n=2,\,3,\,4,\dots,\) sachant que \(a_0=3\) et \(a_1=-5\)
🔗
Réponse.
\(a_2=-30,\ a_3=450,\ a_4=-54\ 800\)
🔗
🔗
🔗
2.
Pour chacune des relations de récurrences ci-dessous, trouver la solution générale respectant les conditions initiales données.
🔗
(a)
\(a_n=4a_{n-1}-3a_{n-2}\text{,}\) où \(a_0=1\) et \(a_1=2\text{.}\)
🔗
Réponse.
\(a_n=\frac{3^n}{2}+\frac{1}{2}\)
🔗
🔗
Solution.
L’équation caractéristique de cette relation est \(0=r^2-4r+3\text{.}\) Les racines de cette équation sont \(r_1=3\) et \(r_2=1\text{.}\) Ainsi, on a \(a_n=\alpha_1 (3)^n + \alpha_2 (1)^n=\alpha_1 (3)^n + \alpha_2\text{.}\) Puisque \(a_0=1\) et \(a_1=2\text{,}\) en remplaçant successivement \(n\) par \(0\) et \(1\text{,}\) on obtient
\begin{align*} 1 \amp = \alpha_1+\alpha_2 \\ 2 \amp = 3 \alpha_1+\alpha_2 \end{align*}
🔗
En résolvant les équations, on trouve \(\alpha_1=\frac{1}{2}\) et \(\frac{1}{2}\text{.}\) Ainsi, \(a_n=\frac{3^n}{2}+\frac{1}{2}\)
🔗
🔗
🔗
(b)
\(a_n=8a_{n-1}-16a_{n-2}\text{,}\) où \(a_0=0\) et \(a_1=1\text{.}\)
🔗
Réponse.
\(a_n=n 4^{n-1}\)
🔗
🔗
Solution.
L’équation caractéristique de cette relation est \(0=r^2-8r+16\text{.}\) L’unique racine de cette équation est \(r_1=4\text{.}\) Ainsi, on a \(a_n=\alpha_1 (4)^n + \alpha_2\cdot n\cdot (4)^n\text{.}\) Puisque \(a_0=0\) et \(a_1=1\text{,}\) en remplaçant successivement \(n\) par \(0\) et \(1\text{,}\) on obtient
\begin{align*} 0 \amp = \alpha_1 \\ 1 \amp = 4 \alpha_1+4 \alpha_2 \end{align*}
🔗
En résolvant les équations, on trouve \(\alpha_1=0\) et \(\frac{1}{4}\text{.}\) Ainsi, \(a_n=n\frac{4^n}{4}=n 4^{n-1}\)
🔗
🔗
🔗
(c)
\(a_n=-2a_{n-1}+35a_{n-2}\text{,}\) où \(a_0=1\) et \(a_1=4\text{.}\)
🔗
Réponse.
\(a_n=\frac{11\cdot 5^n}{12}+\frac{(-7)^n}{12}\)
🔗
🔗
Solution.
L’équation caractéristique de cette relation est \(0=r^2+2r-35\text{.}\) Les racines de cette équation sont \(r_1=5\) et \(r_2=-7\text{.}\) Ainsi, on a \(a_n=\alpha_1 (5)^n + \alpha_2 (-7)^n\text{.}\) Puisque \(a_0=1\) et \(a_1=4\text{,}\) en remplaçant successivement \(n\) par \(0\) et \(1\text{,}\) on obtient
\begin{align*} 1 \amp = \alpha_1 +\alpha_2\\ 4 \amp = 5 \alpha_1-7 \alpha_2 \end{align*}
🔗
En résolvant les équations, on trouve \(\alpha_1=\frac{11}{12}\) et \(\frac{1}{12}\text{.}\) Ainsi, \(a_n=\frac{11\cdot 5^n}{12}+\frac{(-7)^n}{12}\)
🔗
🔗
🔗
(d)
\(a_n=2a_{n-1}+35a_{n-2}\text{,}\) où \(a_0=2\) et \(a_1=3\text{.}\)
🔗
Réponse.
\(a_n=\frac{13\cdot 7^n}{12}+\frac{11 (-5)^n}{12}\)
🔗
🔗
Solution.
L’équation caractéristique de cette relation est \(0=r^2-2r-35\text{.}\) Les racines de cette équation sont \(r_1=7\) et \(r_2=-5\text{.}\) Ainsi, on a \(a_n=\alpha_1 (7)^n + \alpha_2 (-5)^n\text{.}\) Puisque \(a_0=2\) et \(a_1=3\text{,}\) en remplaçant successivement \(n\) par \(0\) et \(1\text{,}\) on obtient
\begin{align*} 2 \amp = \alpha_1 +\alpha_2\\ 3 \amp = 7 \alpha_1-5 \alpha_2 \end{align*}
🔗
En résolvant les équations, on trouve \(\alpha_1=\frac{13}{12}\) et \(\frac{11}{12}\text{.}\) Ainsi, \(a_n=\frac{11\cdot 5^n}{12}+\frac{(-7)^n}{12}\)
🔗
🔗
🔗
(e)
\(a_n=14a_{n-1}-49a_{n-2}\text{,}\) où \(a_0=0\) et \(a_1=0\text{.}\)
🔗
Réponse.
\(a_n=0\)
🔗
🔗
Solution 1.
L’équation caractéristique de cette relation est \(0=r^2-14r+49\text{.}\) L’unique racine de cette équation est \(r_1=7\text{.}\) Ainsi, on a \(a_n=\alpha_1 (7)^n + \alpha_2\cdot n \cdot (7)^n\text{.}\) Puisque \(a_0=0\) et \(a_1=0\text{,}\) en remplaçant successivement \(n\) par \(0\) et \(1\text{,}\) on obtient
\begin{align*} 0 \amp = \alpha_1 +\alpha_2\\ 0 \amp = 7 \alpha_1 \end{align*}
🔗
En résolvant les équations, on trouve \(\alpha_1=\alpha_2=0\text{.}\) Ainsi, \(a_n=0\text{.}\)
🔗
🔗
Solution 2.
On peut également utiliser une preuve par induction pour montrer que \(a_n=0\) pour \(n\geq 0\text{.}\)
🔗
🔗
🔗
🔗
3.
Trouver la forme générale de la suite de Fibonacci \(\{F_n\},\) où \(F_{n}=F_{n-1}+F_{n-2}\) pour \(n\geq 2,\) et \(F_0=F_1=1\text{.}\)
🔗
Réponse.
\(F_n=\left(\frac{5+\sqrt{5}}{10}\right)\left(\frac{1+\sqrt{5}}{2}\right)^n+\left(\frac{5-\sqrt{5}}{10}\right)\left(\frac{1-\sqrt{5}}{2}\right)^n\)
🔗
Solution.
L’équation caractéristique de cette relation est \(0=r^2-r-1\text{.}\) Les racines de cette équation sont \(r_1=\frac{1+\sqrt{5}}{2}\) et \(r_2=\frac{1-\sqrt{5}}{2}\text{.}\) Ainsi, on a \(F_n=\alpha_1\left(\frac{1+\sqrt{5}}{2}\right)^n+\alpha_2 \left(\frac{1-\sqrt{5}}{2}\right)^n\text{.}\) Puisque \(F_0=1\) et \(F_1=1\text{,}\) en remplaçant successivement \(n\) par \(0\) et \(1\text{,}\) on obtient
\begin{align*} 1 \amp = \alpha_1 +\alpha_2\\ 1 \amp = \alpha_1\frac{1+\sqrt{5}}{2}+\alpha_2 \frac{1-\sqrt{5}}{2} \end{align*}
🔗
En résolvant les équations, on trouve \(\alpha_1=\frac{5+\sqrt{5}}{10}\) et \(\alpha_2=\frac{5-\sqrt{5}}{10}\text{.}\) Ainsi, \(F_n=\left(\frac{5+\sqrt{5}}{10}\right)\left(\frac{1+\sqrt{5}}{2}\right)^n+\left(\frac{5-\sqrt{5}}{10}\right)\left(\frac{1-\sqrt{5}}{2}\right)^n\text{.}\)
🔗
🔗
🔗
4.
À l’aide de l’exercice 6.1.8.3, montrer que \(\left(\frac{5+\sqrt{5}}{10}\right)\left(\frac{1+\sqrt{5}}{2}\right)^n+\left(\frac{5-\sqrt{5}}{10}\right)\left(\frac{1-\sqrt{5}}{2}\right)^n \in\,\N\) si \(n\in\,\N\text{.}\)
🔗
Solution.
Par 6.1.8.3, on sait que \(\left(\frac{5+\sqrt{5}}{10}\right)\left(\frac{1+\sqrt{5}}{2}\right)^n+\left(\frac{5-\sqrt{5}}{10}\right)\left(\frac{1-\sqrt{5}}{2}\right)^n\) est le \(n\) ième terme de la suite de Fibonacci. On sait également que les termes de la suite de Fibonacci sont des entiers naturels. Ainsi, \(\left(\frac{5+\sqrt{5}}{10}\right)\left(\frac{1+\sqrt{5}}{2}\right)^n+\left(\frac{5-\sqrt{5}}{10}\right)\left(\frac{1-\sqrt{5}}{2}\right)^n \in\,\N\text{.}\)
🔗
🔗
🔗
5.
Trouver la forme générale de la suite \(\{a_n\}\) si \(a_n=a_{n-1}a_{n-2}\) pour \(n=2,\,3,\,4,\dots,\) sachant que \(a_0=2\) et \(a_1=3\text{.}\)
🔗
Indice 1.
Écrire les premiers termes comme un produit d’une puissance de \(2\) par une puissance de \(3.\) Chercher le terme général des exposants de \(2\) et \(3\text{.}\)
🔗
🔗
Indice 2.
6.1.8.3
🔗
Réponse.
\(a_n=2^{F_{n-2}}3^{F_{n-1}}\) pour \(n\geq 2\text{.}\)
🔗
🔗
🔗
🔗
🔗
🔗
PrécédentTopSuivant