Difference and functional equations Definition

Solution of recurrences by generating functions

Builds on Generating function Formal power series Linear recurrence with constant coefficients

Definition

Let $K$ be a field and let $(u_n)_{n \ge 0}$ be a sequence in $K$ that satisfies a recurrence relation for $n \ge 0$ . The generating function method for this recurrence consists of these steps.

Form the generating function $U(x) = \sum_{n \ge 0} u_n x^n$ in the ring $K[\![x]\!]$ of formal power series.
Multiply the recurrence for index $n$ by a suitable power $x^{n+d}$ and sum over $n \ge 0$ . This gives an equation for $U(x)$ that involves the initial values.
Solve this equation for $U(x)$ .
Read off $u_n$ as the coefficient of $x^n$ in the solution.

For a linear recurrence with constant coefficients $u_{n+d} = c_{d-1} u_{n+d-1} + \cdots + c_0 u_n$ , step 3 gives $U(x) = \frac{P(x)}{1 - c_{d-1} x - c_{d-2} x^2 - \cdots - c_0 x^d},$ where $P$ is a polynomial of degree less than $d$ determined by $u_0, \dots, u_{d-1}$ .

Remarks

Example: the Fibonacci sequence has $F_0 = 0$ , $F_1 = 1$ and $F_{n+2} = F_{n+1} + F_n$ . Multiplying by $x^{n+2}$ and summing gives $F(x) - x = x F(x) + x^2 F(x)$ , so $F(x) = x/(1 - x - x^2)$ . Partial fractions with the roots of $1 - x - x^2$ then give $F_n = (\varphi^n - \psi^n)/\sqrt{5}$ , where $\varphi, \psi$ are the roots of $X^2 - X - 1$ . Non-example: for the nonlinear recurrence $u_{n+1} = u_n^2$ , step 2 does not give an equation in $U$ alone. The series $\sum u_n^2 x^n$ is not a simple function of $U(x)$ , so the method does not apply directly. The denominator in the constant-coefficient case is $x^d \chi(1/x)$ , where $\chi$ is the characteristic polynomial of the recurrence. Other generating functions, such as exponential ones, suit other recurrences, for example those with factors $n$ in the coefficients.

Reading path

To understand this page from the ground up, read these 5 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Formal power series concept
Generating function concept
Recurrence relation definition
Linear recurrence with constant coefficients definition
Solution of recurrences by generating functions definition

Tag	`76NQXSGSHS`
URI	`m2://76NQXSGSHS`
Kind	definition
Writing	W0 stub
MSC	39A06, 05A15
Defines	Solution of recurrences by generating functions
Uses	Generating function, Formal power series, Linear recurrence with constant coefficients

Solution of recurrences by generating functions

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here