Generating Function in Discrete Math: Definition & Examples

Instructor: Paulo Lemelle Fernandes

Paulo has been a Computer Science Professor and researcher for more than 25 years. He has a Ph.D. degree from Institut National Polytechnique de Grenoble, France (1998).

When you have to mathematically deal with an infinite sequence of numbers, it might be easier if you represent it as a Generating Function, since there are lots of mathematical tools for functions, and very few for sequences. This lesson will discuss the generating function in discrete math.

Ordinary Generating Functions

Let's say you have a sequence of numbers that for some reason you need to deal with mathematically. For example, you need to prove some properties about the sequence, to try and generalize its elements, to look for a closed form (a direct form that can be numerically computed), or to express its elements or its sum. A clever discrete math trick to make your life easier is to code this sequence into a polynomial, i.e., the sum of powers of a variable x with each coefficient being one of the sequence numbers. Such codification is called ordinary generating functions. Although there are other kinds of generating functions, in this lesson we will limit ourselves to this simpler, and very useful kind.

Given a simple sequence with the natural numbers, the coded corresponding generating function is represented below.


gen_func_N


The formulation of this generating function is expressed as the summation below, which has a closed form:


numerical_value_for_gen_func_N


Once you have a sequence represented as a generating function there are lots of things that you can then easily do. Let's take a look at four operations that you can apply to sequences and the corresponding effect it has on their generating functions. These operations are:

  • Scaling
  • Addition
  • Right-shifting
  • Product

Before going over the operations, keep in mind that a generating function is a form to express a sequence, and it is not really important to numerically compute it. In other words, let x be just a parameter of the generation function, and not bother to replace it with a numerical value.

Scaling a Generating Function

The first basic operation is scaling, which is simply multiplying all elements of the sequence for the same value (a scalar, thus scaling).

Logically, when you multiply all elements in a sequence by the same value, the generating function, as a sum of terms that have as coefficients the elements of the sequence, has all its terms multiplied by this value. It is a simple application of the good old distributive of product over sum property (a (b + c) = ab + ac). In terms of sequences and generating functions, multiplying a given sequence for a value k results in a sequence that is represented by the generating function of the original sequence multiplied by this same value (k). Exemplifying it for the sequence of natural numbers and its corresponding generating function multiplied by a value k we have the following:


scaling_gen_func_N


Addition of Two Generating Functions

The second operation we will look at is the addition of two sequences. The corresponding effect on their respective generating functions is once again quite straight-forward. In fact, it is the logical result of the commutative property of the sum (a + b + c + d = a + c + b + d). Therefore, the sum of two sequences results in a sequence that is represented by the sum of the two original sequence generating functions. To illustrate, let's use the following two simple sequences below:


two_gen_funcs


The addition of these two sequences results in another sequence that is coded by a generation function that is the sum of the two original ones:


adding_two_gen_funcs


Note that this same sequence codification could be found applying the scaling operation. In this case, multiplying by 2, the generation function of another traditional sequence results as follows:


on_off_gen_func


Right-Shifting a Sequence

A simple, yet useful operation is to shift a sequence including a number of zeros in the beginning of the sequence, in what is called right-shifting a sequence. Let's see how it impacts the corresponding generation Function.

Let's take a look at another classic sequence: the natural numbers starting from the number 1 and the corresponding generating function:


gen_func_Nstar


To unlock this lesson you must be a Study.com Member.
Create your account

Register for a free trial

Are you a student or a teacher?

Unlock Your Education

See for yourself why 30 million people use Study.com

Become a Study.com member and start learning now.
Become a Member  Back
What teachers are saying about Study.com
Free 5-day trial

Earning College Credit

Did you know… We have over 160 college courses that prepare you to earn credit by exam that is accepted by over 1,500 colleges and universities. You can test out of the first two years of college and save thousands off your degree. Anyone can earn credit-by-exam regardless of age or education level.

To learn more, visit our Earning Credit Page

Transferring credit to the school of your choice

Not sure what college you want to attend yet? Study.com has thousands of articles about every imaginable degree, area of study and career path that can help you find the school that's right for you.

Create an account to start this course today
Try it free for 5 days!
Create An Account
Support