7.7 Les systèmes de récurrences

Maintenant que nous avons regardé les techniques standards de résolution des récurrences, il est temps de s’attaquer aux systèmes de récurrences. De façons générale, les fonctions génératrices ordinaires ou exponentielles peuvent à nouveau s’avérer utile. nous allons illustrer cette méthode à l’aide d’un exemple.

Exemple 7.7.1.

On veut résoudre le système de récurrences suivant:

{an=−9⁢an−1+7⁢bn−1,∀n≥1bn=−14⁢an−1+12⁢bn−1,∀n≥1a0=7b0=6\displaystyle\left\{\begin{array}[]{l}a_{n}=-9a_{n-1}+7b_{n-1},\leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \forall n\geq 1\\ b_{n}=-14a_{n-1}+12b_{n-1},\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \forall n\geq 1\\ a_{0}=7\\ b_{0}=6\end{array}\right.

Pour ce faire, nous avons besoin de deux fonctions génératrices, une pour chacune des deux suite. Nous allons donc définir:

f⁢(x)=∑n=0∞an⁢xnetg⁢(x)=∑n=0∞bn⁢xn\displaystyle f(x)=\sum_{n=0}^{\infty}a_{n}x^{n}\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ \textrm{et}\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ g(x)=\sum_{n=0}^{\infty}b_% {n}x^{n}

Ce qui nous permet d’obtenir:

f⁢(x)\displaystyle\displaystyle f(x) =\displaystyle\displaystyle= ∑n=0∞an⁢xn=7+∑n=1∞(−9⁢an−1+7⁢bb−1)⁢xn=7−9⁢x⁢∑n=1∞an−1⁢xn−1+7⁢x⁢∑n=1∞bn−1⁢xn−1\displaystyle\displaystyle\sum_{n=0}^{\infty}a_{n}x^{n}=7+\sum_{n=1}^{\infty}(% -9a_{n-1}+7b_{b-1})x^{n}=7-9x\sum_{n=1}^{\infty}a_{n-1}x^{n-1}+7x\sum_{n=1}^{% \infty}b_{n-1}x^{n-1}
=\displaystyle\displaystyle= 7−9⁢x⁢∑n=1∞an⁢xn+7⁢x⁢∑n=1∞bn⁢xn=7−9⁢x⁢f⁢(x)+7⁢x⁢g⁢(x)\displaystyle\displaystyle 7-9x\sum_{n=1}^{\infty}a_{n}x^{n}+7x\sum_{n=1}^{% \infty}b_{n}x^{n}=7-9xf(x)+7xg(x)
g⁢(x)\displaystyle\displaystyle g(x) =\displaystyle\displaystyle= ∑n=0∞an⁢xn=6+∑n=1∞(−14⁢an−1+12⁢bb−1)⁢xn=6−14⁢x⁢∑n=1∞an−1⁢xn−1+12⁢x⁢∑n=1∞bn−1⁢xn−1\displaystyle\displaystyle\sum_{n=0}^{\infty}a_{n}x^{n}=6+\sum_{n=1}^{\infty}(% -14a_{n-1}+12b_{b-1})x^{n}=6-14x\sum_{n=1}^{\infty}a_{n-1}x^{n-1}+12x\sum_{n=1% }^{\infty}b_{n-1}x^{n-1}
=\displaystyle\displaystyle= 6−14⁢x⁢∑n=1∞an⁢xn+12⁢x⁢∑n=1∞bn⁢xn=6−14⁢x⁢f⁢(x)+12⁢x⁢g⁢(x)\displaystyle\displaystyle 6-14x\sum_{n=1}^{\infty}a_{n}x^{n}+12x\sum_{n=1}^{% \infty}b_{n}x^{n}=6-14xf(x)+12xg(x)

Ce qui nous permet d’obtenir le système d’équation suivant avec f⁢(x)\displaystyle f(x) et g⁢(x)\displaystyle g(x) les inconnus:

{(1+9⁢x)⁢f⁢(x)−7⁢x⁢g⁢(x)=714⁢x⁢f⁢(x)+(1−12⁢x)⁢g⁢(x)=6\displaystyle\left\{\begin{array}[]{l}(1+9x)f(x)-7x\leavevmode\nobreak\ g(x)=7% \\[10.0pt] 14x\leavevmode\nobreak\ f(x)+(1-12x)g(x)=6\end{array}\right.

Pour trouver f⁢(x)\displaystyle f(x) et g⁢(x)\displaystyle g(x), on peut appliquer n’importe quelle méthode de résolution de systèmes d’équations linéaires, mais dans le cas présent comme il s’agit d’un système 2×2\displaystyle 2\times 2 avec coefficients polynomiaux, la méthode de Cramer est probablement la plus simple. Pour la fonction f⁢(x)\displaystyle f(x), on a donc:

f⁢(x)=|7−7⁢x61−12⁢x||1+9⁢x−7⁢x14⁢x1−12⁢x|=7−42⁢x1−3⁢x−10⁢x2=7−42⁢x(1−5⁢x)⁢(1+2⁢x)=A1−5⁢x+B1+2⁢x=(A+B)+(2⁢A−5⁢B)⁢x(1−5⁢x)⁢(1+2⁢x)\displaystyle f(x)=\frac{\begin{vmatrix}7&-7x\\ 6&1-12x\end{vmatrix}}{\begin{vmatrix}1+9x&-7x\\ 14x&1-12x\end{vmatrix}}=\frac{7-42x}{1-3x-10x^{2}}=\frac{7-42x}{(1-5x)(1+2x)}=% \frac{A}{1-5x}+\frac{B}{1+2x}=\frac{(A+B)+(2A-5B)x}{(1-5x)(1+2x)}

On doit donc résoudre le système d’équations linéaires suivant:

{A+B=72⁢A−5⁢B=−42\displaystyle\left\{\begin{array}[]{l}A+B=7\\ 2A-5B=-42\end{array}\right.

Ce qui nous donne A=−1\displaystyle A=-1 et B=8\displaystyle B=8. En revenant à notre fonction génératrice, on obtient donc:

f⁢(x)=∑n=0∞an⁢xn=−11−5⁢x+81+2⁢x=∑n=0∞(−1⁢(5)n+8⁢(−2)n)⁢xn\displaystyle f(x)=\sum_{n=0}^{\infty}a_{n}x^{n}=\frac{-1}{1-5x}+\frac{8}{1+2x% }=\sum_{n=0}^{\infty}\Big{(}-1(5)^{n}+8(-2)^{n}\Big{)}x^{n}

La suite an\displaystyle a_{n} est donc donné par la formule explicite suivante:

an=8⁢(−2)n−5n,∀n≥0\displaystyle a_{n}=8(-2)^{n}-5^{n},\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \forall n\geq 0

On répète ensuite le même principe pour la fonction g⁢(x)\displaystyle g(x). On a donc:

g⁢(x)=|1+9⁢x714⁢x6||1+9⁢x−7⁢x14⁢x1−12⁢x|=6−44⁢x1−3⁢x−10⁢x2=6−44⁢x(1−5⁢x)⁢(1+2⁢x)=C1−5⁢x+D1+2⁢x=(C+D)+(2⁢C−5⁢D)⁢x(1−5⁢x)⁢(1+2⁢x)\displaystyle g(x)=\frac{\begin{vmatrix}1+9x&7\\ 14x&6\end{vmatrix}}{\begin{vmatrix}1+9x&-7x\\ 14x&1-12x\end{vmatrix}}=\frac{6-44x}{1-3x-10x^{2}}=\frac{6-44x}{(1-5x)(1+2x)}=% \frac{C}{1-5x}+\frac{D}{1+2x}=\frac{(C+D)+(2C-5D)x}{(1-5x)(1+2x)}

On doit donc résoudre le système d’équations linéaires suivant:

{C+D=62⁢C−5⁢D=−44\displaystyle\left\{\begin{array}[]{l}C+D=6\\ 2C-5D=-44\end{array}\right.

Ce qui nous donne: C=−2\displaystyle C=-2 et D=8\displaystyle D=8. En revenant à notre fonction génératrice:

g⁢(x)=−21−5⁢x+81+2⁢x=∑n=0∞(−2⁢(5)n+8⁢(−2)n)⁢xn\displaystyle g(x)=\frac{-2}{1-5x}+\frac{8}{1+2x}=\sum_{n=0}^{\infty}\Big{(}-2% (5)^{n}+8(-2)^{n}\Big{)}x^{n}

La suite bn\displaystyle b_{n} a donc comme formule explicite l’expression suivante:

bn=8⁢(−2)n−2⁢(5)n,∀n≥0\displaystyle b_{n}=8(-2)^{n}-2(5)^{n},\leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \forall n\geq 0

Dans le cas où chacune des équations de notre système est linéaire, homogène et à coefficients constants, il est aussi possible d’appliquer la méthode du polynôme caractéristique, ce qui simplifie grandement le problème. La clé pour pouvoir appliquer cette méthode est de réaliser qu’un tel système peut être écrit sous la forme matricielle suivante:

x→n=A⁢x→n−1,∀n≥0\displaystyle\vec{x}_{n}=A\vec{x}_{n-1},\leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \forall n\geq 0

Dans ce cas, le polynôme caractéristique est défini comme étant:

p⁢(λ)=det(A−λ⁢I)\displaystyle p(\lambda)=\det(A-\lambda I)

Toutes les règles que nous avons vues concernant la résolution d’une récurrence à l’aide du polynôme caractéristique peuvent alors être appliquées. À noter que la forme de notre solution sera la même que l’on cherche les solutions de an\displaystyle a_{n}, bn\displaystyle b_{n} ou même de an+bn\displaystyle a_{n}+b_{n}. Seules les constantes changeront. Nous allons illustrer cette méthode en résolvant à nouveau la même récurrence que dans l’exemple précédent.

Exemple 7.7.2.

On veut résoudre le système de récurrences suivant à l’aide de la méthode du polynôme caractéristique:

{an=−9⁢an−1+7⁢bn−1,∀n≥1bn=−14⁢an−1+12⁢bn−1,∀n≥1a0=7b0=6\displaystyle\left\{\begin{array}[]{l}a_{n}=-9a_{n-1}+7b_{n-1},\leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \forall n\geq 1\\ b_{n}=-14a_{n-1}+12b_{n-1},\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \forall n\geq 1\\ a_{0}=7\\ b_{0}=6\end{array}\right.

Pour ce faire, on commence par réécrire notre récurrence sous forme matricielle:

(anbn)=(−97−1412)⏟=A⁢(an−1bn−1)\displaystyle\begin{pmatrix}a_{n}\\ b_{n}\end{pmatrix}=\underbrace{\begin{pmatrix}-9&7\\ -14&12\end{pmatrix}}_{=A}\begin{pmatrix}a_{n-1}\\ b_{n-1}\end{pmatrix}

Le polynôme caractéristique est donc:

p⁢(λ)=|−9−λ7−1412−λ|=(−9−λ)⁢(12−λ)+7⁢(14)=λ2−3⁢λ−10=(λ−5)⁢(λ+2)\displaystyle p(\lambda)=\begin{vmatrix}-9-\lambda&7\\ -14&12-\lambda\end{vmatrix}=(-9-\lambda)(12-\lambda)+7(14)=\lambda^{2}-3% \lambda-10=(\lambda-5)(\lambda+2)

La solution générales de notre récurrence est donc:

{an=A⁢(5)n+B⁢(−2)n,∀n≥0bn=C⁢(5)n+D⁢(−2)n,∀n≥1\displaystyle\left\{\begin{array}[]{l}a_{n}=A(5)^{n}+B(-2)^{n},\leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \forall n\geq 0\\ b_{n}=C(5)^{n}+D(-2)^{n},\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ \forall n\geq 1\end{array}\right.

Pour trouver les constantes, nous avons besoin de deux valeurs initiales pour chacune des deux suites. Comme nous n’en avons qu’une seule, il nous faut donc calculer la seconde.

a1=−9⁢(7)+7⁢(6)=−21 et b1=−14⁢(7)+12⁢(6)=−26\displaystyle a_{1}=-9(7)+7(6)=-21\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \textrm{ et }% \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ b_{1}=-14(7)+12(6)=-26

On doit donc résoudre les deux systèmes d’équations linéaires suivant:

{A+B=75⁢A−2⁢B=−21 et {C+D=65⁢C−2⁢D=−26\displaystyle\left\{\begin{array}[]{l}A+B=7\\ 5A-2B=-21\end{array}\right.\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \textrm{ et }% \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \left\{\begin{array}[]{l}C+D=6\\ 5C-2D=-26\end{array}\right.

On obtient donc A=−1,B=8,C=−2\displaystyle A=-1,B=8,C=-2 et D=8\displaystyle D=8. La solution de notre système est donc:

{an=8⁢(−2)n−5n,∀n≥0bn=8⁢(−2)n−2⁢(5)n,∀n≥0\displaystyle\left\{\begin{array}[]{l}a_{n}=8(-2)^{n}-5^{n},\leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \forall n\geq 0\\[10.0pt] b_{n}=8(-2)^{n}-2(5)^{n},\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ \forall n\geq 0\end{array}\right.