Ordinary Generating Functions for Simple Sequences
You'll learn how to construct generating functions for basic sequences like constant sequences and powers of n using geometric series.
The Core Idea
An ordinary generating function (OGF) packages a sequence into a single formal power series. For a sequence , its generating function is:
The coefficients are your sequence! Now let's build generating functions for the simplest sequences.
The Constant Sequence: 1, 1, 1, ...
For the sequence where every term equals 1, the generating function is:
This is a geometric series with first term 1 and common ratio . When , it sums to:
Think of this as a "compressed encoding": the infinite sequence is captured by the compact formula .
Powers of n: 1, 2, 3, 4, ...
For the sequence , we want:
Start with . Take the derivative:
Multiply by to shift indices:
This generates the sequence .
Why This Matters
Generating functions transform sequence problems into algebraic manipulations. The geometric series becomes your foundation—differentiate, multiply, or combine to build more complex sequences.
Key Takeaway: The generating function for is , and for it's —both derived from the geometric series.