Course contentsShow
← Mathematics
Lesson 2639 of 3,12152. CombinatoricsFree lesson

Ordinary Generating Functions for Simple Sequences

Construct generating functions for basic sequences like 1,1,1,... and powers of n using geometric series.

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 a0,a1,a2,…a_0, a_1, a_2, \ldots, its generating function is:

G(x)=a0+a1x+a2x2+a3x3+⋯G(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots

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:

G(x)=1+x+x2+x3+⋯G(x) = 1 + x + x^2 + x^3 + \cdots

This is a geometric series with first term 1 and common ratio xx. When ∣x∣<1|x| < 1, it sums to:

G(x)=11−xG(x) = \frac{1}{1-x}

Think of this as a "compressed encoding": the infinite sequence 1,1,1,…1, 1, 1, \ldots is captured by the compact formula 11−x\frac{1}{1-x}.

Powers of n: 1, 2, 3, 4, ...

For the sequence an=na_n = n, we want:

G(x)=0+1x+2x2+3x3+⋯G(x) = 0 + 1x + 2x^2 + 3x^3 + \cdots

Start with 11−x=1+x+x2+⋯\frac{1}{1-x} = 1 + x + x^2 + \cdots. Take the derivative:

ddx(11−x)=1(1−x)2=1+2x+3x2+⋯\frac{d}{dx}\left(\frac{1}{1-x}\right) = \frac{1}{(1-x)^2} = 1 + 2x + 3x^2 + \cdots

Multiply by xx to shift indices:

G(x)=x(1−x)2G(x) = \frac{x}{(1-x)^2}

This generates the sequence 0,1,2,3,…0, 1, 2, 3, \ldots.

Why This Matters

Generating functions transform sequence problems into algebraic manipulations. The geometric series 11−x\frac{1}{1-x} becomes your foundation—differentiate, multiply, or combine to build more complex sequences.

Key Takeaway: The generating function for 1,1,1,…1,1,1,\ldots is 11−x\frac{1}{1-x}, and for nn it's x(1−x)2\frac{x}{(1-x)^2}—both derived from the geometric series.