7.3 La méthode des fonctions génératrices

Rappelons que l’idée des fonctions génératrices est d’écrire une suite ak\displaystyle a_{k} sous la forme d’une série ∑k=0∞ak⁢xk\displaystyle\sum_{k=0}^{\infty}a_{k}x^{k}. Les outils du calcul différentiel et intégral pouvant s’appliquer aux séries (qui sont en fait des polynômes de degré infini), les séries sont plus facile à manipuler que les suites. De plus, comme il s’agit d’une bijection, si on parvient à trouver les coefficients de la série, on aura trouvé notre suite, ce qui peut en particulier nous permettre de trouver une formule explicite pour certaine suite définie par récurrence.

Nous avons déjà rencontrer quelques fonctions génératrices importante. En particulier les séries génératrices des coefficients binomiaux et des coefficients multi-ensembles que nous allons rappeler immédiatement:

∑k=0∞(nk)⁢xk=(1+x)n\displaystyle\sum_{k=0}^{\infty}\binom{n}{k}x^{k}=(1+x)^{n} ∑k=0∞⟨nk⟩⁢xk=1(1−x)n\displaystyle\sum_{k=0}^{\infty}\left\langle n\atop k\right\rangle x^{k}=\frac% {1}{(1-x)^{n}}

En prenant n=1\displaystyle n=1 dans la seconde somme, et en remplaçant x\displaystyle x par a⁢xm\displaystyle ax^{m}, on obtient la série génératrice suivante qui est particulièrement importante pour le reste du teste:

∑k=0∞ak⁢xm⁢k=11−a⁢xm\displaystyle\sum_{k=0}^{\infty}a^{k}x^{mk}=\frac{1}{1-ax^{m}}

Ce type de fonction génératrice est ce que nous appelons une fonction génératrice ordinaire. Basé sur le problème des dérangement, il nous est possible de définir un autre type de fonctions génératrices: Les fonctions génératrices exponentielles. Nous avons vu que la fonction exponentielle peut s’écrire sous la forme d’une série:

ex=∑n=0∞xnn!\displaystyle e^{x}=\sum_{n=0}^{\infty}\frac{x^{n}}{n!}

Ce qui nous amène à définir la fonction génératrice exponentielle d’une suite ak\displaystyle a_{k} comme étant ∑k=0∞ak⁢xkk!\displaystyle\sum_{k=0}^{\infty}a_{k}\frac{x^{k}}{k!}.

Exemple 7.3.1.

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

