How to Solve a Difference Equation with Generating Functions
At a glance
- 1. Specify the recurrence
Write the recurrence, its starting index, and all required initial values.
- 2. Define the series
Set the generating function to the sum of the sequence terms multiplied by successive powers of a variable.
- 3. Translate each shift
Rewrite the recurrence as an equation involving the generating function, accounting for initial terms.
- 4. Extract the coefficients
Solve for the generating function, then expand it or use a known series to read off the sequence.
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 has different solutions for different choices of .
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 ;
- the range of indices for which it applies, such as ;
- enough initial values to determine the sequence, such as and .
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 , those details also affect the setup.
The generating-function method
For a sequence , define its ordinary generating function by
Multiply the recurrence by and sum over its stated range. Rewrite each sum in terms of . When an index shift removes the first terms of a sum, include those initial values explicitly. Solve the resulting equation for , then expand it as a power series to identify the coefficients .
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
Define . Summing the left side of the recurrence from gives . The two sums on the right are
Thus the recurrence becomes
Solving for gives
To extract the terms explicitly, let and . Since , partial fractions give
Using , compare coefficients to obtain
For instance, this gives , , , , and , 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 , sum from , not .
- Dropping boundary terms. For example, shifting a sum can remove terms involving or ; check them before replacing the sum with .
- Confusing the generating function with the sequence. The function encodes the terms as coefficients; the answer for comes from expanding it or extracting its coefficient of .
To obtain a solution for a specific difference equation, supply the recurrence together with its index range and initial conditions.
References
- Herbert S. Wilf, Generatingfunctionology
Spotted an error? Send a correction. Read how we write and check articles in our editorial policy.