Generating functions

 

The generating function for the  sequence  is the function  or any equivalent closed form expression.

Generating functions are considered as algebraic forms and can be manipulated as such, without regard to actual convergence of the power series.

Generating functions can be used to derive formulas for the sums of powers of integers.

Generating functions can be used to solve recurrence relations.

Each sequence  defines a unique generating function , and conversely.

Examples:

1. The sequence 0, 1,4, 9, 16, . . . of squares of the nonnegative integers has the generating function  However, this generating function has a concise closed form expression, namely  Verification is obtained by carrying out long division on the indicated polynomials. This concise form can be used to deduce properties involving the sequence, such as an explicit algebraic expression for the sum of squares of the first n positive integers.

2. The generating function for the sequence 1, 1, 1, 1, . . . is

 Differentiating both sides of this expression produces

 Thus,  is a closed form expression for the generating function of the sequence 1, 2, 3, 4, . . . .