Processing math: 100%

Saturday, May 28, 2016

Generating functions of sequences

The generating function of a sequence
{a(n)}n=0={a0,a1,a2,} for integers n0 is defined as f(x)=a0+a1x+a1x2+.

For a sequence that satisfies the linear recurrence relation
a(n)=c0a(n1)+c1a(n2)++cma(nm1)
with initial terms a(0)=a0,a(1)=a1,,a(m)=am,
the general form of the generating function is given by:

f(x)=amxm+i<mi=0(aixicixj<mij=0ajxi+j)1ximi=0cixi

The sequence a(n)=bcn+d satisfies the recurrence relation a(n)=(c+1)a(n1)ca(n2) with
generating function:

(b(1x)+d(1cx))/((1x)(1cx)).

No comments:

Post a Comment