Genererande funktion

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

Definition

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

$f(x)=\sum _{k=0}^\infty a_k x^k$

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.

Exponentiell genererande funktion

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

$\sum_{k=0}^\infty \frac{a_k}{k!} x^k$.

Exempel

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

F_n definieras av rekursionen $F_{k+2}-F_{k+1}-F_k=0\$, och $F_0=0, F_1=1\$

Genom att sätta $f(x)=\sum _{k=0} ^\infty F_k x^k$ kan vi ställa upp

$(1 - x - x^2) \cdot f(x) =$

Substituera f(x)

$= (1 - x - x^2) \cdot \left(\sum _{k=0} ^\infty F_k x^k\right) =$

Multiplicera in i parentesen

$= \sum _{k=0}^\infty F_k x^{k}- \sum _{k=0}^\infty F_k x^{k+1}- \sum _{k=0}^\infty F_k x^{k+2} =$

Förskjut indexen med 0, 1 respektive 2 steg

$= \sum _{k=0}^\infty F_k x^{k}- \sum _{k=1}^\infty F_{k-1} x^{k}- \sum _{k=2}^\infty F_{k-2} x^{k} =$

Ta ut k = 0 och k = 1

$= \left(F_0 \cdot x^0 + F_1 \cdot x + \sum _{k=2}^\infty F_k x^{k}\right) - \left(F_{1-1} \cdot x^1 + \sum _{k=2}^\infty F_{k-1} x^{k}\right)-\left(\sum _{k=2}^\infty F_{k-2} x^{k}\right) =$

Slå ihop resterande summor

$= F_0 + F_1 \cdot x - F_0 \cdot x + \sum _{k=2}^\infty \left(F_{k} - F_{k-1} - F_{k-2}\right) \cdot x^{k}$

Sätt in F₀ = 0, F₁ = 1 och rekursionen

$= 0 + 1 \cdot x - 0 \cdot x + \sum _{k=2}^\infty 0 \cdot x^{k} = x$

Alltså gäller

$f(x) = \frac{x}{1 - x - x^2}$