7.4 La méthode du polynôme caractéristique

Comme vous l’avez sans doute remarqué dans la section précédente, la méthode des fonctions génératrices peut d’avoir longue et pénible à appliquer. Heureusement pour nous, dans plusieurs cas important, il nous est possible de simplifier grandement la méthode. Le premier cas que nous allons traiter est celui des récurrences homogènes linéaires à coefficients constants.

Définition 7.4.1.

Pour une suite définie par récurrence, on définit les termes suivants:

  1. 1.
    ​

    Linéaire: Tous les termes ai\displaystyle a_{i} sont à la puissance 1\displaystyle 1.

  2. 2.
    ​

    Homogène: Tout les termes contiennent un ai\displaystyle a_{i}.

  3. 3.
    ​

    Coefficients constants: Tous les coefficients des ai\displaystyle a_{i} sont des constantes.

Théorème 7.4.1:

Méthode du polynôme caractéristique. Si an\displaystyle a_{n} est une suite définie par récurrence qui est homogène, linéaire et à coefficient constant de la forme:

an=c1⁢an−1+c2⁢an−2+c3⁢an−3+…⁢ck⁢an−k\displaystyle a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+c_{3}a_{n-3}+...c_{k}a_{n-k}

Alors on définit le polynôme caractéristique comme étant:

p⁢(λ)\displaystyle\displaystyle p(\lambda) =\displaystyle\displaystyle= −λk+c1⁢λk−1+c2⁢λk−2+c3⁢λk−3+…+ck−1⁢λ+ck\displaystyle\displaystyle-\lambda^{k}+c_{1}\lambda^{k-1}+c_{2}\lambda^{k-2}+c% _{3}\lambda^{k-3}+...+c_{k-1}\lambda+c_{k}
=\displaystyle\displaystyle= −(λ−r1)α1⁢(λ−r2)α2⁢…⁢(λ−rm)αm\displaystyle\displaystyle-(\lambda-r_{1})^{\alpha_{1}}(\lambda-r_{2})^{\alpha% _{2}}...(\lambda-r_{m})^{\alpha_{m}}

où les ri\displaystyle r_{i} sont les racines distinctes du polynôme. Pour chacune des racines ri\displaystyle r_{i}, on prend donc une somme de la forme

C1⁢rin+C2⁢n⁢rin+C3⁢n2⁢rin+…+Cαi⁢nαi−1⁢rin\displaystyle C_{1}r_{i}^{n}+C_{2}nr_{i}^{n}+C_{3}n^{2}r_{i}^{n}+...+C_{\alpha% _{i}}n^{\alpha_{i}-1}r_{i}^{n}

En faisant la somme des sommes obtenus pour chacune des racines, on obtient alors la forme générale d’une formule explicite pour notre récurrence an\displaystyle a_{n}.

Exemple 7.4.1.

On veut résoudre l’équation définie par récurrence suivante:

