Introduction to Generating Functions | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 8.12 Free with a free account

Introduction to Generating Functions

Discrete Mathematics · Chapter 8: Binomial Probability, Recurrence Relations, and Generating FunctionsSection 8.12 · lesson 57 of 8711 min · free with a free account

← Recurrences in Divide-and-Conquer AlgorithmsNext lesson: The Inclusion-Exclusion Principle →

Earn 4 college credits for Discrete MathematicsRecommended for credit by NCCRS · Math 230 · self-paced · one payment, lifetime access
Enroll in Discrete Mathematics · $250 →Download the syllabus (PDF)

In this lesson

A whole sequence packed into one power series - and algebra doing the counting.

  • Define an ordinary generating function
  • Move between a sequence and its closed form
  • Use shifting and convolution
  • Solve a recurrence with a generating function

Transcript

Everything said in the video, section by section (1,524 words). Read along, or search it.

Binomial Probability, Recurrence Relations, and Generating Functions

Introduction to Generating Functions

This section introduces generating functions, a second strategy for recurrences and counting problems. Instead of treating a sequence as a list of numbers, a generating function packages the whole sequence into one algebraic object. Then ordinary algebra does the counting. We'll build the definition, move between sequences and their closed forms, and solve a recurrence with no characteristic equation at all.

The Opening Problem

12 Tokens, 4 Capped Zones

A delivery dispatcher at a ride-share company needs to count something oddly specific. How many distinct ways can twelve identical priority tokens be assigned across four city zones, when each zone has a cap? Solving problems one at a time, like the recurrences in section eight point ten, works, but it treats each one as an isolated puzzle. There's a second strategy, and it works by changing what a sequence is. Package the entire sequence into a single formal power series, and let ordinary polynomial algebra, multiplying, dividing, and shifting, do the combinatorial counting. The same tool helps estimate how many parse trees a grammar allows, count error-correcting codewords of a given weight, and count routes through layers of network switches.

Definition 8.12.1

The Ordinary Generating Function

An ordinary generating function encodes an infinite sequence, as the coefficients of a power series in a symbol x. G of x is a zero, plus a one x, plus a two x squared, and so on. The word formal is doing real work. x is never given a numeric value, and whether the series converges doesn't matter. It's a bookkeeping structure, not a function to evaluate. The coefficient of x to the n is exactly a n. It's written with square brackets, x to the n, applied to G of x. And two generating functions are equal exactly when every coefficient agrees.

Worked Example 8.12.1

3 Closed Forms to Know

Three sequences come up so often they're worth memorizing. The constant sequence of ones gives one plus x plus x squared, and so on. That's a geometric series, with closed form one over one minus x. That closed form is verified by cross-multiplying, not by convergence. One minus x, times the series, leaves only the one. Every other term cancels. So the two are formal inverses. The sequence one, r, r squared, and so on, gives one over one minus r x, by the same identity. And the binomial coefficients m choose zero through m choose m, followed by zeros, give one plus x, to the m. That's the binomial theorem. So a generating function doesn't even have to be infinite. This one's a polynomial.

Theorem 8.12.1

The Generalized Geometric Series

The most useful expansion beyond the geometric series is this. One over one minus x, to the k, is the sum of n plus k minus one, choose k minus one, times x to the n. It's proved by induction on k. The case k equals one is the geometric series. For larger k, write one over one minus x to the k as one over one minus x, times one over one minus x to the k minus one. Multiplying generating functions convolves their coefficients. So the coefficient of x to the n is a sum of binomial coefficients from the previous case. And that sum collapses, by the hockey stick identity, which follows from Pascal's rule in section five point seven. That gives exactly the claimed formula for k.

Worked Example 8.12.2

Reading a Sequence Out

Now read a sequence out of a closed form. Suppose G of x is three over one minus x, squared. Factor out the three. Then apply the theorem with k equal to two. One over one minus x, squared, has coefficients n plus one choose one, which is just n plus one. Multiply through by three. So a n equals three times n plus one. The sequence is three, six, nine, twelve, and so on, the positive multiples of three. Moving fluently in both directions, from a sequence to its generating function and back, is the actual skill here.

Theorem 8.12.2

Operations on Sequences, as Algebra

Generating functions solve recurrences once a few manipulations are in place. Each one turns an operation on a sequence into an operation on its generating function. Scaling. Multiplying G of x by a constant multiplies every coefficient by it. Addition. Adding two generating functions adds their coefficients term by term. Right shift. Multiplying by x moves every term one place to the right, and puts a zero in front. The coefficient of x to the n becomes a n minus one. And convolution. Multiplying two generating functions collects every product a i b k, with i plus k equal to n, into the coefficient of x to the n. The right shift is the workhorse, because a recurrence relates each term to earlier terms, and multiplying by x is exactly what reaches back.

Worked Example 8.12.3

Turn the Recurrence Into an Equation

Take the recurrence a n equals three a n minus one, plus two, for n at least one, with a zero equal to one. Let G of x be its generating function. Multiply the recurrence by x to the n, and sum over every n where it holds, from one on. The left side is G of x minus the n equals zero term, so G of x minus one. The first term on the right, by the shift rule, is three x times G of x. The second is a geometric series starting at n equals one. That's two over one minus x, minus its first term, which is two x over one minus x. So the recurrence has become one algebraic equation. G of x minus one equals three x G of x, plus two x over one minus x.

Worked Example 8.12.3

Solve for G(x), Then Read Off a(n)

