Ma · Mathematics

How to Solve a Difference Equation with Generating Functions

Published By the 9to5Science editorial team

At a glance

  1. 1. Specify the recurrence

    Write the recurrence, its starting index, and all required initial values.

  2. 2. Define the series

    Set the generating function to the sum of the sequence terms multiplied by successive powers of a variable.

  3. 3. Translate each shift

    Rewrite the recurrence as an equation involving the generating function, accounting for initial terms.

  4. 4. Extract the coefficients

    Solve for the generating function, then expand it or use a known series to read off the sequence.

Advertisement

A difference equation describes how sequence terms are related, but this title does not include the actual recurrence or its initial values. There is therefore no unique sequence to solve for: even the recurrence an=an−1a_n=a_{n-1} has different solutions for different choices of a0a_0.

The standard generating-function method turns a recurrence into an algebraic equation. The example below works through the steps; to solve a particular problem, you also need to provide its recurrence, index range, and starting values.

What information is needed?

A solvable problem should state:

  • the recurrence, such as an=an−1+an−2a_n=a_{n-1}+a_{n-2};
  • the range of indices for which it applies, such as n≥2n\geq 2;
  • enough initial values to determine the sequence, such as a0a_0 and a1a_1.

The index range matters because it determines which initial terms must be handled separately when shifting sums. If a problem instead asks for a sequence indexed by all integers, or includes a forcing term that depends on nn, those details also affect the setup.

The generating-function method

For a sequence a0,a1,a2,…a_0,a_1,a_2,\ldots, define its ordinary generating function by

A(x)=∑n≥0anxn.A(x)=\sum_{n\geq 0}a_nx^n.

Multiply the recurrence by xnx^n and sum over its stated range. Rewrite each sum in terms of A(x)A(x). When an index shift removes the first terms of a sum, include those initial values explicitly. Solve the resulting equation for A(x)A(x), then expand it as a power series to identify the coefficients ana_n.

In many recurrence problems, these calculations can be treated as operations on formal power series. You do not need to establish numerical convergence just to compare coefficients.

Worked example: the Fibonacci recurrence

Consider

an=an−1+an−2(n≥2),a0=0,a1=1.a_n=a_{n-1}+a_{n-2}\quad(n\geq 2),\qquad a_0=0,\quad a_1=1.

Define A(x)=∑n≥0anxnA(x)=\sum_{n\geq0}a_nx^n. Summing the left side of the recurrence from n=2n=2 gives A(x)−a0−a1x=A(x)−xA(x)-a_0-a_1x=A(x)-x. The two sums on the right are

∑n≥2an−1xn=xA(x),∑n≥2an−2xn=x2A(x).\sum_{n\geq2}a_{n-1}x^n=xA(x),\qquad \sum_{n\geq2}a_{n-2}x^n=x^2A(x).

Thus the recurrence becomes

A(x)−x=xA(x)+x2A(x).A(x)-x=xA(x)+x^2A(x).

Solving for A(x)A(x) gives

A(x)=x1−x−x2.A(x)=\frac{x}{1-x-x^2}.

To extract the terms explicitly, let ϕ=(1+5)/2\phi=(1+\sqrt{5})/2 and ψ=(1−5)/2\psi=(1-\sqrt{5})/2. Since 1−x−x2=(1−ϕx)(1−ψx)1-x-x^2=(1-\phi x)(1-\psi x), partial fractions give

A(x)=15(11−ϕx−11−ψx).A(x)=\frac{1}{\sqrt{5}}\left(\frac{1}{1-\phi x}-\frac{1}{1-\psi x}\right).

Using 1/(1−cx)=∑n≥0cnxn1/(1-cx)=\sum_{n\geq0}c^nx^n, compare coefficients to obtain

an=ϕn−ψn5.a_n=\frac{\phi^n-\psi^n}{\sqrt{5}}.

For instance, this gives a0=0a_0=0, a1=1a_1=1, a2=1a_2=1, a3=2a_3=2, and a4=3a_4=3, as required by the recurrence.

Common mistakes

  • Leaving out starting values. A recurrence generally allows multiple sequences until enough initial terms are fixed.
  • Starting the sum at the wrong index. For a recurrence valid only when n≥2n\geq2, sum from n=2n=2, not n=0n=0.
  • Dropping boundary terms. For example, shifting a sum can remove terms involving a0a_0 or a1a_1; check them before replacing the sum with A(x)A(x).
  • Confusing the generating function with the sequence. The function A(x)A(x) encodes the terms as coefficients; the answer for ana_n comes from expanding it or extracting its coefficient of xnx^n.

To obtain a solution for a specific difference equation, supply the recurrence together with its index range and initial conditions.

References

  1. Herbert S. Wilf, Generatingfunctionology

Spotted an error? Send a correction. Read how we write and check articles in our editorial policy.