On commence avec cette curieuse question
Quelle est la somme, si elle existe, de
\begin{align*} &0,\!1 \\ \\ +\ &0,\!01 \\ \\ +\ &0,\!002 \\ \\ +\ &0,\!0003 \\ \\ +\ &0,\!00005 \\ \\ +\ &0,\!000008 \\ \\ +\ &0,\!0000013 \\ \\ +\ &\dots \end{align*}
On reconnaît les termes de la suite de Fibonacci, multipliés par des puissances de \(10\) correspondant à leur rang. Cette somme existe et, ô surprise, il s’agit en plus d’un nombre rationnel !
Dans ce billet, on répondra à cette question et on fait même un peu plus, pour la chance. On reprend, d’abord, la très célèbre suite de Fibonacci\[F_{0} = 0, \quad F_{1} = 1,\] \[F_{n} = F_{n-1} + F_{n-2}\]et on cherche ce qu’on appelle la fonction génératrice de la suite. Cette fonction génératrice nous permettra plus tard de trouver une expression de forme fermée (closed form pour les anglophones) pour calculer la valeur du \(n\)e terme de la suite (sans calculer tous les termes précédents avec la formule par récurrence). On s’intéressera enfin à la réponse à la question posée en préambule.
On commence donc par chercher une fonction génératrice de la suite, c’est-à-dire qu’on cherche une fonction polynomiale \(f\) \[f(z) = F_{0} + F_{1}z + F_{2}z^2 + F_{3}z^3 + F_{4}z^4 + F_{5}z^5 + \ \dots\]dont les coefficients des termes en \(z\) sont justement les termes de la suite de Fibonacci. Comme il existe une infinité de termes pour la suite de Fibonacci, la fonction possède elle aussi une infinité de termes. Et comme en plus\[F_{0}, \ F_{1}, \ F_{2}, \ \dots\]sont tous des entiers positifs, et même que\[F_{0} \leq F_{1}\leq F_{2}\leq \ \dots\]on peut déjà se demander si cette fonction converge pour certaines valeurs de \(z\) autres que, par exemple, \(z = 0\). S’il est facile de vérifier que \(f(0) = 0\), il est aussi facile de vérifier que la série diverge pour d’autres valeurs de \(z\): d’un coup d’œil, on constate qu’elle diverge pour des valeurs de \(z\) supérieure ou égale à \(1\). On laisse cependant pour l’instant cette question plus technique en plan, avant d’y répondre plus tard, lorsqu’on aura exprimé la fonction sous une forme plus pratique. On multiplie deux fois la fonction, d’abord par \(z\) puis par \(z^{2}\). \begin{align*}f(z) &= F_{0} + F_{1}z + F_{2}z^2 + F_{3}z^3 + F_{4}z^4 + F_{5}z^5 + \ \dots \\ \\ zf(z) &= \phantom{F_{0} + }\ \, F_{0}z + F_{1}z^2 + F_{2}z^3 + F_{3}z^4 + F_{4}z^5 + \ \dots \\ \\ z^2f(z) &= \phantom{F_{0} + F_{1}z + }\ \, F_{0}z^2 + F_{1}z^3 + F_{2}z^4 + F_{3}z^5 + \ \dots \end{align*}On soustrait les deux équations du bas à la première. On remarque que tous les termes à partir de \(z^{2}\) disparaissent. En effet, en se rappelant la définition même des termes de la suite de Fibonacci, on a, par exemple, pour les termes en \(z^{2}\) seulement \begin{align*}F_{2}z^{2}-F_{1}z^{2}-F_{0}z^{2} &= \left(F_{2}-F_{1}-F_{0}\right)z^{2} \\ \\ &=\left(F_{1} + F_{0}-F_{1}-F_{0}\right)z^{2} \\ \\ &=0\end{align*}puis pour les termes en \(z^{3}\) \begin{align*}F_{3}z^{3}-F_{2}z^{3}-F_{1}z^{3} &= \left(F_{3}-F_{2}-F_{1}\right)z^{3} \\ \\ &=\left(F_{2} + F_{1}-F_{2}-F_{1}\right)z^{3} \\ \\ &=0\end{align*}et ainsi de suite… De plus, comme \[F_{0} = 0\]il ne reste à la fin que \[\left(F_{1}-F_{0}\right)z\]ce qui est tout simplement \[\left(F_{1}-F_{0}\right)z = (1-0)z = z\]Ah ! On a donc\[f(z)-zf(z)-z^{2}f(z) = z\]et en effectuant la mise en évidence\[f(x)\left(1-z-z^{2}\right)=z\]
on obtient une nouvelle expression pour la fonction \(f\), une forme fermée de \(f\) \[f(z) = \frac{z}{1-z-z^{2}}\]Avant de continuer, une petite division avec crochet fort distrayante illustre de belle manière cette dernière égalité
Il n’y a pas à dire : ces coefficients sont les termes de la suite de Fibonacci !
On tente ensuite d’exprimer la fraction de droite comme une somme de “fractions partielles”. Afin d’y arriver, on utilise une fonction génératrice plus simple, telle que\[\frac{1}{1-\alpha z}=1 +\alpha z + \alpha^{2}z^{2} + \alpha^{3}z^{3} + \alpha^{4}z^{3} + \alpha^{5}z^{5} + \, \dots\]On pose\[f(z) = \frac{z}{1-z-z^{2}} = \frac{A}{1-\alpha z} + \frac{B}{1-\beta z}\]En développant la partie de droite on obtient\[\frac{A}{1-\alpha z} + \frac{B}{1-\beta z} = A\sum_{n=0}^{\infty}\alpha^{n}z^{n} + B\sum_{n=0}^{\infty}\beta^{n}z^{n}\]ou de manière équivalente\[\frac{A}{1-\alpha z} + \frac{B}{1-\beta z} = \sum_{n=0}^{\infty}\left(A\alpha^{n} + B\beta^{n}\right)z^{n}\]En outre,\[f(z)=\sum_{n=0}^{\infty}F_{n}z^{n} = \sum_{n=0}^{\infty}\left(A\alpha^{n} + B\beta^{n}\right) z^{n}\]et les expressions\[A\alpha^{n} + B\beta^{n}\]correspondent aux coefficients \(F_{n}\) des \(z^{n}\), c’est-à-dire aux termes de la suite de Fibonacci. On essaie donc de trouver des \(A\), \(B\), \(\alpha\) et \(\beta\) tels que\[\frac{A}{1-\alpha z}+\frac{B}{1-\beta z}=\frac{z}{1-z-z^{2}}\]En mettant la somme à gauche sur le même dénominateur, on obtient\begin{align*}\frac{A}{1-\alpha z} + \frac{B}{1-\beta z} &= \frac{A\left(1-\beta z\right)}{\left(1-\alpha z\right)\left(1-\beta z\right)} + \frac{B\left(1-\alpha z\right)}{\left(1-\beta z\right)\left(1-\alpha z\right)} \\ \\ &= \frac{A-A\beta z + B-B\alpha z}{\left(1-\alpha z\right)\left(1-\beta z\right)} \\ \\ &=\frac{\left(A+B\right)-\left(A\beta + \beta\alpha\right)z}{\left(1-\alpha z\right)\left(1-\beta z\right)}\end{align*}c’est-à-dire qu’on a \[\frac{z}{1-z-z^{2}} = \frac{\left(A+B\right)-\left(A\beta + \beta\alpha\right)z}{\left(1-\alpha z\right)\left(1-\beta z\right)}\]et qu’il faut résoudre le système d’équations suivant\begin{align*}1-z-z^{2}&=\left(1-\alpha z\right)\left(1-\beta z\right) \\ \\ z &= \left(A + B\right)-\left(A\beta + B\alpha\right)z\end{align*}En examinant la première équation, on peut s’attaquer aux valeurs de α et β en tentant de factoriser le trinôme\[1-z-z^{2}\]dont le terme constant est \(1\). En complétant le carré et en factorisant la différence de carrés, on obtient\begin{align*}1-z-z^{2}&= 1-z+\frac{1}{4}z^{2}-\frac{1}{4}z^{2}-z^{2}\\ \\ &=\left(1-\frac{1}{2}z\right)^{2}-\frac{5}{4}z^{2}\\ \\ &=\left(1-\frac{1}{2}z\right)^{2}-\left(\frac{\sqrt{5}}{2}z\right)^{2} \\ \\ &=\left(1-\frac{1+\sqrt{5}}{2}z\right)\left(1-\frac{1-\sqrt{5}}{2}z\right)\end{align*}et cela nous donne des valeurs pour \(\alpha\) et \(\beta\) \[\alpha = \frac{1+\sqrt{5}}{2}, \quad \beta = \frac{1-\sqrt{5}}{2}\]Le premier nombre est bien connu, c’est le nombre d’or, tel que vu ici par exemple. On note généralement le nombre d’or avec la lettre grecque \(\varphi\). On remarque au passage que\[\frac{1-\sqrt{5}}{2} = -\varphi^{-1}\]Puisque\[\alpha=\varphi,\quad\beta = -\varphi^{-1}\]il ne reste qu’à trouver A et B dans\[z = \left(A + B \right)-\left(A\beta + B\alpha\right)z\]En posant \(z = 0\), on trouve facilement que \(B = -A\). Du coup, l’équation précédente devient\begin{align*}z&=\big(A+\left(-A\right)\big)-\big(\left(-A\right)\varphi^{-1}-A\varphi\big)z \\ \\ &=\left(A\varphi^{-1} + A\varphi\right)z\end{align*}En divisant par \(z \neq 0\) \[1 = A\varphi^{-1}+A\varphi\]puis en effectuant la mise en évidence de \(A\),\[1=A\left(\varphi^{-1}+\varphi\right)\]on obtient\[\frac{1}{\varphi^{-1}+\varphi}=A\]Un peu d’algèbre élémentaire nous permet d’écrire d’abord ceci\begin{align*}A &=\frac{1}{\varphi^{-1} + \varphi} \\ \\ &=\frac{\varphi}{1+\varphi^{2}} \\ \\ &= \frac{\frac{1+\sqrt{5}}{2}}{1 + \frac{6+2\sqrt{5}}{4}} \\ \\ &=\frac{1+\sqrt{5}}{5+\sqrt{5}}\end{align*}puis de simplifier davantage \begin{align*} A &= \frac{1+\sqrt{5}}{5 + \sqrt{5}} \\ \\ &=\frac{1+\sqrt{5}}{5+\sqrt{5}} \cdot \frac{1-\sqrt{5}}{1-\sqrt{5}} \\ \\ &=\frac{1-5}{5-5\sqrt{5}+\sqrt{5}-5} \\ \\ &=\frac{-4}{-4\sqrt{5}} \\ \\ &=\frac{1}{\sqrt{5}}\end{align*}On trouve par le fait même que\[B=-\frac{1}{\sqrt{5}}\]Cela nous permet de de remplacer \(A\), \(B\), \(\alpha\) et \(\beta\) d’abord dans\[\frac{1}{1-\alpha z} + \frac{B}{1-\beta z} = \frac{z}{1-z-z^{2}}\]afin d’obtenir la fonction \(f\) comme somme de fractions partielles \begin{align*} f(z) &= \frac{\frac{1}{\sqrt{5}}}{1-\varphi z} + \frac{\frac{-1}{\sqrt{5}}}{1+\varphi^{-1}z} \\ \\ &=\left(\frac{1}{\sqrt{5}}\right)\left(\frac{1}{1-\varphi z}-\frac{1}{1+\varphi^{-1}z}\right) \end{align*}Et comme\[f(z)=A\sum_{n=0}^{\infty}\alpha^{n}z^{n}+B\sum_{n=0}^{\infty}\beta^{n}z^{n}\]c’est-à-dire que\[f(z) = \frac{1}{\sqrt{5}}\sum_{n=0}^{\infty}\varphi^{n}z^{n}-\frac{1}{\sqrt{5}}\sum_{n=0}^{\infty}\left(-\varphi^{-1}\right)^{n}z^{n}\]on peut enfin trouver pour quelles valeurs de \(z\) est-ce que la fonction existe, autrement dit, pour quelles valeurs de \(z\) est-ce que \[\sum_{n=0}^{\infty}\left(\frac{1}{\sqrt{5}}\varphi^{n}+\frac{-1}{\sqrt{5}}\left(-\varphi^{-1}\right)^{n}\right)z^{n}=\frac{1}{\sqrt{5}}\sum_{n=0}^{\infty}\varphi^{n}z^{n}-\frac{1}{\sqrt{5}}\sum_{n=0}^{\infty}\left(-\varphi^{-1}\right)^{n}z^{n}\]converge. La première somme converge si \[\lim_{n\to\infty}\left|\frac{\varphi^{n+1}z^{n+1}}{\varphi^{n}z^{n}}\right|<1\]On obtient donc\begin{align*}\left|\varphi z\right|<1 \\ \\ -1<\varphi z<1 \\ \\ -1<\frac{1+\sqrt{5}}{2}z<1 \\ \\ \frac{-2}{1+\sqrt{5}}<z<\frac{2}{1+\sqrt{5}}\end{align*}La deuxième somme converge si \[\lim_{n\to \infty}\left|\frac{\left(-\varphi^{-1}\right)^{n+1}z^{n+1}}{\left(-\varphi^{-1}\right)^{n}z^{n}}\right|<1\]et on obtient\begin{align*}\left|-\varphi^{-1}z\right|<1 \\ \\ -1<-\varphi^{-1}z<1 \\ \\ -1<\frac{1-\sqrt{5}}{2}z<1 \\ \\ \frac{2}{1-\sqrt{5}}<z<\frac{-2}{1-\sqrt{5}}\end{align*}Puisque \[\frac{2}{1-\sqrt{5}}<\frac{-2}{1+\sqrt{5}}<z<\frac{2}{1+\sqrt{5}}<\frac{-2}{1-\sqrt{5}}\]on trouve que la série converge seulement pour des valeurs de \(z\)entre \[\frac{-2}{1+\sqrt{5}}<z<\frac{2}{1+\sqrt{5}}\]Par ailleurs, on obtient également un résultat fort intéressant, la formule pour le \(n\)ième terme de la suite de Fibonacci, les coefficients de \(z^{n}\) dans \(f(z)\). En remplaçant \(A\), \(B\), \(\alpha\) et \(\beta\) dans \[F_{n} = A\alpha^{n} + B\beta^{n}\]on a \[F_{n} = \frac{1}{\sqrt{5}}\varphi^{n} + \left(-\frac{1}{\sqrt{5}}\right)\left(-\varphi^{-1}\right)^{n}\]qu’on peut réécrire comme \begin{align*}F_{n} &= \frac{1}{\sqrt{5}}\varphi^{n}+\left(-\frac{1}{\sqrt{5}}\right)\left(-\varphi^{-1}\right)^{n} \\ \\ &= \left(\frac{1}{\sqrt{5}}\right)\left(\varphi^{n}-\left(-\varphi^{-1}\right)^{n}\right) \\ \\ &=\left(\frac{1}{\sqrt{5}}\right)\left(\varphi^{n}-\left(-1\right)^{n}\right)\left(\varphi^{-1}\right)^{n} \\ \\ &=\frac{\varphi^{n}-\left(-1\right)^{n}\varphi^{-n}}{\sqrt{5}}\end{align*}formule qui a été découverte par Daniel Bernoulli en 1728 et ensuite tombée dans l’oubli jusqu’à ce que Jacques Binet la redécouvre en 1843. Un peu d’algèbre nous permet de la transformer sous d’autres formes couramment rencontrées dans la littérature et sur internet.
On s’attarde enfin à la question du début du billet, à savoir vers quel nombre converge la somme suivante\[\sum_{n=0}^{\infty}\frac{F_{n}}{10^{n}} = 0 + 0,\!1 + 0,\!01 + 0,\!002 + 0,\!0003 + 0,\!00005 + 0,\!000008 + 0,\!0000013 + \ \dots\]Aussi étonnant que cela puisse paraître, la somme existe et c’est un nombre rationnel de période \(44\). C’est \[\sum_{n=0}^{\infty}\frac{F_{n}}{10^{n}} = \frac{10}{89} = 0,\!\overline{11235955056179775280898876404494382022471910}\] Pour trouver cette valeur, on réutilise\begin{align*}f(z) &= F_{0} + F_{1}z + F_{2}z^{2} + F_{3}z^{3} + F_{4}z^{4} + F_{5}z^{5} + \ \dots \\ \\ &=\frac{z}{1-z-z^{2}}\end{align*}et on pose \[z = \frac{1}{10}\] puisque \[\frac{-2}{1+\sqrt{5}}<\frac{1}{10}<\frac{2}{1+\sqrt{5}}\]afin d’obtenir \begin{align*}f\left(\frac{1}{10}\right) &= \frac{\frac{1}{10}}{1-\frac{1}{10}-\left(\frac{1}{10}\right)^{2}} \\ \\ &= \frac{\frac{1}{10}}{1-\frac{1}{10} – \frac{1}{100}} \\ \\ &=\frac{10}{100-10-1} \\ \\ &=\frac{10}{89}\end{align*}c’est-à-dire \[\frac{10}{89} = F_{0} + F_{1}\left(\frac{1}{10}\right) + F_{2}\left(\frac{1}{10}\right)^2 + F_{3}\left(\frac{1}{10}\right)^{3} + F_{4}\left(\frac{1}{10}\right)^{4} + \ \dots \]ou \begin{align*}\frac{10}{89} &=\phantom{+}0 \\ \\ &\phantom{=}+0,\!1 \\ \\ &\phantom{=}+0,\!01 \\ \\ &\phantom{=}+0,\!002 \\ \\ &\phantom{=}+0,\!0003 \\ \\ &\phantom{=}+0,\!00005 \\ \\ &\phantom{=}+0,\!000008 \\ \\ &\phantom{=}+0,\!0000013 \\ \\ &\phantom{=}+\dots\end{align*}
Référence : Ronald Graham, Donald Knuth et Oren Patashnik (1994), Concrete Mathematics : A Foundation In Computer Science
On se retrouve avec deux triangles dont les hauteurs tombent à l’extérieur du triangle, sur le prolongement du côté opposé. Le premier triangle a une base de \(6\) et une hauteur de \(5\), le deuxième triangle a une base de \(3\) et une hauteur de \(8\) (plus difficile à voir). L’aire de la région ombrée est donc de \[\frac{6\times 5}{2}+\frac{3\times 8}{2} = 15 + 12 = 27\]Voilà ! Ça parait si simple !
