En genererande funktion är inom matematik en formell potensserie som innehåller information om en talföljd .
Den genererande funktionen f till talföljden an , n = 0, 1, 2, ..., definieras som
f
(
x
)
=
∑
k
=
0
∞
a
k
x
k
{\displaystyle 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.
Om an är sannolikhetsfördelningen av en diskret slumpvariabel så är dess genererande funktion kallad en sannolikhetsgenererande funktion .
Ibland betraktas istället en exponentiell genererande funktion till en talföljd an , definierad som:
∑
k
=
0
∞
a
k
k
!
x
k
{\displaystyle \sum _{k=0}^{\infty }{\frac {a_{k}}{k!}}x^{k}}
Den genererande funktionen till Fibonacciföljden Fn kan bestämmas som följer:
Fn definieras av rekursionen
F
k
+
2
−
F
k
+
1
−
F
k
=
0
{\displaystyle F_{k+2}-F_{k+1}-F_{k}=0\ }
F
0
=
0
,
F
1
=
1
{\displaystyle F_{0}=0,F_{1}=1\ }
Genom att sätta
f
(
x
)
=
∑
k
=
0
∞
F
k
x
k
{\displaystyle f(x)=\sum _{k=0}^{\infty }F_{k}x^{k}}
(
1
−
x
−
x
2
)
⋅
f
(
x
)
=
{\displaystyle (1-x-x^{2})\cdot f(x)=}
Substituera f (x )
=
(
1
−
x
−
x
2
)
⋅
(
∑
k
=
0
∞
F
k
x
k
)
=
{\displaystyle =(1-x-x^{2})\cdot \left(\sum _{k=0}^{\infty }F_{k}x^{k}\right)=}
Multiplicera in i parentesen
=
∑
k
=
0
∞
F
k
x
k
−
∑
k
=
0
∞
F
k
x
k
+
1
−
∑
k
=
0
∞
F
k
x
k
+
2
=
{\displaystyle =\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
=
∑
k
=
0
∞
F
k
x
k
−
∑
k
=
1
∞
F
k
−
1
x
k
−
∑
k
=
2
∞
F
k
−
2
x
k
=
{\displaystyle =\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
=
(
F
0
⋅
x
0
+
F
1
⋅
x
+
∑
k
=
2
∞
F
k
x
k
)
−
(
F
1
−
1
⋅
x
1
+
∑
k
=
2
∞
F
k
−
1
x
k
)
−
(
∑
k
=
2
∞
F
k
−
2
x
k
)
=
{\displaystyle =\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
⋅
x
−
F
0
⋅
x
+
∑
k
=
2
∞
(
F
k
−
F
k
−
1
−
F
k
−
2
)
⋅
x
k
{\displaystyle =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 = 0, F 1 = 1 och rekursionen
=
0
+
1
⋅
x
−
0
⋅
x
+
∑
k
=
2
∞
0
⋅
x
k
=
x
{\displaystyle =0+1\cdot x-0\cdot x+\sum _{k=2}^{\infty }0\cdot x^{k}=x}
Alltså gäller
f
(
x
)
=
x
1
−
x
−
x
2
{\displaystyle f(x)={\frac {x}{1-x-x^{2}}}}