Fonction génératrice de la somme de n nombres entiers à la puissance k
Un article de Wikipedia.
Sommaire |
Fonction génératrice de la somme de n nombres entiers à la puissance k
But
Déterminer la fonction génératrice de la somme de n entiers à la puissance k.
Introduction
Une fonction génératrice est une fonction d'une variable f(x) dont les coefficients du développement en xk correspondent à ceux d'une série ak (pour k ≥ 0) donnée.
Il y a 2 sortes de fonctions génératrices :
- l'une écrite sous la forme d'un développement en série de puissances ordinaire
- f(x) = ∑k≥0 ak * xk
- les coefficients sont obtenus par dérivée k ième de la fonction et qui est ensuite calculée au point 0
- ak = 1 / k ! * dk / d x k f(x) | x = 0
- l'autre écrite sous la forme d'un développement en série de puissances pour des fonctions génératrices exponentielles
- f(x) = ∑k≥0 ak * xk / k !
- les coefficients sont obtenus par dérivée k ième de la fonction et calculée au point 0
- ak = dk / d x k f(x) | x = 0
Chaque sorte de fonction génératrice a ses possibilités propres et est utilisée en fonction de la série à traiter.
Notations
f (x) = {ak} désigne une fonction génératrice de puissances ordinaire
f (x) = {ak}e désigne une fonction génératrice exponentielle
Exemples
Des exemples permettent de mieux saisir ces différentes fonctions génératrices
f (x) = {1k} = 1 + x + x2 + x3 + ... + xk + ... = 1 / (1 - x)
f (x) = {1k}e = 1 + x / 1 ! + x2 / 2 ! + x3 / 3 ! + ... + xk / n ! + ... = ex (d'où le caractère exponentiel)
Propriétés remarquables
| propriété | fonction génératrice ordinaire | fonction génératrice exponentielle |
| f | { ak } | { ak }e |
| g | { bk } | { bk }e |
| f + g | { ak + bk } | { ak + bk }e |
| x * f ' = x * d f / dx | { k * ak } | { k * ak }e |
| f * g | { ∑r = 0r = k ar * bk-r } | { ∑r = 0r = k (rk) * ar * bk-r }e ou (rk) = k ! / ( r ! * (k - r ) ! ) |
| f( β * x ) avec β un nombre | { βk * ak } | { βk * ak }e |
Fort de ces propriétés remarquables et de la relation récurrente des sommes des entiers à la puissance k de l'article Formule générale pour calculer la somme des nombres entiers à la puissance m, il est possible de déterminer la fonction génératrice recherchée.
Comme la formule récurrente inclu des combinaisons, il est donc évident qu'il faut utiliser la forme exponentielle pour la fonction génératrice.
La forme initiale de la formule avant réduction se prête le mieux à la détermination de la fonction génératrice.
Soit
S = { Σr=1r=n rk }e
Et la formule récurrente avant réduction de Formule générale pour calculer la somme des nombres entiers à la puissance m réécrite dans notre contexte
(n + 1)k + Σj=1j=k jk = Σj=1j=k (j + 1)k + 1.
Et soit
Sk = Σr=1r=n rk
et donc nous recherchons
S = { Sk }e
alors, en développant aussi (j + 1)k = Σm=0m=k (mk) * jk
(n + 1)k + Sk = Σm=0m=k (mk) * Sk + 1.
A partir de là, la fonction génératrice commence à se présenter.
En procédant composant par composant
{ 1 }e = ex
{ (n + 1)k }e = { Σm=0m=k (mk) * nk }e = { 1 }e * { nk }e = { 1 }e * { nk * 1 }e = ex * en * x
{ Sk }e = S
{ Σm=0m=k (mk) * Sk }e = { 1 }e * { Sk }e = ex * S
soit finalement
ex * en * x + S = ex * S + ex
et donc, la fonction génératrice recherchée est
S = ex * ( en * x - 1 ) / ( ex - 1 )
Réécriture de la fonction génératrice pour confirmation
Comme souvent en mathématque (et ailleurs d'ailleurs), une fois le chemin parcouru, une analyse du résultat s'impose pour mieux le comprendre.
En réécrivant le résultat précédent en posant u = ex
S = u * ( un - 1 ) / ( u - 1 )
nous reconnaissons le second terme
( un - 1 ) / ( u - 1 ) = 1 + u + u2 + ... + un - 1 = Σk=0k=n-1 uk
et ainsi
S = u + u2 + ... + un = Σk=1k=n uk = Σk=1k=n ek * x
Cela confirme que S est bien la formule que nous recherchons car Sm est obtenue en dérivant m fois la fonction S et en l'évaluant au point x = 0.
Or la dérivée m ième de ek * x vaut km * ek * x et donc
S(m) = Σk=1k=n km * ek * x
au point x = 0
S(m)(0) = Σk=1k=n km
qui est bien Sm !
Résultats
L'utilisation de la fonction génératrice S (la première, pas la confirmation) pour extraire une formule pour la somme de n entiers à la puissance k est relativement compliquée car la dérivée de S devient vite longue et l'évaluation en x = 0 se heurte immédiatement à un rapport 0 / 0 ! Il faut donc utiliser le développement en x des exponentielles jusqu'au degré k + 1 !
Exemples
Réécrivons S pour limiter la complexité de la dérivation de S
S = ex * ( en * x - 1 ) / ( ex - 1 ) = ( en * x - 1 ) / ( 1 - e-x )
Ainsi, pour S(0)(0) = S(0) nous avons au premier abord
S(0) = ( 1 - 1 ) / ( 1 - 1 ) = 0 / 0
En utilisant le développement au premier degrés de ex = 1 + x
S(x) = ( 1 + (n * x) - 1 ) / ( 1 - ( 1 - x ) ) = n * x / x = n
et donc S(0) = n comme attendu.
Pour S'(0) le calcul est encore plus compliqué.
S'(x) = [ n * en * x * ( 1 - e-x ) - ( en * x - 1 ) * e-x ] / ( 1 - e-x )2 = [ n * en * x + e-x - (n + 1) * en * x * e-x ] / ( 1 - e-x )2
Et S'(0) au premier abord
S'(0) = [ n + 1 - (n + 1) ] / ( 1 - 1 )2 = 0 / 0
En utilisant le développement au second degrés de ex = 1 + x + x2/2
S'(x) = [ n * ( 1 + n *x + (n * x)2/2 ) + 1 - x + x2/2 - (n + 1) * ( 1 + n *x + (n * x)2/2 ) * ( 1 - x + x2/2 ) ] / [ 1 - ( 1 - x + x2/2) ]2
En passant les détails
S'(x) = x2 * [ n * ( n + 1 ) / 2 + n * ( n + 1 ) * ( n - 1 ) * x / 2 - n2 * ( n + 1 ) * x2 / 4 ] / [ x2 * ( 1 - x/2 )2 ] S'(x) = [ n * ( n + 1 ) / 2 + n * ( n + 1 ) * ( n - 1 ) * x / 2 - n2 * ( n + 1 ) * x2 / 4 ] / ( 1 - x/2 )2
et en l'évaluant au point x = 0
S'(0) = n * ( n + 1 ) / 2
comme attendu.
Pour les autres degrés, je laisse cela aux plus téméraires (ou aux systèmes automatiques).
La fonction génératrice permet aussi de déterminer la valeur de la série s = Σm≥0 Sm / m ! en calculant S au point x = 1
s = Σm≥0 Sm / m ! = Σm≥0 Σr=1r=n rm / m ! = S(1) = e * ( en - 1 ) / ( e - 1 )
Conclusions
En connaissant une relation récurrente sur les termes d'une série, les fonctions génératrices sont d'une puissance 'redoutable' pour résoudre 'facilement' l'ensemble du problème.
D'un autre côté, comme par dualité, ce qui est facile à obtenir devient plus difficile à conquérir; l'extraction de la somme des entiers à la puissance k est vraiment ardue !
Il y a un second sentiment avec les fonctions génératrices, celui de pouvoir transformer le plomb en or !
La banale formule (le plomb) u * ( un - 1 ) / ( u - 1 ) = u + u2 + ... + un révèle une puissance insoupçonnée (l'or) en l'appliquant sur u = ex, pour celui qui sait l'interpréter bien sûr.
Y-t-il de l'or à nos pieds qui est invisible à nos yeux ? Il semblerait !
Enfin, les fonctions génératrices font partie des outils qui, à défaut de pouvoir résoudre un problème particulier, permettent de résoudre tous les problèmes en même temps.
Et c'est cela qui donne cet effet 'Waouh' lorsque la fonction génératrice est enfin déterminée car elle tient dans sa main l'ensemble des solutions du problème.
Les fonctions génératrices permettent d'aborder le problème traité ici (et bien d'autres !) de manières différentes et se trouvent dans l'excellent livre cité dans les ressources.
Ressources
- L'excellent ouvrage de Herbert S. Wilf, generatingfunctionology, Academic Press, Inc., 1990
