Back To Course

Math 108: Discrete Mathematics11 chapters | 88 lessons

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.

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.

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

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.

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:

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:

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:

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:

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:

If we shift this sequence right, i.e., placing 0 as the first element and shifting the rest of the sequence right, we will get the sequence of natural numbers seen at the beginning of this lesson. It is easy to see that the corresponding generating function will have all its terms multiplied by an additional *x* (*x* will become *x* squared, *x* squared will become *x* cubed, and so on). Therefore, again considering the distributive property, the shifting process of one single 0 will multiply the generating function by *x*.

Generalizing this right-shifting operation to include any number *z* of zeros at the beginning of the sequence, we will obtain a generating function that is the multiplication of the original generating function by *x* power *z*, e.g. with *z = 3*:

The last operation we will look at is the **multiplication** of two sequences. The only tricky part in this case is to understand what is meant by the multiplication of sequences. In this context, the multiplication of sequences *A* and *B* results in a sequence *C*. The *i*-th element is a sum of *i* products of one element of *A* by one element of *B* taken in the reverse order. The formal definition of each of the elements of the sequence *C* is then expressed as below:

Therefore, a product sequence *C* of sequences *A* and *B* has a generating function that is the product of the generating functions of *A* and *B*. To illustrate, let's see the product of two previously shown sequences:

Note that the elements of sequence *C* are obtained as:

- First element: (1 x 1) = 1
- Second element: (1 x -1) + (2 x 1) = -1 + 2 = 1
- Third element: (1 x 1) + (2 x -1) + (3 x 1) = 1 - 2 + 3 = 2
- Fourth element: (1 x -1) + (2 x 1) + (3 x -1) + (4 x 1) = -1 + 2 - 3 + 4 = 2
- Fifth element: (1 x 1) + (2 x -1) + (3 x 1) + (4 x -1) + (5 x 1) = 1 - 2 + 3 - 4 + 5 = 3
- Sixth element: (1 x -1) + (2 x 1) + (3 x -1) + (4 x 1) + (5 x -1) + (6 x 1) = -1 + 2 - 3 + 4 - 5 + 6 = 3
- and so on ...

To better deal with sequences, we have now seen how to represent a sequence by a **generating function** and we have learned about four operations that can be executed around sequences represented as generating functions: **scaling**, **addition**, **right-shifting** and **multiplication**.

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

Create your account

Are you a student or a teacher?

Already a member? Log In

BackDid 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

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.

You are viewing lesson
Lesson
5 in chapter 7 of the course:

Back To Course

Math 108: Discrete Mathematics11 chapters | 88 lessons

- Computer Science 332: Cybersecurity Policies and Management
- Introduction to SQL
- Computer Science 203: Defensive Security
- GRE Information Guide
- Computer Science 310: Current Trends in Computer Science & IT
- Probability & Sample Space
- Polynomials Overview
- FTCE: Equations and Inequalities
- FTCE: Analyzing Data and Drawing Conclusions
- FTCE: Data Analysis & Visualization
- What is the ASCP Exam?
- ASCPI vs ASCP
- MEGA Exam Registration Information
- MEGA & MoGEA Prep Product Comparison
- PERT Prep Product Comparison
- MTLE Prep Product Comparison
- What is the MTLE Test?

- Complex Variables: Definitions & Examples
- Real Analysis: Completeness of the Real Numbers
- Ancient Israel: Social Structure & Political Organization
- Holden Caulfield in Catcher in the Rye: Character & Analysis
- Life Cycle of a Sunflower Lesson Plan
- The Ugly Duckling Lesson Plan
- Types of Conflict Lesson Plan
- Quiz & Worksheet - Determining the Number of Main Ideas in a Text
- Quiz & Worksheet - Mildred in Fahrenheit 451
- Order of Events in Narratives: Quiz & Worksheet for Kids
- Quiz & Worksheet - The Square Root Property
- Flashcards - Measurement & Experimental Design
- Flashcards - Stars & Celestial Bodies
- Next Generation Science Standards
- Trigonometry Worksheets

- Fundamentals of Nursing Syllabus Resource & Lesson Plans
- Middle School US History: Tutoring Solution
- UExcel Physics: Study Guide & Test Prep
- High School Physics: Homeschool Curriculum
- Technical Writing Syllabus Resource & Lesson Plans
- WEST History: Imperialism & Colonization
- THEA Test: Quadratic Equations
- Quiz & Worksheet - Characteristics of Hexane
- Quiz & Worksheet - Frame Narrative
- Quiz & Worksheet - Characteristics of Greek Tragedy
- Quiz & Worksheet - Types of Distribution Systems
- Quiz & Worksheet - Characteristics of Discouraged Workers

- Annelid Circulatory System
- How to Find the Centroid of a Triangle
- What's in Common Core Standards Appendix C?
- SAT Registration & Test Dates
- What Is Science? - Lesson Plan
- How to Ace the MCAT
- Easy Science Experiments to Do at Home
- Preparing for the AP Biology Exam: Tips & Tricks
- Youth Suicide Prevention Programs
- 504 Plans in Wisconsin
- DNA Experiments for Kids
- 504 Plans in Missouri

- Tech and Engineering - Videos
- Tech and Engineering - Quizzes
- Tech and Engineering - Questions & Answers

Browse by subject