Back To Course

Math 108: Discrete Mathematics11 chapters | 86 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
4 in chapter 7 of the course:

Back To Course

Math 108: Discrete Mathematics11 chapters | 86 lessons

- Computer Science 336: Network Forensics
- Computer Science 220: Fundamentals of Routing and Switching
- Global Competency Fundamentals & Applications
- Introduction to the Principles of Project Management
- Praxis Elementary Education: Reading & Language Arts - Applied CKT (7902): Study Guide & Practice
- Practical Applications for Business Ethics
- Practical Applications for Marketing
- Practical Applications for HR Management
- Practical Applications for Organizational Behavior
- Analyzing Texts Using Writing Structures
- MBLEx Prep Product Comparison
- AEPA Prep Product Comparison
- ASCP Prep Product Comparison
- NCE Prep Product Comparison
- TASC Test Score Information
- What is the TASC Test?
- Praxis Prep Product Comparison

- Diclofenac vs. Ibuprofen
- Developing & Managing a High-Quality Library Collection
- Library Space Planning
- Literacy Strategies for Teachers
- Arithmetic Operations in R Programming
- Practical Application: Understanding Employee Behavior
- Positive Global Outcomes of Global Competence
- Practical Application: Color Wheel Infographic
- Quiz & Worksheet - Developing a Learner-Centered Classroom
- Quiz & Worksheet - Technology for Teaching Reading
- Quiz & Worksheet - Pectoralis Major Anatomy
- Quiz & Worksheet - Oral & Written Communication Skills
- Quiz & Worksheet - How to Teach Reading to ELL Students
- Flashcards - Measurement & Experimental Design
- Flashcards - Stars & Celestial Bodies

- ILTS English Language Arts (207): Test Practice and Study Guide
- CLEP College Algebra: Study Guide & Test Prep
- Earth Science: Middle School
- High School World History: Homeschool Curriculum
- SAT Prep: Practice & Study Guide
- Accounting Basics: Homework Help
- FTCE: Essay Skills
- Quiz & Worksheet - Counseling Issues in Colleges and Universities
- Quiz & Worksheet - Mass, Weight & the Effect of Gravity
- Quiz & Worksheet - Life Cycle of the Sun
- Quiz & Worksheet - Glaciers
- Quiz & Worksheet - Properties of Electric Currents

- Endothermic and Exothermic Reactions
- Corporal Punishment: History & Effects
- Collage Lesson Plan
- STEM & Next Generation Science Standards
- Homeschooling in New Jersey
- Leadership & Organizational Behavior: Assignment 1 - Organizational Change
- Minnesota State Social Studies Standards
- Tennessee Homeschool Laws
- Cellular Respiration Lesson Plan
- Homeschooling in Utah
- The Difference Between the GMAT & GRE
- Nutrition Lesson Plan

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

Browse by subject