# 8: Generating Functions and Recursion

• • Joy Morris
• University of Lethbridge
$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

We’ve seen how the Generalised Binomial Theorem can be used to extract coefficients from a certain sort of generating function. Before we proceed with learning how to use generating functions to find explicit formulas for the nth term of a recursively-defined sequence, we need to know how to extract coefficients from some more complicated expressions.

• 8.1: Partial Fractions
If a generating function looks like 1/(1+ax^i)^j, we can use the Generalised Binomial Theorem to find the coefficient of x^r. But what can we do if the generating function looks like 1/(a+bx+cx^2), for example, or even more complicated expressions? One tool that can help us extract coefficients from some expressions like this, is the method of partial fractions.
• 8.2: Factoring Polynomials
You should be familiar with the quadratic formula, which allows us to factor any polynomial of degree two, into linear factors. Recall that in order to use the Generalised Binomial Theorem, we need the constant term to be 1. If you are very comfortable with algebraic manipulations, you can use the quadratic formula to factor and then divide each factor by the appropriate value so as to make the constant term 1.
• 8.3: Using Generating Functions to Solve Recursively-Defined Sequences
At last, we are ready to apply the mechanics we’ve introduced in this chapter, to find an explicit formula for the nth term of a recursively-defined sequence. This method is probably most easily understood using examples found in this section.
• 8.4: Summary
This page contains the summary of the topics covered in Chapter 8.

This page titled 8: Generating Functions and Recursion is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Joy Morris.