Skip to main content
Mathematics LibreTexts

7: Generating Functions

  • Page ID
  • \( \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}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Recall that the basic goal with a recursively-defined sequence, is to find an explicit formula for the nth term of the sequence. Generating functions will allow us to do this.

    • 7.1: What is a Generating Function?
      A generating function is a formal structure that is closely related to a numerical sequence, but allows us to manipulate the sequence as a single entity, with the goal of understanding it better.
    • 7.2: The Generalized Binomial Theorem
      We are going to present a generalised version of the special case of Theorem 3.3.1, the Binomial Theorem, in which the exponent is allowed to be negative.
    • 7.3: Using Generating Functions To Count Things
      As you might expect of something that has come up in our study of enumeration, generating functions can be useful in solving problems about counting. We’ve already seen this in the Binomial Theorem. In fact, the argument we used to prove the Binomial Theorem explained why this works. Therefore, we can use similar reasoning to solve other counting questions.
    • 7.4: Summary
      This page contains the summary of the topics covered in Chapter 7.

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

    • Was this article helpful?