Recurrence Relations & Ordinary Generating Functions

A recurrence relation of the form a_n + c_1 a_{n-1} + c_2 a_{n-2} + ... + c_k a_{n-k} = 0 has constant coefficients.

Method of Characteristic Roots:

Substitute trial solution a_n = r^n into the recurrence to obtain the characteristic equation:

r^k + c_1 r^{k-1} + ... + c_k = 0.

1. Distinct Real Roots r_1, r_2, ..., r_k:

a_n = A_1 r_1^n + A_2 r_2^n + ... + A_k r_k^n.

2. Repeated Roots (Root r with multiplicity m):

a_n = (A_0 + A_1 n + A_2 n^2 + ... + A_{m-1} n^{m-1}) r^n.

Constants A_i are determined from initial boundary conditions.

An Ordinary Generating Function encapsulates an infinite numerical sequence {a_0, a_1, a_2, ...} as coefficients of a formal power series:

G(x) = sum_{n=0}^infty a_n x^n = a_0 + a_1 x + a_2 x^2 + ...

Standard Power Series Expansions:

- frac{1}{1 - x} = sum_{n=0}^infty x^n = 1 + x + x^2 + ...

- frac{1}{1 - a x} = sum_{n=0}^infty a^n x^n

- frac{1}{(1 - x)^2} = sum_{n=0}^infty (n + 1) x^n

- frac{1}{(1 - x)^k} = sum_{n=0}^infty binom{n + k - 1}{n} x^n