{an=5⁢an−1+2,∀n≥1a0=3\displaystyle\left\{\begin{array}[]{l}a_{n}=5a_{n-1}+2,\forall n\geq 1\\ a_{0}=3\end{array}\right.

Pour ce faire, nous allons appliquer la méthode des fonctions génératrices. On a donc:

∑n=0∞an⁢xn\displaystyle\displaystyle\sum_{n=0}^{\infty}a_{n}x^{n} =\displaystyle\displaystyle= a0+∑n=1∞an⁢xn=3+∑n=1∞(5⁢an−1+2)⁢xn=3+5⁢x⁢∑n=1∞an−1⁢xn−1+2⁢x⁢∑n=1∞xn−1\displaystyle\displaystyle a_{0}+\sum_{n=1}^{\infty}a_{n}x^{n}=3+\sum_{n=1}^{% \infty}(5a_{n-1}+2)x^{n}=3+5x\sum_{n=1}^{\infty}a_{n-1}x^{n-1}+2x\sum_{n=1}^{% \infty}x^{n-1}
=\displaystyle\displaystyle= 3+5⁢x⁢∑n=0∞an⁢xn+2⁢x⁢∑n=0∞xn=3+5⁢x⁢∑n=0∞an⁢xn+2⁢x1−x\displaystyle\displaystyle 3+5x\sum_{n=0}^{\infty}a_{n}x^{n}+2x\sum_{n=0}^{% \infty}x^{n}=3+5x\sum_{n=0}^{\infty}a_{n}x^{n}+\frac{2x}{1-x}

On obtient donc:

(1−5⁢x)⁢∑n=0∞an⁢xn\displaystyle\displaystyle(1-5x)\sum_{n=0}^{\infty}a_{n}x^{n} =\displaystyle\displaystyle= 3⁢(1−x)+2⁢x1−x=3−x1−x\displaystyle\displaystyle\frac{3(1-x)+2x}{1-x}=\frac{3-x}{1-x}
∑n=0∞an⁢xn\displaystyle\displaystyle\sum_{n=0}^{\infty}a_{n}x^{n} =\displaystyle\displaystyle= 3⁢(1−x)+2⁢x1−x=3−x(1−x)⁢(1−5⁢x)=A1−x+B1−5⁢x=A⁢(1−5⁢x)+B⁢(1−x)(1−x)⁢(1−5⁢x)\displaystyle\displaystyle\frac{3(1-x)+2x}{1-x}=\frac{3-x}{(1-x)(1-5x)}=\frac{% A}{1-x}+\frac{B}{1-5x}=\frac{A(1-5x)+B(1-x)}{(1-x)(1-5x)}

Ce qui nous donne le système d’équations linéaires suivants:

{A+B=3−5⁢A−B=−1\displaystyle\left\{\begin{array}[]{l}A+B=3\\ -5A-B=-1\end{array}\right.

En additionnant les deux équations, on obtient −4⁢A=2\displaystyle-4A=2, c’est à dire A=−12\displaystyle A=\frac{-1}{2}. En remplaçant dans la première équation, on a donc: B=72\displaystyle B=\frac{7}{2}. On obtient donc:

∑n=0∞an⁢xn=−1/21−x+7/21−5⁢x=−12⁢∑n=0∞xn+72⁢∑n=0∞5n⁢xn=∑n=0∞(−12+72⋅5n)⁢xn\displaystyle\sum_{n=0}^{\infty}a_{n}x^{n}=\frac{\nicefrac{{-1}}{{2}}}{1-x}+% \frac{\nicefrac{{7}}{{2}}}{1-5x}=\frac{-1}{2}\sum_{n=0}^{\infty}x^{n}+\frac{7}% {2}\sum_{n=0}^{\infty}5^{n}x^{n}=\sum_{n=0}^{\infty}\left(\frac{-1}{2}+\frac{7% }{2}\cdot 5^{n}\right)x^{n}

La solution de la récurrence est donc an=7⋅5n−12\displaystyle a_{n}=\frac{7\cdot 5^{n}-1}{2} pour tout n≥0\displaystyle n\geq 0.

Exemple 7.3.2.

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.

Nous allons maintenant appliquer la méthode des fonctions génératrices.

∑n=0∞an⁢xn\displaystyle\displaystyle\sum_{n=0}^{\infty}a_{n}x^{n} =\displaystyle\displaystyle= 7+22⁢x+∑n=2∞an⁢xn=7+22⁢x+∑n=2∞(5⁢an−1+14⁢an−2)⁢xn=7+22⁢x+5⁢∑n=2∞an−1⁢xn+14⁢∑n=2∞an−2⁢xn\displaystyle\displaystyle 7+22x+\sum_{n=2}^{\infty}a_{n}x^{n}=7+22x+\sum_{n=2% }^{\infty}(5a_{n-1}+14a_{n-2})x^{n}=7+22x+5\sum_{n=2}^{\infty}a_{n-1}x^{n}+14% \sum_{n=2}^{\infty}a_{n-2}x^{n}
=\displaystyle\displaystyle= 7+22⁢x+5⁢x⁢∑n=2∞an−1⁢xn−1+14⁢x2⁢∑n=2∞an−2⁢xn−2=7+22⁢x+5⁢x⁢∑n=1∞an⁢xn+14⁢x2⁢∑n=0∞an⁢xn\displaystyle\displaystyle 7+22x+5x\sum_{n=2}^{\infty}a_{n-1}x^{n-1}+14x^{2}% \sum_{n=2}^{\infty}a_{n-2}x^{n-2}=7+22x+5x\sum_{n=1}^{\infty}a_{n}x^{n}+14x^{2% }\sum_{n=0}^{\infty}a_{n}x^{n}
=\displaystyle\displaystyle= 7+22⁢x+5⁢x⁢(∑n=0∞an⁢xn−a0)+14⁢x2⁢∑n=0∞an⁢xn=7+22⁢x+5⁢x⁢(∑n=0∞an⁢xn−7)+14⁢x2⁢∑n=0∞an⁢xn\displaystyle\displaystyle 7+22x+5x\left(\sum_{n=0}^{\infty}a_{n}x^{n}-a_{0}% \right)+14x^{2}\sum_{n=0}^{\infty}a_{n}x^{n}=7+22x+5x\left(\sum_{n=0}^{\infty}% a_{n}x^{n}-7\right)+14x^{2}\sum_{n=0}^{\infty}a_{n}x^{n}
=\displaystyle\displaystyle= 7+22⁢x+5⁢x⁢∑n=0∞an⁢xn−35⁢x+14⁢x2⁢∑n=0∞an⁢xn\displaystyle\displaystyle 7+22x+5x\sum_{n=0}^{\infty}a_{n}x^{n}-35x+14x^{2}% \sum_{n=0}^{\infty}a_{n}x^{n}

Ce qui nous donne:

(1−5⁢x−14⁢x2)⁢∑n=0∞an⁢xn=7+22⁢x−35⁢x=7−13⁢x⇒∑n=0∞an⁢xn=7−13⁢x1−5⁢x−14⁢x2=7−13⁢x(1−7⁢x)⁢(1+2⁢x)\displaystyle\left(1-5x-14x^{2}\right)\sum_{n=0}^{\infty}a_{n}x^{n}=7+22x-35x=% 7-13x\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ % \Rightarrow\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \sum% _{n=0}^{\infty}a_{n}x^{n}=\frac{7-13x}{1-5x-14x^{2}}=\frac{7-13x}{(1-7x)(1+2x)}

On applique maintenant la décomposition en fraction partielle. On cherche des constantes A\displaystyle A et B\displaystyle B telle que:

7−13⁢x(1−7⁢x)⁢(1+2⁢x)=A1−7⁢x+B1+2⁢x=A⁢(1+2⁢x)+B⁢(1−7⁢x)(1−7⁢x)⁢(1+2⁢x)=(2⁢A−7⁢B)⁢x+(A+B)(1−7⁢x)⁢(1+2⁢x)\displaystyle\frac{7-13x}{(1-7x)(1+2x)}=\frac{A}{1-7x}+\frac{B}{1+2x}=\frac{A(% 1+2x)+B(1-7x)}{(1-7x)(1+2x)}=\frac{(2A-7B)x+(A+B)}{(1-7x)(1+2x)}

Ce qui nous donne le système d’équations linéaires suivant:

{2⁢A−7⁢B=−13A+B=7⇒A=4⁢ et ⁢B=3\displaystyle\left\{\begin{array}[]{l}2A-7B=-13\\ A+B=7\end{array}\right.\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ \Rightarrow\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ A=4\textrm{ et }B=3

En revenant à notre série, on a donc:

∑n=0∞an⁢xn=41−7⁢x+31+2⁢x=4⁢∑n=0∞(7⁢x)n+3⁢∑n=0∞(−2⁢x)n=∑n=0∞(4⁢(7)n+3⁢(−2)n)⁢xn\displaystyle\sum_{n=0}^{\infty}a_{n}x^{n}=\frac{4}{1-7x}+\frac{3}{1+2x}=4\sum% _{n=0}^{\infty}(7x)^{n}+3\sum_{n=0}^{\infty}(-2x)^{n}=\sum_{n=0}^{\infty}\left% (4(7)^{n}+3(-2)^{n}\right)x^{n}

Ce qui nous donne finalement:

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.3.3.

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

{an=12⁢an−1−48⁢an−2+64⁢an−3,∀n≥3a0=2a1=56a2=640\displaystyle\left\{\begin{array}[]{l}a_{n}=12a_{n-1}-48a_{n-2}+64a_{n-3},% \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \forall n\geq 3% \\ a_{0}=2\\ a_{1}=56\\ a_{2}=640\end{array}\right.

Pour ce faire, nous allons utiliser la méthode des fonctions génératrices. On a donc:

∑n=0∞an⁢xn\displaystyle\displaystyle\sum_{n=0}^{\infty}a_{n}x^{n} =\displaystyle\displaystyle= 2+56⁢x+640⁢x2+∑n=3∞an⁢xn=2+56⁢x+640⁢x2+∑n=3∞(12⁢an−1−48⁢an−2+64⁢an−3)⁢xn\displaystyle\displaystyle 2+56x+640x^{2}+\sum_{n=3}^{\infty}a_{n}x^{n}=2+56x+% 640x^{2}+\sum_{n=3}^{\infty}\left(12a_{n-1}-48a_{n-2}+64a_{n-3}\right)x^{n}
=\displaystyle\displaystyle= 2+56⁢x+640⁢x2+12⁢x⁢∑n=3∞an−1⁢xn−1−48⁢x2⁢∑n=3∞an−2⁢xn−2+64⁢x3⁢∑n=3∞an−3⁢xn−3\displaystyle\displaystyle 2+56x+640x^{2}+12x\sum_{n=3}^{\infty}a_{n-1}x^{n-1}% -48x^{2}\sum_{n=3}^{\infty}a_{n-2}x^{n-2}+64x^{3}\sum_{n=3}^{\infty}a_{n-3}x^{% n-3}
=\displaystyle\displaystyle= 2+56⁢x+640⁢x2+12⁢x⁢∑n=2∞an⁢xn−48⁢x2⁢∑n=1∞an⁢xn+64⁢x3⁢∑n=0∞an⁢xn\displaystyle\displaystyle 2+56x+640x^{2}+12x\sum_{n=2}^{\infty}a_{n}x^{n}-48x% ^{2}\sum_{n=1}^{\infty}a_{n}x^{n}+64x^{3}\sum_{n=0}^{\infty}a_{n}x^{n}
=\displaystyle\displaystyle= 2+56⁢x+640⁢x2+12⁢x⁢∑n=0∞an⁢xn−48⁢x2⁢∑n=0∞an⁢xn+64⁢x3⁢∑n=0∞an⁢xn−12⁢x⁢(a0+a1⁢x)+48⁢x2⁢(a0)\displaystyle\displaystyle 2+56x+640x^{2}+12x\sum_{n=0}^{\infty}a_{n}x^{n}-48x% ^{2}\sum_{n=0}^{\infty}a_{n}x^{n}+64x^{3}\sum_{n=0}^{\infty}a_{n}x^{n}-12x(a_{% 0}+a_{1}x)+48x^{2}(a_{0})
=\displaystyle\displaystyle= 2+32⁢x+64⁢x2+12⁢x⁢∑n=0∞an⁢xn−48⁢x2⁢∑n=0∞+64⁢x3⁢∑n=0∞an⁢xn\displaystyle\displaystyle 2+32x+64x^{2}+12x\sum_{n=0}^{\infty}a_{n}x^{n}-48x^% {2}\sum_{n=0}^{\infty}+64x^{3}\sum_{n=0}^{\infty}a_{n}x^{n}

En isolant la somme, on obtient donc:

∑n=0∞an⁢xn=2+32⁢x+64⁢x21−12⁢x+48⁢x2−64⁢x3=2+32⁢x+64⁢x2(1−4⁢x)3\displaystyle\sum_{n=0}^{\infty}a_{n}x^{n}=\frac{2+32x+64x^{2}}{1-12x+48x^{2}-% 64x^{3}}=\frac{2+32x+64x^{2}}{(1-4x)^{3}}

Nous allons maintenant appliquer la méthode de décomposition en fractions partielles:

2+32⁢x+64⁢x2(1−4⁢x)3=A1−4⁢x+B(1−4⁢x)2+C(1−4⁢x)3=A⁢(1−4⁢x)2+B⁢(1−4⁢x)+C(1−4⁢x)3=A⁢(1−8⁢x+16⁢x2)+B⁢(1−4⁢x)+C(1−4⁢x)3\displaystyle\frac{2+32x+64x^{2}}{(1-4x)^{3}}=\frac{A}{1-4x}+\frac{B}{(1-4x)^{% 2}}+\frac{C}{(1-4x)^{3}}=\frac{A(1-4x)^{2}+B(1-4x)+C}{(1-4x)^{3}}=\frac{A(1-8x% +16x^{2})+B(1-4x)+C}{(1-4x)^{3}}

Ce qui nous permet d’obtenir le système d’équations linéaires suivant:

{16⁢A=64−8⁢A−4⁢B=32A+B+C=2\displaystyle\left\{\begin{array}[]{l}16A=64\\ -8A-4B=32\\ A+B+C=2\end{array}\right.

qui est relativement facile à résoudre. On obtient donc A=4,B=−16\displaystyle A=4,B=-16 et C=14\displaystyle C=14. Notre fonction génératrice devient donc:

∑n=0∞an⁢xn\displaystyle\displaystyle\sum_{n=0}^{\infty}a_{n}x^{n} =\displaystyle\displaystyle= 41−4⁢x−16(1−4⁢x)2+14(1−4⁢x)3=∑n=0∞4⁢(4⁢x)n−∑n=0∞16⁢⟨2n⟩⁢(4⁢x)n+∑n=0∞14⁢⟨3n⟩⁢(4⁢x)n\displaystyle\displaystyle\frac{4}{1-4x}-\frac{16}{(1-4x)^{2}}+\frac{14}{(1-4x% )^{3}}=\sum_{n=0}^{\infty}4(4x)^{n}-\sum_{n=0}^{\infty}16\left\langle 2\atop n% \right\rangle(4x)^{n}+\sum_{n=0}^{\infty}14\left\langle 3\atop n\right\rangle(% 4x)^{n}
=\displaystyle\displaystyle= ∑n=0∞[4⋅4n−16⁢(n+1)⋅4n+14⁢(n+2)⁢(n+1)2⋅4n]⁢xn\displaystyle\displaystyle\sum_{n=0}^{\infty}\left[4\cdot 4^{n}-16(n+1)\cdot 4% ^{n}+14\frac{(n+2)(n+1)}{2}\cdot 4^{n}\right]x^{n}

Ce qui nous permet d’obtenir:

an\displaystyle\displaystyle a_{n} =\displaystyle\displaystyle= 4⋅4n−16⁢(n+1)⋅4n+14⁢(n+2)⁢(n+1)2⋅4n\displaystyle\displaystyle 4\cdot 4^{n}-16(n+1)\cdot 4^{n}+14\frac{(n+2)(n+1)}% {2}\cdot 4^{n}
=\displaystyle\displaystyle= 4⋅4n−16⁢n⋅4n−16⋅4n+7⁢n2⋅4n+21⁢n⋅4n+14⋅4n\displaystyle\displaystyle 4\cdot 4^{n}-16n\cdot 4^{n}-16\cdot 4^{n}+7n^{2}% \cdot 4^{n}+21n\cdot 4^{n}+14\cdot 4^{n}
=\displaystyle\displaystyle= 4n⁢(2+5⁢n+7⁢n2)\displaystyle\displaystyle 4^{n}(2+5n+7n^{2})
Exemple 7.3.4.

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

{an=7⁢an−1−9⁢an−2+63⁢an−3,∀n≥3a0=9a1=35a2=209\displaystyle\left\{\begin{array}[]{l}a_{n}=7a_{n-1}-9a_{n-2}+63a_{n-3},% \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \forall n\geq 3% \\ a_{0}=9\\ a_{1}=35\\ a_{2}=209\end{array}\right.

Pour ce faire, nous allons utiliser la méthode des fonctions génératrices. Nous avons donc:

∑n=0∞an⁢xn\displaystyle\displaystyle\sum_{n=0}^{\infty}a_{n}x^{n} =\displaystyle\displaystyle= 9+35⁢x+209⁢x2+∑n=3∞an⁢xn\displaystyle\displaystyle 9+35x+209x^{2}+\sum_{n=3}^{\infty}a_{n}x^{n}
=\displaystyle\displaystyle= 9+35⁢x+209⁢x2+∑n=3∞(7⁢an−1−9⁢an−2+63⁢an−3)⁢xn\displaystyle\displaystyle 9+35x+209x^{2}+\sum_{n=3}^{\infty}(7a_{n-1}-9a_{n-2% }+63a_{n-3})x^{n}
=\displaystyle\displaystyle= 9+35⁢x+209⁢x2+7⁢x⁢∑n=2∞an⁢xn−9⁢x2⁢∑n=1∞an⁢xn+63⁢x3⁢∑n=0∞an⁢xn\displaystyle\displaystyle 9+35x+209x^{2}+7x\sum_{n=2}^{\infty}a_{n}x^{n}-9x^{% 2}\sum_{n=1}^{\infty}a_{n}x^{n}+63x^{3}\sum_{n=0}^{\infty}a_{n}x^{n}
=\displaystyle\displaystyle= 9+35⁢x+209⁢x2+(7⁢x−9⁢x2+63⁢x3)⁢(∑n=0∞an⁢xn)−63⁢x−245⁢x2+81⁢x2\displaystyle\displaystyle 9+35x+209x^{2}+(7x-9x^{2}+63x^{3})\left(\sum_{n=0}^% {\infty}a_{n}x^{n}\right)-63x-245x^{2}+81x^{2}
=\displaystyle\displaystyle= (7⁢x−9⁢x2+63⁢x3)⁢(∑n=0∞an⁢xn)+9−28⁢x+45⁢x2\displaystyle\displaystyle(7x-9x^{2}+63x^{3})\left(\sum_{n=0}^{\infty}a_{n}x^{% n}\right)+9-28x+45x^{2}

En isolant la série, nous obtenons donc:

∑n=0∞an⁢xn=9−28⁢x+45⁢x21−7⁢x+9⁢x2−63⁢x3\displaystyle\sum_{n=0}^{\infty}a_{n}x^{n}=\frac{9-28x+45x^{2}}{1-7x+9x^{2}-63% x^{3}}

Nous devons maintenant appliquer la méthode de décomposition en fractions partielles. Pour ce faire, nous devons premièrement factoriser le dénominateur. Ici, nous allons utiliser une petite astuce. Par le théorème des racines rationnelles, nous savons que les racines rationnelles (s’il y en a) auront la forme 1k\displaystyle\frac{1}{k} avec k\displaystyle k un diviseur entier de 63\displaystyle 63. Travailler avec les fractions peut cependant sembler un peu difficile. Nous allons donc faire la transformation suivante:

p⁢(x)=1−7⁢x+9⁢x2−63⁢x3⇒q⁢(x)=x3⁢p⁢(1x)=x3−7⁢x2+9⁢x−63\displaystyle p(x)=1-7x+9x^{2}-63x^{3}\leavevmode\nobreak\ \leavevmode\nobreak% \ \leavevmode\nobreak\ \Rightarrow\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ q(x)=x^{3}p\left(\frac{1}{x}\right)=x^{3}-7x^{2}+9x-63

En trouvant les racines du polynôme q⁢(x)\displaystyle q(x), nous aurons donc trouvé l’inverse des racines du polynôme p⁢(x)\displaystyle p(x). Pour trouver les racines du polynôme q⁢(x)\displaystyle q(x), nous devons tester les différents diviseurs réels de 63\displaystyle 63. Comme 63=32⋅71\displaystyle 63=3^{2}\cdot 7^{1}, il est facile de voir que 63\displaystyle 63 ne possède que 6\displaystyle 6 diviseurs positifs (et autant négatif). Par la règle des signes de Descartes, nous pouvons cependant affirmer que toutes les racines sont positives. Nous n’avons donc que 6\displaystyle 6 valeurs à tester: 1,3,7,9,21,63\displaystyle 1,3,7,9,21,63. À partir de cette liste, nous trouvons facilement que q⁢(7)=0\displaystyle q(7)=0, ce qui signifie que 17\displaystyle\frac{1}{7} est une racine du polynôme p⁢(x)\displaystyle p(x). Le polynôme p⁢(x)\displaystyle p(x) peut donc être divisé par 1−7⁢x\displaystyle 1-7x.

\polylongdiv−63⁢x3+9⁢x2−7⁢x+1−7⁢x+1\displaystyle\polylongdiv{-63x^{3}+9x^{2}-7x+1}{-7x+1}

Comme le polynôme 1+9⁢x2\displaystyle 1+9x^{2} est irréductible, notre décomposition en fractions partielles aura la forme

∑n=0∞an⁢xn\displaystyle\displaystyle\sum_{n=0}^{\infty}a_{n}x^{n} =\displaystyle\displaystyle= 9−28⁢x+45⁢x21−7⁢x+9⁢x2−63⁢x3=A1−7⁢x+B⁢x+C1+9⁢x2\displaystyle\displaystyle\frac{9-28x+45x^{2}}{1-7x+9x^{2}-63x^{3}}=\frac{A}{1% -7x}+\frac{Bx+C}{1+9x^{2}}
=\displaystyle\displaystyle= A⁢(1+9⁢x2)+(B⁢x+C)⁢(1−7⁢x)(1−7⁢x)⁢(1+9⁢x2)=(A+C)+(B−7⁢C)⁢x+(9⁢A−7⁢B)⁢x2(1−7⁢x)⁢(1+9⁢x2)\displaystyle\displaystyle\frac{A(1+9x^{2})+(Bx+C)(1-7x)}{(1-7x)(1+9x^{2})}=% \frac{(A+C)+(B-7C)x+(9A-7B)x^{2}}{(1-7x)(1+9x^{2})}

Ceci nous amène donc au système d’équations linéaires suivant:

{A+C=9B−7⁢C=−289⁢A−7⁢B=45\displaystyle\left\{\begin{array}[]{l}A+C=9\\ B-7C=-28\\ 9A-7B=45\end{array}\right.

que l’on peut résoudre à l’aide par exemple de la méthode de Gauss, ce qui nous donne:

(101901−7−289−7045)∼9⁢L1−L3→L3(101901−7−2807936)∼L3−7⁢L2→L3(101901−7−280058232)\displaystyle\left(\begin{array}[]{@{}*{3}{c}|c@{}}1&0&1&9\\ 0&1&-7&-28\\ 9&-7&0&45\end{array}\right)\stackrel{{\scriptstyle 9L_{1}-L_{3}\rightarrow L_{% 3}}}{{\sim}}\left(\begin{array}[]{@{}*{3}{c}|c@{}}1&0&1&9\\ 0&1&-7&-28\\ 0&7&9&36\end{array}\right)\stackrel{{\scriptstyle L_{3}-7L_{2}\rightarrow L_{3% }}}{{\sim}}\left(\begin{array}[]{@{}*{3}{c}|c@{}}1&0&1&9\\ 0&1&-7&-28\\ 0&0&58&232\end{array}\right)

Ce qui nous permet d’obtenir A=5,B=0\displaystyle A=5,B=0 et C=4\displaystyle C=4. En retournant en notre fonction génératrice, nous obtenons donc:

∑n=0∞an⁢xn\displaystyle\displaystyle\sum_{n=0}^{\infty}a_{n}x^{n} =\displaystyle\displaystyle= 51−7⁢x+41+9⁢x2\displaystyle\displaystyle\frac{5}{1-7x}+\frac{4}{1+9x^{2}}
=\displaystyle\displaystyle= 5⁢∑n=0∞(7⁢x)n+4⁢∑n=0∞(−9⁢x2)n\displaystyle\displaystyle 5\sum_{n=0}^{\infty}(7x)^{n}+4\sum_{n=0}^{\infty}(-% 9x^{2})^{n}
=\displaystyle\displaystyle= 5⁢∑n=0∞7n⁢xn+4⁢∑n=0∞(−1)n⁢32⁢n⁢x2⁢n\displaystyle\displaystyle 5\sum_{n=0}^{\infty}7^{n}x^{n}+4\sum_{n=0}^{\infty}% (-1)^{n}3^{2n}x^{2n}
=\displaystyle\displaystyle= ∑n=0∞5⋅72⁢n⁢x2⁢n+∑n=0∞5⋅72⁢n+1⁢x2⁢n+1+∑n=0∞4⁢(−1)n⁢32⁢n⁢x2⁢n\displaystyle\displaystyle\sum_{n=0}^{\infty}5\cdot 7^{2n}x^{2n}+\sum_{n=0}^{% \infty}5\cdot 7^{2n+1}x^{2n+1}+\sum_{n=0}^{\infty}4(-1)^{n}3^{2n}x^{2n}
=\displaystyle\displaystyle= ∑n=0∞(5⋅72⁢n+4⁢(−1)n⁢32⁢n)⏟termes pairs⁢x2⁢n+∑n=0∞(5⋅72⁢n+1)⏟termes impairs⁢x2⁢n+1\displaystyle\displaystyle\sum_{n=0}^{\infty}\underbrace{\left(5\cdot 7^{2n}+4% (-1)^{n}3^{2n}\right)}_{\textrm{termes pairs}}x^{2n}+\sum_{n=0}^{\infty}% \underbrace{\left(5\cdot 7^{2n+1}\right)}_{\textrm{termes impairs}}x^{2n+1}

Ce qui nous permet d’obtenir la solution suivante:

an={5⋅7n+4⁢(−1)n/2⋅3n si n est pair5⋅7n si n est impair\displaystyle a_{n}=\left\{\begin{array}[]{ll}5\cdot 7^{n}+4(-1)^{\nicefrac{{n% }}{{2}}}\cdot 3^{n}\nobreak\leavevmode\nobreak\leavevmode\nobreak\leavevmode&% \textrm{ si $\displaystyle n$ est pair}\\ 5\cdot 7^{n}\nobreak\leavevmode\nobreak\leavevmode\nobreak\leavevmode&\textrm{% si $\displaystyle n$ est impair}\end{array}\right.