Un article de Wikipedia.

Version du 13 juillet 2013 à 19:30

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 x^k correspond à celui d'une série a_k (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 a_k * x^k
  • les coefficients sont obtenus par dérivée k ième de la fonction et qui est ensuite calculée au point 0
    • a_k = 1 / k ! * d^k / 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 a_k * x^k / k !
  • les coefficients sont obtenus par dérivée k ième de la fonction et calculée au point 0
    • a_k = d^k / 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.

Notation

f (x) = {a_k} désigne une fonction génératrice de puissances ordinaire

f (x) = {a_k}_e désigne une fonction génératrice exponnentielle

Exemples

Des exemples permettent de mieux saisir ces différentes fonctions génératrices

f (x) = {1_k} = 1 + x + x² + x³ + ... + x^k + ... = 1 / (1 - x)

f (x) = {1_k}_e = 1 + x / 1 ! + x² / 2 ! + x³ / 3 ! + ... + x^k / n ! + ... = e^x (d'où le caractère exponenteille)

Propriétés remarquables

Fort de ces propriétés remarquables et de la relation récursive 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écursive 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écursive 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=0^m=k (_m^k) * j_k

(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 = e^x

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 S_m 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 e^{k * x} vaut k^m * e^{k * 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 S_m !

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 exponenetielles 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) = S(0) nous avons au premier abord

S(0) = ( 1 - 1 )  / ( 1 - 1 ) = 0 / 0 

En utiisant le développement au premier degrés de e^x = 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é.

Conclusions

Ressources