8: Generating Functions and Recursion
- Page ID
- 60109
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\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]{\| #1 \|}\) \( \newcommand{\inner}[2]{\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]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
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.