Back To Course

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

Back To Course

Math 108: Discrete Mathematics11 chapters | 80 lessons

- ILTS Physical Education (144): Study Guide & Practice
- OSAT Physical Education/Health/Safety (CEOE) (012): Study Guide & Practice
- NYSTCE Physical Education (076): Study Guide & Practice
- ILTS Health Careers (173): Study Guide & Practice
- OSAT Biological Sciences (CEOE) (010): Study Guide & Practice
- Careers in Healthcare
- Flexibility, Strength & Endurance
- Conditioning & Training Principles
- Motor Development & Learning Overview
- Overview of Safety Issues in Physical Education
- AFOQT Cost
- What Does the HESI A2 Nursing Exam Consist of?
- How to Learn Pharmacology for NCLEX
- What Are Considered Higher-Level Questions on the NCLEX?
- How to Study for NCLEx in 2 Weeks
- How Hard Is the ASVAB
- How Long is the HESI A2 Nursing Exam?

- Lazarillo de Tormes: Summary, Analysis & Theme
- Graphs in Discrete Math: Definition, Types & Uses
- Supplementary & Functional Curriculum: Selection & Implementation
- Scaffolding in Teaching: Tips & Strategies
- Creating a Veteran Recruitment & Hiring Program: Resources & Best Practices
- MySQL Commands: List & Examples
- Creating an Inclusive Workplace Environment for Veterans: Importance & Strategies
- Installing MySQL for Database Programming
- Quiz & Worksheet - Comedy in A Midsummer Night's Dream
- Quiz & Worksheet - Declarative vs. Imperative Sentences
- Quiz & Worksheet - Instruction for Reading & Writing Fluency
- Quiz & Worksheet - Components of a Sewing Machine
- Quiz & Worksheet - How to Assess Leadership in Inclusive Performance Reviews
- Flashcards - Measurement & Experimental Design
- Flashcards - Stars & Celestial Bodies

- CSET Physical Education Subtest III (131): Practice & Study Guide
- AP Music Theory: Homeschool Curriculum
- Across Five Aprils Study Guide
- Praxis Psychology (5391): Practice & Study Guide
- Homeschooling Facts for Parents
- Group Decision Making: Lesson Plans
- Polar Coordinates & Parameterizations Lesson Plans
- Quiz & Worksheet - Features of Selective Attention
- Quiz & Worksheet - Continuous Reinforcement
- Quiz & Worksheet - Understanding White Privilege
- Quiz & Worksheet - Algorithms in Psychology
- Quiz & Worksheet - Types of Entrepreneurship

- Employee Discipline in the Workplace: Procedures & Principle
- The Gold Rush Forty-Niners: History & Definition
- What is National Board Certification?
- What is Professional Development for Teachers?
- Fourth Grade South Carolina Science Standards
- New York State (NYS) Common Core Standards
- Lesson Plan Ideas for the First Day of School
- Utah Science Standards for 4th Grade
- Poetry Books & Activities for Kindergarten
- Stanford Standardized Test Requirements
- Fun Math Games for the Classroom
- Common Core Standards in Maine

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

Browse by subject