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

## Saturday, May 28, 2016

Subscribe to:
Post Comments (Atom)

## No comments:

## Post a Comment