En genererande funktion är inom matematik en formell potensserie som innehåller information om en talföljd.

DefinitionRedigera

Den genererande funktionen f till talföljden an, n = 0, 1, 2, ..., definieras som

 

Ofta är f bara definierad i ett intervall runt origo (ibland bara i en punkt), nämligen när summan bara konvergerar där. Det är då mer fruktbart att betrakta f som en formell potensserie snarare än en funktion.

Om an är sannolikhetsfördelningen av en diskret slumpvariabel så är dess genererande funktion kallad en sannolikhetsgenererande funktion.

Exponentiell genererande funktionRedigera

Ibland betraktas istället en exponentiell genererande funktion till en talföljd an, definierad som:

 .

ExempelRedigera

Den genererande funktionen till Fibonacciföljden Fn kan bestämmas som följer:

Fn definieras av rekursionen  , och  

Genom att sätta   kan vi ställa upp

 

Substituera f(x)

 

Multiplicera in i parentesen

 

Förskjut indexen med 0, 1 respektive 2 steg

 

Ta ut k = 0 och k = 1

 

Slå ihop resterande summor

 

Sätt in F0 = 0, F1 = 1 och rekursionen

 

Alltså gäller

 

Externa länkarRedigera