7.6 La méthode des fonctions génératrices exponentielles

Jusqu’à présent, nous nous sommes intéresser aux récurrences à coefficients constants. Les techniques que nous avons vu jusqu’à présent ne fonctionne pas très bien lorsque ce n’est pas le cas. Nous allons maintenant voir une autre approche aux fonctions génératrices permettant de résoudre certaine équation qui n’ont pas des coefficients constants. L’idée est de réécrire une suite an\displaystyle a_{n} sous la forme d’une fonction génératrice exponentielle. C’est à dire sous la forme:

∑n=0∞an⁢xnn!\displaystyle\sum_{n=0}^{\infty}a_{n}\frac{x^{n}}{n!}
Exemple 7.6.1.

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

{an=n⁢an−1,∀n≥1a0=1\displaystyle\left\{\begin{array}[]{l}a_{n}=na_{n-1},\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \forall n\geq 1\\ a_{0}=1\end{array}\right.

En applicant les fonctions génératrices exponentielles on obtient:

∑n=0∞an⁢xnn!=1+∑n=1∞n⁢an−1⁢xnn!=1+x⁢∑n=1∞an−1⁢xn−1(n−1)!=1+x⁢∑n=0∞an⁢xnn!\displaystyle\sum_{n=0}^{\infty}a_{n}\frac{x^{n}}{n!}=1+\sum_{n=1}^{\infty}na_% {n-1}\frac{x^{n}}{n!}=1+x\sum_{n=1}^{\infty}\frac{a_{n-1}x^{n-1}}{(n-1)!}=1+x% \sum_{n=0}^{\infty}a_{n}\frac{x^{n}}{n!}

En isolant la série, on obtient:

(1−x)⁢∑n=0∞an⁢xnn!=1⇒∑n=0∞an⁢xnn!=11−x=∑n=0∞xn=∑n=0∞n!⁢xnn!\displaystyle(1-x)\sum_{n=0}^{\infty}a_{n}\frac{x^{n}}{n!}=1\leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \Rightarrow\leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \sum_{n=0}^{\infty}a_{n}% \frac{x^{n}}{n!}=\frac{1}{1-x}=\sum_{n=0}^{\infty}x^{n}=\sum_{n=0}^{\infty}n!% \frac{x^{n}}{n!}

On obtient donc que an=n!\displaystyle a_{n}=n! pour tout n≥0\displaystyle n\geq 0.

Remarquez que l’exemple précédent était particulièrement simple et est en fait la définition récursive de la factorielle. La méthode peut cependant être utiliser dans des cas plus compliqué. C’est ce que nous allons faire immédiatement.

Exemple 7.6.2.

On veut trouver une formule explicite pour la suite définie par récurrence suivante:

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

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

∑n=0∞an⁢xnn!\displaystyle\displaystyle\sum_{n=0}^{\infty}\frac{a_{n}x^{n}}{n!} =\displaystyle\displaystyle= 3+∑n=1∞(n⁢an−1+2)⁢xnn!=3+∑n=1∞n⁢an−1⁢xnn!+∑n=1∞2⁢xnn!=3+x⁢∑n=1∞an−1⁢xn−1(n−1)!+∑n=0∞2⁢xnn!−2\displaystyle\displaystyle 3+\sum_{n=1}^{\infty}\frac{(na_{n-1}+2)x^{n}}{n!}=3% +\sum_{n=1}^{\infty}\frac{na_{n-1}x^{n}}{n!}+\sum_{n=1}^{\infty}\frac{2x^{n}}{% n!}=3+x\sum_{n=1}^{\infty}\frac{a_{n-1}x^{n-1}}{(n-1)!}+\sum_{n=0}^{\infty}% \frac{2x^{n}}{n!}-2
=\displaystyle\displaystyle= 1+x⁢∑n=0∞an⁢xnn!+2⁢ex\displaystyle\displaystyle 1+x\sum_{n=0}^{\infty}\frac{a_{n}x^{n}}{n!}+2e^{x}

En isolant la série, on obtient donc:

∑n=0∞an⁢xnn!\displaystyle\displaystyle\sum_{n=0}^{\infty}\frac{a_{n}x^{n}}{n!} =\displaystyle\displaystyle= 1+2⁢ex1−x=11−x+2⁢ex⁢11−x=∑n=0∞xn+2⁢(∑n=0∞xnn!)⁢(∑n=0∞xn)=∑n=0∞xn+2⁢∑n=0∞(∑k=0n1k!)⁢xn\displaystyle\displaystyle\frac{1+2e^{x}}{1-x}=\frac{1}{1-x}+2e^{x}\frac{1}{1-% x}=\sum_{n=0}^{\infty}x^{n}+2\left(\sum_{n=0}^{\infty}\frac{x^{n}}{n!}\right)% \left(\sum_{n=0}^{\infty}x^{n}\right)=\sum_{n=0}^{\infty}x^{n}+2\sum_{n=0}^{% \infty}\left(\sum_{k=0}^{n}\frac{1}{k!}\right)x^{n}
=\displaystyle\displaystyle= ∑n=0∞[1+2⁢∑k=0n1k!]⁢xn=∑n=0∞[n!+2⁢∑k=0nn!k!]⁢xnn\displaystyle\displaystyle\sum_{n=0}^{\infty}\left[1+2\sum_{k=0}^{n}\frac{1}{k% !}\right]x^{n}=\sum_{n=0}^{\infty}\left[n!+2\sum_{k=0}^{n}\frac{n!}{k!}\right]% \frac{x^{n}}{n}

Ce qui nous permet donc d’obtenir que an=n!+2⁢∑k=0nn!k!\displaystyle a_{n}=n!+2\sum_{k=0}^{n}\frac{n!}{k!} pour tout n≥0\displaystyle n\geq 0. Remarquez que si n\displaystyle n est grand, nous obtenons que an≈n!+2⁢n!⁢e\displaystyle a_{n}\approx n!+2n!e.