## Saturday, May 28, 2016

### Generating functions of sequences

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))$$.