On commence avec cette curieuse question

Quelle est la somme, si elle existe, dethedudeminds_20130405182(2)

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 Fibonaccithedudeminds_2013040501

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 nième 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

thedudeminds_2013040502

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 plusthedudeminds_2013040601sont tous des entiers positifs, et même quethedudeminds_2013040602on 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 quethedudeminds_2013040504il 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 z2.thedudeminds_2013040505On soustrait les deux équations du bas à la première. On remarque que tous les termes à partir de z2 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 z2 seulementthedudeminds_2013040507puis pour les termes en z3 thedudeminds_2013040508et ainsi de suite… De plus, commethedudeminds_2013040506il ne reste à la fin quethedudeminds_2013040509ce qui est tout simplement
thedudeminds_2013040510Ah ! On a doncthedudeminds_2013040511et en effectuant la mise en évidencethedudeminds_2013040512on obtient une nouvelle expression pour la fonction f, une forme fermée de fthedudeminds_2013040513Avant de continuer, une petite division avec crochet fort distrayante illustre de belle manière cette dernière égalitéthedudeminds_2013040501

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 quethedudeminds_2013040520On posethedudeminds_2013041508En développant la partie de droite on obtientthedudeminds_2013040521ou de manière équivalente
thedudeminds_2013040522En outre,thedudeminds_2013041505et les expressionsthedudeminds_2013040524correspondent aux coefficients Fn des zn, c’est-à-dire aux termes de la suite de Fibonacci. On essaie donc de trouver des A, B, α et β tels que thedudeminds_2013040523En mettant la somme à gauche sur le même dénominateur, on obtientthedudeminds_2013040525c’est-à-dire qu’on a
thedudeminds_2013040526et qu’il faut résoudre le système d’équations suivantthedudeminds_2013040527thedudeminds_2013040528En examinant la première équation, on peut s’attaquer aux valeurs de α et β en tentant de factoriser le trinôme.thedudeminds_2013040603dont le terme constant est 1. En complétant le carré et en factorisant la différence de carrés, on obtientthedudeminds_2013040604et cela nous donne des valeurs pour α et βthedudeminds_2013040605Le 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 φ. On remarque au passage que thedudeminds_2013040606Puisquethedudeminds_2013040607il ne reste qu’à trouver A et B dansthedudeminds_2013040528En posant z = 0, on trouve facilement que B = –A. Du coup, l’équation précédente devientthedudeminds_2013040608En divisant par z ≠ 0thedudeminds_2013040609puis en effectuant la mise en évidence de A,thedudeminds_2013040610on obtientthedudeminds_2013040611Un peu d’algèbre élémentaire nous permet d’écrire d’abord cecithedudeminds_2013040612puis de simplifier davantagethedudeminds_2013040613
On trouve par le fait même quethedudeminds_2013043001Cela nous permet de de remplacer AB, α et β d’abord dansthedudeminds_2013040523afin d’obtenir la fonction f comme somme de fractions partielles
thedudeminds_2013040615

Et commethedudeminds_2013041101c’est-à-dire quethedudeminds_2013041102on peut enfin trouver pour quelles valeurs de z est-ce que la fonction existe, autrement dit, pour quelles valeurs de z est-ce quethedudeminds_2013041601 converge. La première somme converge si thedudeminds_2013041610On obtient doncthedudeminds_2013041104La deuxième somme converge si thedudeminds_2013041611et on obtientthedudeminds_2013041105

Puisquethedudeminds_2013041501on trouve que la série converge seulement pour des valeurs de z entrethedudeminds_2013041503

Par ailleurs, on obtient également un résultat fort intéressant, la formule pour le nième terme de la suite de Fibonacci, les coefficients de zn dans f(z). En remplaçant A, B, α et β dansthedudeminds_2013040524on athedudeminds_2013041506qu’on peut réécrire comme thedudeminds_2013041507

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

thedudeminds_2013041509Aussi étonnant que cela puisse paraître, la somme existe et c’est un nombre rationnel de période 44thedudeminds_2013040519On réutilisethedudeminds_2013041510et on posethedudeminds_2013041511afin d’obtenirthedudeminds_2013040514c’est-à-direthedudeminds_2013040515outhedudeminds_2013041602

Référence : Ronald Graham, Donald Knuth et Oren Patashnik (1994), Concrete Mathematics : A Foundation In Computer Science