Un article de Wikipedia.

Version du 13 juillet 2013 à 19:12 (modifier) Ziglooadmin (Discuter | Contributions) (→Propriétés remarquables) ← Différence précédente		Version du 13 juillet 2013 à 19:13 (modifier) (défaire) Ziglooadmin (Discuter | Contributions) m (→Propriétés remarquables) Différence suivante →
Ligne 103 :		Ligne 103 :
	soit finalement		soit finalement
-	e<sup>x</sup> * e<sup>n * x</sup> + S = e<sup>x</sup> * S + e<sup>x</sup>	+	e<sup>x</sup> * e<sup>n * x</sup> + S = e<sup>x</sup> * S + e<sup>x</sup>
	et donc, la fonction génératrice recherchée est		et donc, la fonction génératrice recherchée est

---

Version du 13 juillet 2013 à 19:13

Sommaire 1 Fonction génératrice de la somme de n nombres entiers à la puissance k 1.1 But 1.2 Introduction 1.2.1 Notation 1.2.2 Exemples 1.2.3 Propriétés remarquables 1.2.4 Réécriture de la fonction génératrice pour confirmation 1.3 Résultats 1.4 Conclusions 1.5 Ressources

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

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 } 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é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</sub>

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

Conclusions

Ressources