{an=−4⁢an−1+77⁢an−2,∀n≥3a1=41a2=683\displaystyle\left\{\begin{array}[]{l}a_{n}=-4a_{n-1}+77a_{n-2},\leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \forall n\geq 3\\ a_{1}=41\\ a_{2}=683\end{array}\right.

Pour ce faire, on doit commencer par résoudre l’Équation r2=−4⁢r+77\displaystyle r^{2}=-4r+77 c’est à dire trouver les racines du polynôme r2+4⁢r−77=0\displaystyle r^{2}+4r-77=0.

r=−4±42−4⁢(1)⁢(−77)2⁢(1)=−4±3242=−4±182=−2±9=7⁢ et −11\displaystyle r=\frac{-4\pm\sqrt{4^{2}-4(1)(-77)}}{2(1)}=\frac{-4\pm\sqrt{324}% }{2}=\frac{-4\pm 18}{2}=-2\pm 9=7\textrm{ et }-11

Donc la solution de l’équation aura donc la forme:

an=7n⁢α1+(−11)n⁢α2,∀n≥1\displaystyle a_{n}=7^{n}\alpha_{1}+(-11)^{n}\alpha_{2},\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \forall n\geq 1

Pour trouver α1\displaystyle\alpha_{1} et α2\displaystyle\alpha_{2}, on utilise les valeurs a1=41\displaystyle a_{1}=41 et a2=683\displaystyle a_{2}=683, ce qui nous amène au système d’équations linéaires suivant:

{7⁢α1−11⁢α2=4149⁢α1+121⁢α2=683⇒{49⁢α1−77⁢α2=28749⁢α1+121⁢α2=683⇒ 198α2=396⇒ 2\displaystyle\left\{\begin{array}[]{l}7\alpha_{1}-11\alpha_{2}=41\\ 49\alpha_{1}+121\alpha_{2}=683\end{array}\right.\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ \Rightarrow\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \left\{\begin{array}[]{l}4% 9\alpha_{1}-77\alpha_{2}=287\\ 49\alpha_{1}+121\alpha_{2}=683\end{array}\right.\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \Rightarrow\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ 198\alpha_{2}=396\leavevmode\nobreak% \ \leavevmode\nobreak\ \leavevmode\nobreak\ \Rightarrow\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ 2

Puis en remplaçant dans la première équation on trouve α1=9\displaystyle\alpha_{1}=9, ce qui nous donne la solution suivante:

an=9⁢(7)n+2⁢(−11)n,∀n≥1\displaystyle a_{n}=9(7)^{n}+2(-11)^{n},\leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \forall n\geq 1
Exemple 7.4.2.

On veut résoudre l’équation définie par récurrence suivante:

{an=8⁢an−1−16⁢an−2,∀n≥3a1=20a2=128\displaystyle\left\{\begin{array}[]{l}a_{n}=8a_{n-1}-16a_{n-2},\leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \forall n\geq 3\\ a_{1}=20\\ a_{2}=128\end{array}\right.

Pour ce faire, on commence par trouver les solutions de l’équation r2=8⁢r−16\displaystyle r^{2}=8r-16, c’est à dire trouver les racines du polynôme r2−8⁢r+16=0\displaystyle r^{2}-8r+16=0.

r=8±(−8)2−4⁢(1)⁢(16)2⁢(1)=8±02=4\displaystyle r=\frac{8\pm\sqrt{(-8)^{2}-4(1)(16)}}{2(1)}=\frac{8\pm 0}{2}=4

Donc la seule racine est r\displaystyle r. On peut donc affirmer que la solution aura la forme

an=α1⁢(4)n+α2⁢n⁢(4)n\displaystyle a_{n}=\alpha_{1}(4)^{n}+\alpha_{2}n(4)^{n}

Il faut maintenant trouver la valeur des constantes, pour ce faire, on doit résoudre le système d’équations linéaires suivant:

{4⁢α1+4⁢α2=2016⁢α1+32⁢α2=128⇒{16⁢α1+16⁢α2=8016⁢α1+32⁢α2=128⇒ 16α2=48⇒α2=3\displaystyle\left\{\begin{array}[]{l}4\alpha_{1}+4\alpha_{2}=20\\ 16\alpha_{1}+32\alpha_{2}=128\end{array}\right.\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \Rightarrow\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \left\{\begin{array}[]{l}16\alpha_{1% }+16\alpha_{2}=80\\ 16\alpha_{1}+32\alpha_{2}=128\end{array}\right.\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \Rightarrow\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ 16\alpha_{2}=48\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \Rightarrow\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \alpha_{2}=3

Puis en utilisant la première équation on obtient α1=2\displaystyle\alpha_{1}=2. La solution est donc:

an=2⁢(4)n+3⁢n⁢(4)n,∀n≥1\displaystyle a_{n}=2(4)^{n}+3n(4)^{n},\leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \forall n\geq 1
Exemple 7.4.3.

On veut résoudre l’équation de récurrence suivante:

{an=5⁢an−1+14⁢an−2,∀n≥2a0=7a1=22\displaystyle\left\{\begin{array}[]{l}a_{n}=5a_{n-1}+14a_{n-2},\leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \forall n\geq 2\\ a_{0}=7\\ a_{1}=22\end{array}\right.

Comme il s’agit d’une récurrence linéaire homogène à coefficients constants, nous pouvons appliquer la méthode du polynôme caractéristique. Pour ce faire, on doit trouver les racines du polynôme suivant:

λ2=5⁢λ+14⇒λ2−5⁢λ−14=0⇒(λ−7)⁢(λ+2)=0\displaystyle\lambda^{2}=5\lambda+14\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \Rightarrow\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \lambda^{2}-5\lambda-14=0\leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \Rightarrow\leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ (\lambda-7)(\lambda+2)=0

Les racines sont donc λ1=7\displaystyle\lambda_{1}=7 et λ2=−2\displaystyle\lambda_{2}=-2. La solution de l’équation de récurrence aura donc la forme suivante:

an=C1⁢(7)n+C2⁢(−2)n\displaystyle a_{n}=C_{1}(7)^{n}+C_{2}(-2)^{n}

Pour trouver les constantes, on utilise les conditions initiale:

{a0=7=C1+C2a1=22=7⁢C1−2⁢C2\displaystyle\left\{\begin{array}[]{l}a_{0}=7=C_{1}+C_{2}\\ a_{1}=22=7C_{1}-2C_{2}\end{array}\right.

De la première équation, on obtient C1=7−C2\displaystyle C_{1}=7-C_{2}, puis en remplaçant dans la seconde on obtient:

22=7(7−C2)−2C2=49−7C2−2C2=49−9C2⇒ 9C2=27⇒C2=3\displaystyle 22=7(7-C_{2})-2C_{2}=49-7C_{2}-2C_{2}=49-9C_{2}\leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \Rightarrow\leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ 9C_{2}=27\leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \Rightarrow\leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ C_{2}=3

Ce qui nous donne finalement C1=7−3=4\displaystyle C_{1}=7-3=4. La solution de l’équation de récurrence est donc:

an=4⁢(7)n+3⁢(−2)n,∀n≥0\displaystyle a_{n}=4(7)^{n}+3(-2)^{n},\leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \forall n\geq 0
Exemple 7.4.4.

On veut résoudre la suite définie par récurrence suivante:

{an=17⁢an−1−103⁢an−2+267⁢an−3−252⁢an−4,∀n≥5a0=16a1=89a3=536a4=3431\displaystyle\left\{\begin{array}[]{l}a_{n}=17a_{n-1}-103a_{n-2}+267a_{n-3}-25% 2a_{n-4},\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ % \forall n\geq 5\\ a_{0}=16\\ a_{1}=89\\ a_{3}=536\\ a_{4}=3431\end{array}\right.

Pour ce faire, commençons par trouver son polynôme caractéristique. On a donc:

p⁢(λ)=−λ4+17⁢λ3−103⁢λ2+267⁢λ−252\displaystyle p(\lambda)=-\lambda^{4}+17\lambda^{3}-103\lambda^{2}+267\lambda-% 252

De plus, en remplaçant λ\displaystyle\lambda par −λ\displaystyle-\lambda on obtient:

p⁢(λ)=−λ4−17⁢λ3−103⁢λ2−267⁢λ−252\displaystyle p(\lambda)=-\lambda^{4}-17\lambda^{3}-103\lambda^{2}-267\lambda-% 252

On remarque donc que toutes les racines de polynôme caractéristique doivent être positive, et de plus, si elle sont rationnelles elles doivent être un diviseur de 252\displaystyle 252. Comme 252=22⋅32⋅7\displaystyle 252=2^{2}\cdot 3^{2}\cdot 7, il est facile de voir que 252\displaystyle 252 possède exactement 3⋅3⋅2=18\displaystyle 3\cdot 3\cdot 2=18 diviseurs. En testant pour les différents diviseurs, on obtient facilement que 3\displaystyle 3 est une racine. Nous allons donc effectuer la division euclidienne, ce qui nous permet d’obtenir:

−λ4+17⁢λ3−103⁢λ2+267⁢λ−252=−(λ−3)⁢(λ3−14⁢λ2+61⁢λ−84)\displaystyle-\lambda^{4}+17\lambda^{3}-103\lambda^{2}+267\lambda-252=-(% \lambda-3)(\lambda^{3}-14\lambda^{2}+61\lambda-84)

Il nous faut donc factoriser le polynôme λ3−14⁢λ2+61⁢λ−84\displaystyle\lambda^{3}-14\lambda^{2}+61\lambda-84. Pour ce faire, remarquons qu’à nouveau la règle des signes de Descartes nous permet d’affirmer que toutes les racines sont réelles. De plus, par le théorème des racines rationnelles, nous savons que si une racine rationnelle existe, elle doit être un diviseur de 84\displaystyle 84. Comme 84=22⋅3⋅7\displaystyle 84=2^{2}\cdot 3\cdot 7, nous avons au plus 12\displaystyle 12 diviseurs à tester. Nous obtenons donc facilement que 3\displaystyle 3 est à nouveau une racine. On a donc:

−λ4+17λ3−103λ2+267λ−252=−(λ−3)2(λ2−11λ+28)=λ−3)2(λ−4)(λ−7)\displaystyle-\lambda^{4}+17\lambda^{3}-103\lambda^{2}+267\lambda-252=-(% \lambda-3)^{2}(\lambda^{2}-11\lambda+28)=\lambda-3)^{2}(\lambda-4)(\lambda-7)

Les racines du polynôme caractéristique sont donc 3,3,4,7\displaystyle 3,3,4,7. Notez que 3\displaystyle 3 est une racines double. La forme explicite de notre récurrence est donc:

an=C1⋅3n+C2⁢n⋅3n+C3⋅4n+C4⋅7n\displaystyle a_{n}=C_{1}\cdot 3^{n}+C_{2}n\cdot 3^{n}+C_{3}\cdot 4^{n}+C_{4}% \cdot 7^{n}

En remplaçant les différentes valeurs initiales dans cette équations, nous obtenons donc le système d’équations linéaires suivant:

{C1+C3+C4=163⁢C1+3⁢C2+4⁢C3+7⁢C4=899⁢C1+18⁢C2+16⁢C3+49⁢C4=53627⁢C1+81⁢C2+64⁢C3+343⁢C4=3431\displaystyle\left\{\begin{array}[]{l}C_{1}+C_{3}+C_{4}=16\\ 3C_{1}+3C_{2}+4C_{3}+7C_{4}=89\\ 9C_{1}+18C_{2}+16C_{3}+49C_{4}=536\\ 27C_{1}+81C_{2}+64C_{3}+343C_{4}=3431\end{array}\right.

Que l’on peut résoudre à l’aide par exemple de la méthode de Gauss. On obtient donc:

(10111633478991816495362781643433431)∼−3⁢L1+L2→L2−9⁢L1+L3→L3−27⁢L1+L4→L4(101116031441018740392081373162999)∼−6⁢L2+L3→L3−27⁢L2+L4→L4(1011160314410011614600102081892)\displaystyle\left(\begin{array}[]{@{}*{4}{c}|c@{}}1&0&1&1&16\\ 3&3&4&7&89\\ 9&18&16&49&536\\ 27&81&64&343&3431\end{array}\right)\stackrel{{\scriptstyle{\begin{array}[]{c}-% 3L_{1}+L_{2}\rightarrow L_{2}\\ -9L_{1}+L_{3}\rightarrow L_{3}\\ -27L_{1}+L_{4}\rightarrow L_{4}\end{array}}}}{{\sim}}\left(\begin{array}[]{@{}% *{4}{c}|c@{}}1&0&1&1&16\\ 0&3&1&4&41\\ 0&18&7&40&392\\ 0&81&37&316&2999\end{array}\right)\stackrel{{\scriptstyle{\begin{array}[]{c}-6% L_{2}+L_{3}\rightarrow L_{3}\\ -27L_{2}+L_{4}\rightarrow L_{4}\end{array}}}}{{\sim}}\left(\begin{array}[]{@{}% *{4}{c}|c@{}}1&0&1&1&16\\ 0&3&1&4&41\\ 0&0&1&16&146\\ 0&0&10&208&1892\end{array}\right)
∼−10⁢L3+L4→L4(1011160314410011614600048432)\displaystyle\stackrel{{\scriptstyle{\begin{array}[]{c}-10L_{3}+L_{4}% \rightarrow L_{4}\end{array}}}}{{\sim}}\left(\begin{array}[]{@{}*{4}{c}|c@{}}1% &0&1&1&16\\ 0&3&1&4&41\\ 0&0&1&16&146\\ 0&0&0&48&432\end{array}\right)

Ce qui nous permet d’obtenir:

C4\displaystyle\displaystyle C_{4} =\displaystyle\displaystyle= 9\displaystyle\displaystyle 9
C3\displaystyle\displaystyle C_{3} =\displaystyle\displaystyle= 146−16⁢(9)=2\displaystyle\displaystyle 146-16(9)=2
C2\displaystyle\displaystyle C_{2} =\displaystyle\displaystyle= 41−1⁢(4)−4⁢(9)3=33=1\displaystyle\displaystyle\frac{41-1(4)-4(9)}{3}=\frac{3}{3}=1
C1\displaystyle\displaystyle C_{1} =\displaystyle\displaystyle= 16−9−2=5\displaystyle\displaystyle 16-9-2=5

La solution de notre équation de récurrence est donc:

an=5⋅3n+n⋅3n+2⋅4n+9⋅7n,∀n≥0\displaystyle a_{n}=5\cdot 3^{n}+n\cdot 3^{n}+2\cdot 4^{n}+9\cdot 7^{n},% \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \forall n\geq 0