Now solve for G of x, like any equation. Collect the G terms and simplify. G of x times one minus three x equals one plus x, over one minus x. So G of x is one plus x, over one minus x, times one minus three x. Split that with partial fractions. It's minus one over one minus x, plus two over one minus three x. Now read off the coefficients with the building blocks. a n is minus one times one, plus two times three to the n. That's two times three to the n, minus one. Check it. a zero is one, which matches. a one is three times one plus two, five, and the formula gives six minus one. a two is seventeen both ways. The recurrence became an equation, solved with ordinary algebra. The unknown just happened to be a power series, not a number.

Listing 1

Coefficients by Long Division

A short routine makes the coefficient extraction mechanical, for any fraction of polynomials. If G of x times the denominator equals the numerator, then matching coefficients of x to the n on both sides, gives each a n from the earlier ones. Running it on one plus x, over one minus four x plus three x squared, prints one, five, seventeen, fifty-three, one hundred sixty-one, and four hundred eighty-five. Each matches two times three to the n, minus one. For n equals five, that's two times two hundred forty-three, minus one.

Figure 1

A Round Trip Through Algebra

Here's the whole method as a round trip. Start with a sequence, and encode it as a generating function. Apply the recurrence, with shifting and summing, to get an algebraic equation for G of x. Solve it, use partial fractions, and extract a closed form for a n. Then check it against the original sequence. A combinatorial problem about terms becomes an algebra problem about one power series.

Comparing Methods

Characteristic Equation or Generating Function?

This table compares generating functions with the characteristic equation method from section eight point ten. The characteristic equation suits homogeneous or simply forced recurrences. It guesses r to the n, and finds the roots. Generating functions suit irregular forcing terms. The recurrence becomes one equation for G of x, and the closed form emerges from algebra, not a guess. Generating functions also handle systems of several recurrences naturally, though they take more setup by hand. Neither is strictly better. The forcing term, and how many recurrences are coupled, usually decide.

Back to the Tokens

1 Factor per Zone

Back to the dispatcher's tokens. Each zone contributes one polynomial factor, one plus x plus x squared, up to x to its cap. Multiply the four factors together. By convolution, the number of valid ways to assign twelve tokens, is the coefficient of x to the twelfth in that product. Section eight point thirteen develops exactly this multi-factor technique for counting with constraints.

Takeaways

Package, Manipulate, Extract

To summarize. An ordinary generating function encodes a whole sequence as the coefficients of one formal power series. x is never evaluated. One over one minus x, one over one minus r x, and one plus x to the m are the basic building blocks. Scaling, addition, shifting, and convolution turn sequence operations into algebra. So a recurrence becomes an equation for G of x, which is solved, and then coefficients are extracted. Here's something to think about. The example was first-order. Suppose the recurrence were second-order, like Fibonacci, with a zero equal to zero and a one equal to one. How many initial terms would have to be peeled off the left-hand sum, before the shift rule applies cleanly? Why does the order of the recurrence, and not its coefficients, decide that? And what would go wrong in the algebra if too few terms were removed?

About Discrete Mathematics at UPI Study

Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus Every course with PRO →

Why take it here

Why students take Discrete Mathematics with UPI Study

The math behind computer scienceDiscrete Mathematics is the mathematics of computer science: logic, proofs, sets, counting, probability and graphs underpin algorithms, data structures, cryptography and databases. Completing it now lets you qualify for those courses at your university.
Credit at a fraction of the priceThe same 4 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Introduction to Generating Functions

What is an ordinary generating function?
An ordinary generating function is a formal power series G(x)=a_0+a_1x+a_2x^2+\cdots whose coefficients are the terms of a sequence. The symbol x is never given a numeric value, and convergence does not matter, so the series is bookkeeping rather than a function to evaluate. The coefficient of x^n is a_n, and two generating functions are equal exactly when every coefficient matches.
How do you find the sequence from a closed form like 3/(1−x)^2?
Match the closed form to a known building block and read off the coefficients. Since \frac{1}{(1-x)^k}=\sum_{n\ge 0}\binom{n+k-1}{k-1}x^n, taking k=2 gives coefficients n+1. Multiplying by 3 gives a_n=3(n+1), so the sequence is 3, 6, 9, 12, and so on. Other basic blocks are \frac{1}{1-x}, \frac{1}{1-rx}, and (1+x)^m.
How do you solve a recurrence using a generating function?
Turn the recurrence into an algebraic equation for G(x), solve it, and extract coefficients. For a_n=3a_{n-1}+2 with a_0=1, multiply by x^n and sum over n\ge1 to get G-1=3xG+\frac{2x}{1-x}. Then G=\frac{1+x}{(1-x)(1-3x)}=\frac{-1}{1-x}+\frac{2}{1-3x}, so a_n=2\cdot3^n-1.
How do shifting and convolution work for generating functions?
Multiplying G(x) by x shifts every term one place right, so the coefficient of x^n becomes a_{n-1}. This is how a recurrence reaches back to earlier terms. Multiplying two generating functions is convolution: the coefficient of x^n in G(x)H(x) is the sum of a_ib_k over all i+k=n. Scaling and adding act term by term.

About the Discrete Mathematics course

How many college credits is Discrete Mathematics?
Discrete Mathematics (Math 230) carries a NCCRS credit recommendation for 4 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Discrete Mathematics cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Discrete Mathematics take?
It is self-paced with no deadlines. The 87 lessons total about 13 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 4 credits in Discrete Mathematics.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Discrete Mathematics →Download the syllabusEvery course with PRO →
Discrete Mathematics
4 credits · NCCRSEnroll →