The generating function of a sequence
$\{a(n)\}_{n=0}^\infty = \{a_0, a_1, a_2, \cdots\}$ for integers $n\geq 0$ is defined as $f(x) = a_0 + a_1x + a_1x^2 + \cdots$.
For a sequence that satisfies the linear recurrence relation
$a(n) = c_0a(n-1) + c_1a(n-2) + \cdots + c_{m}a(n-m-1)$
with initial terms $a(0) = a_0, a(1) = a_1, \cdots , a(m) = a_m$,
the general form of the generating function is given by:
$$ f(x) = \frac{a_mx^m + \sum_{i=0}^{i< m}\left(a_ix^i- c_ix\sum_{j=0}^{j < m-i}a_jx^{i+j}\right)}{
1-x\sum_{i=0}^{i \leq m}c_ix^{i}}
$$
The sequence $a(n) = bc^n+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