Recurrence Relations and Generating Functions

2026-11-18

notes / Discrete Structures

Generating Functions

Given a series of numbers {an}n=0∞ its generating function in a formal power series f(x)=∑n=0∞bnxn where bn could be directly obtained from an and n

Ordinary generating functions have bn=an

Solving Recurrences

example recurrence

for n≥2 and f0=0, f1=1

fn=fn−1+fn−2

  1. Form generating function:

F(x)=f0+f1x+f2x2+f3x3+…

  1. Manipulation: substitute known values and recurrences

F(x)=0+1x+(f1+f0)x2+(f2+f1)x3+…=x+x(f1x+f2x2+…)+x2(f0+f1x+f2x2+…)=x+xF(x)+x2F(x)

which gives us

F(x)=x1−x−x2

example 2:

for a1=2

ai+1=ai+2i

for generating function and manipulate

A(x)=2x+(a1+2)x2+(a2+2⋅2)x3+…A(x)=2x+xA(x)+2x2(1+2x+3x2+…)A(x)=xA(x)+2x(1+x+2x2+3x3+…)

Sum of Power Series

From the sum of GP we can derive the sum of a power series to get ∑∞nxn=1(1−x)2

A(x)=xA(x)+2x(1−x)2A(x)=2x(1−x)3

linked from