Generating Function

There are various types of generating functions, including ordinary generating functions, '''exponential generating functions''', '''Lambert series''', '''Bell series''', and '''Dirichlet series'''; definitions and examples are given below. Every sequence has a generating function of each type. The particular generating function that is most useful in a given context will depend upon the nature of the sequence and the details of the problem being addressed.

Generating functions are often expressed in closed form as functions of a formal argument ''x''. Sometimes a generating function is evaluated at a specific value of ''x''. However, it must be remembered that generating functions are formal power series, and they will not necessarily Converge for all values of ''x''.

DEFINITIONS

A generating function is a clothesline on which we hang up a sequence of numbers for display.

:— Herbert Wilf , ''generatingfunctionology'' (1994)

Ordinary generating function

The ''ordinary generating function'' of a sequence ''a''_''n'' is

:

G(a_n;x)=\sum_{n=0}^{\infty}a_nx^n.

When ''generating function'' is used without qualification, it is usually taken to mean an ordinary generating function.

If ''a''_''n'' is the Probability Mass Function of a Discrete Random Variable , then its ordinary generating function is called a Probability-generating Function .

The ordinary generating function can be generalised to sequences with multiple indexes. For example, the ordinary generating function of a sequence ''a''_''m,n'' (where ''n'' and ''m'' are natural numbers) is

:

G(a_{m,n};x,y)=\sum_{m,n=0}^{\infty}a_{m,n}x^my^n.

Exponential generating function

The ''exponential generating function'' of a sequence ''a''_''n'' is

:

EG(a_n;x)=\sum _{n=0}^{\infty} a_n rac{x^n}{n!}.

Poisson generating function

The ''Poisson generating function'' of a sequence ''a''_''n'' is

:

PG(a_n;x)=\sum _{n=0}^{\infty} a_n e^{-x} rac{x^n}{n!}.

Lambert series

The '' Lambert Series '' of a sequence ''a''_''n'' is

:

LG(a_n;x)=\sum _{n=1}^{\infty} a_n rac{x^n}{1-x^n}.

Note that in a Lambert series the index ''n'' starts at 1, not at 0.

Bell series

The Bell Series of an Arithmetic Function ''f''(''n'') and a prime ''p'' is

:

f_p(x)=\sum_{n=0}^\infty f(p^n)x^n.

Dirichlet series generating functions

Dirichlet Series are often classified as generating functions, although they are not strictly formal power series. The ''Dirichlet series generating function'' of a sequence ''a''_''n'' is

:

DG(a_n;s)=\sum _{n=1}^{\infty} rac{a_n}{n^s}.

The Dirichlet series generating function is especially useful when ''a''_''n'' is a Multiplicative Function , when it has an Euler Product expression in terms of the function's Bell series

:

DG(a_n;s)=\prod_{p} f_p(p^{-s})\,.

If ''a''_''n'' is a Dirichlet Character then its Dirichlet series generating function is called a Dirichlet L-series .

Polynomial sequence generating functions

The idea of generating functions can be extended to sequences of other objects. Thus, for example, polynomial sequences of Binomial Type are generated by

:

e^{xf(t)}=\sum_{n=0}^\infty {p_n(x) \over n!}t^n

where ''p''_''n''(''x'') is a sequence of polynomials and ''f''(''t'') is a function of a certain form. Sheffer Sequence s are generated in a similar way. See the main article Generalized Appell Polynomials for more information.

EXAMPLES

Generating functions for the sequence of Square Number s ''a''_''n'' = ''n''² are:

Ordinary generating function

:

G(n^2;x)=\sum_{n=0}^{\infty}n^2x^n=rac{x(x+1)}{(1-x)^3}

Exponential generating function

:

EG(n^2;x)=\sum _{n=0}^{\infty} rac{n^2x^n}{n!}=x(x+1)e^x

Bell series

:

f_p(x)=\sum_{n=0}^\infty p^{2n}x^n=rac{1}{1-p^2x}

Dirichlet series generating function

:

DG(n^2;s)=\sum_{n=1}^{\infty} rac{n^2}{n^s}=\zeta(s-2)

ANOTHER EXAMPLE

Generating functions can be created by extending simpler generating functions. For example, starting with

:

G(1;x)=\sum_{n=0}^{\infty} x^n = rac{1}{1-x}

and replacing

x

with

2x

, we obtain

:

G(1;2x)=rac{1}{1-2x} = 1+(2x)+(2x)^2+\cdots+(2x)^n+\cdots=G(2^n;x).

MORE DETAILED EXAMPLE &MDASH; FIBONACCI NUMBERS

Consider the problem of finding a closed formula for the Fibonacci Numbers ''F''_''n'' defined by ''F''₀ = 0, ''F''₁ = 1, and ''F''_''n'' = ''F''_''n''−1 + ''F''_''n''−2 for ''n'' ≥ 2. We form the ordinary generating function

:

f = \sum_{n \ge 0} F_n X^n

for this sequence. The generating function for the sequence (''F''_''n''−1) is ''Xf'' and that of (''F''_''n''−2) is ''X''²''f''. From the recurrence relation, we therefore see that the power series ''Xf'' + ''X''²''f'' agrees with ''f'' except for the first two coefficients. Taking these into account, we find that

:

f = Xf + X^2 f + X

(this is the crucial step; recurrence relations can almost always be translated into equations for the generating functions). Solving this equation for ''f'', we get

:

f = rac{X} {1 - X - X^2}

The denominator can be factored using the Golden Ratio φ₁ = (1 + √5)/2 and φ₂ = (1 − √5)/2, and the technique of Partial Fraction Decomposition yields

:

f = rac{1 / \sqrt{5}} {1-\phi_1 X} - rac{1/\sqrt{5}} {1- \phi_2 X}

These two formal power series are known explicitly because they are Geometric Series ; comparing coefficients, we find the explicit formula

:

F_n = rac{1} {\sqrt{5}} (\phi_1^n - \phi_2^n).

APPLICATIONS

Generating functions are used to

Find Recurrence Relation s for sequences – the form of a generating function may suggest a recurrence formula.

Find relationships between sequences – if the generating functions of two sequences have a similar form, then the sequences themselves are probably related.

Explore the asymptotic behaviour of sequences.

Prove identities involving sequences.

Solve Enumeration problems in Combinatorics .

Evaluate infinite sums.

OTHER GENERATING FUNCTIONS

Examples of Polynomial Sequence s generated by more complex generating functions include:

Difference Polynomials

Generalized Appell Polynomials

Q-difference Polynomial s

	APPAREL
	BABY
	BEAUTY
	BOOKS
	CAR TOYS
	CELL PHONES
	DVD'S
	ELECTRONICS
	GOURMET FOOD
	GROCERIES
	HEALTH & PERSONAL
	HOME & GARDEN
	JEWELRY
	MUSIC
	MUSIC INSTRUMENTS
	OFFICE PRODUCTS
	SOFTWARE
	SPORTING GOODS
	TOOLS & HARDWARE
	TOYS
	VIDEO GAMES
	SHOPPING HOME

	MORE SHOPPING...

	CATEGORIES ABOUT GENERATING FUNCTION

	combinatorics

	exponentials

Information About

Generating Function