The generating function of a sequence
{a(n)}∞n=0={a0,a1,a2,⋯} for integers n≥0 is defined as f(x)=a0+a1x+a1x2+⋯.
For a sequence that satisfies the linear recurrence relation
a(n)=c0a(n−1)+c1a(n−2)+⋯+cma(n−m−1)
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(aixi−cix∑j<m−ij=0ajxi+j)1−x∑i≤mi=0cixi
The sequence a(n)=bcn+d satisfies the recurrence relation a(n)=(c+1)a(n−1)−ca(n−2) with
generating function:
(b(1−x)+d(1−cx))/((1−x)(1−cx)).
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment