Generating Functions and Recursion
Skip to main content \(\def\xautoref#1{\ref{#1}}
\renewcommand{\thepage}{\roman{page}}
\renewcommand{\thepage}{\arabic{page}}
\def\radius{3}
\def\steps{18}
\renewcommand{\arraystretch}{2.2}
\def\openbox{\undefined}
\def\ellipsea{[rotate=30](0,0) ellipse (3cm and 2cm)}
\def\thm{\undefined}
\def\ellipseb{[rotate=150](3,1.72) ellipse (3cm and 2cm)}
\def\cor{\undefined}
\def\ellipsec{[rotate=270](3,-1.7) ellipse (3cm and 2cm)}
\def\prop{\undefined}
\def\lem{\undefined}
\def\defn{\undefined}
\def\rem{\undefined}
\renewcommand{\indexname}{Index}
\newcommand{\noneed}{(\!\emph{You do not need to show your work.})}
\renewcommand{\indexname}{List of Notation}
\newcommand{\multiset}[2]{\left(\!\binom{#1}{#2}\!\right)}
\newcommand{\tmultiset}[2]{\big(\!\binom{#1}{#2}\!\big)}
\newcommand{\twoonone}{\twocolumn
\setlength{\textwidth}{9.5 in}
\setlength{\textheight}{7.25 in}
\setlength{\columnsep}{0.5in}
\hoffset=-1in
\voffset=-1in
}
\newcommand{\theProbPart}{\Alph{ProbPart}}
\newcommand{\practiceproblems}{
\section*{Practice Exercises}
\addcontentsline{toc}{section}{Practice Exercises}
}
\newcommand{\problempart}{
\textbf{Part \Alph{ProbPart}}\
}
\newcommand{\solutions}{$\star$}
\newcommand{\leftsolutions}{\hspace{-2.2em}\makebox[2em][l]{\solutions}}
\newcommand{\solutionsection}[2]{
\section*{Chapter {\ref{#1}} Exercise {\ref{#2}}}
}
\newcommand{\nextSeq}{\stepcounter{countSeq}\arabic{countSeq}, }
\newcommand{\noSeq}{\stepcounter{countSeq}}
\newcommand{\lastSeq}{and \stepcounter{countSeq}\arabic{countSeq} }
\renewcommand{\thechapter}{\arabic{chapter}}
\def\chapterrunhead{\partrunhead}
\def\sectionrunhead{\partrunhead}
\newcommand{\TTbf}[1]{\textbf{\large #1}}
\newcommand{\whline}{\noalign{\global\savedwidth\arrayrulewidth \global\arrayrulewidth 2pt}\hline
\noalign{\global\arrayrulewidth\savedwidth}}
\newcommand{\leftnone}[1]{\hbox to 0pt{#1\hss}}
\newcommand{\hypend}{\whline}
\newcommand{\nohypotheses}{ \\}
\newcommand{\AndIntro}[2]{$\eand$-intro (lines ${#1}$ and ${#2}$)}
\newcommand{\AndIntroB}[2]{$\eand$-intro \\ (lines ${#1}$ and ${#2}$)}
\newcommand{\AndElim}[1]{$\eand$-elim (line ${#1}$)}
\newcommand{\OrIntro}[1]{$\eor$-intro (line ${#1}$)}
\newcommand{\OrElim}[2]{$\eor$-elim (lines ${#1}$ and ${#2}$)}
\newcommand{\IfIntro}[2]{$\eif$-intro (lines ${#1}$--${#2}$)}
\newcommand{\IfElim}[2]{$\eif$-elim (lines ${#1}$ and ${#2}$)}
\newcommand{\IffIntro}[2]{$\eiff$-intro (lines ${#1}$ and ${#2}$)}
\newcommand{\IffElim}[1]{$\eiff$-elim (line ${#1}$)}
\newcommand{\IffElimB}[2]{$\eiff$-elim \\ (lines ${#1}$ and ${#2}$)}
\newcommand{\NotIntro}[2]{Proof by Contradiction (lines ${#1}$--${#2}$)}
\newcommand{\NotElim}[1]{$\enot$-elim (line ${#1}$)}
\newcommand{\Repeat}[1]{repeat~(line ${#1}$)}
\newcommand{\AllElim}[1]{$\forall$-elim (line ${#1}$)}
\newcommand{\AllElimSet}[2]{$\forall$-elim (lines ${#1}$ and~${#2}$)}
\newcommand{\AllIntro}[1]{$\forall$-intro (line ${#1}$)}
\newcommand{\AllIntroSet}[2]{$\forall$-intro (lines ${#1}$--${#2}$)}
\newcommand{\ExistElim}[3]{$\exists$-elim (lines ${#1}$ and ${#2}$--${#3}$)}
\newcommand{\ExistElimSet}[3]{$\exists$-elim (lines ${#1}$ and ${#2}$--${#3}$)}
\newcommand{\ExistIntro}[1]{$\exists$-intro (line ${#1}$)}
\newcommand{\ExistIntroSet}[2]{$\exists$-intro (lines ${#1}$ and~${#2}$)}
\newcommand{\EqualIntro}{$=$-intro}
\newcommand{\EqualElim}[2]{$=$-elim (lines ${#1}$ and~${#2}$)}
\newcommand{\NotSimplify}[1]{$\enot$-simplify (line $#1$)}
\newcommand{\Cases}[3]{Proof by cases (lines $#1$, $#2$, and $#3$)}
\newcommand{\by}[2]{#1 (#2)}
\newcommand{\var}[1]{\text{#1}}
\newcommand{\bigset}[2]{\left\{\, #1
\mathrel{\left|
\right.} #2 \,\right\} }
\renewcommand{\see}[1]{{(}see~\ref{#1}{)}}
\newcommand{\seeex}[1]{{(}see Exer.~\ref{#1}{)}}
\newcommand{\fullseeex}[2]{{(}see Exer.~\ref{#1}\pref{#1-#2}{)}}
\newcommand{\fullcsee}[2]{(see~\fullcref{#1}{#2})}
\newcommand{\fullsee}[2]{(see~\fullref{#1}{#2})}
\newcommand{\fullcref}[2]{\xautoref{#1}\pref{#1-#2}}
\newcommand{\fullCref}[2]{\xautoref{#1}\pref{#1-#2}}
\newcommand{\fullcf}[2]{(cf.~\ref{#1}\pref{#1-#2})}
\newcommand{\cfSect}[1]{(cf.~\S\ref{#1})}
\newcommand{\power}{\mathcal{P}}
\newcommand{\compose}{\mathbin{\circ}}
\newcommand{\Id}{I}
\newcommand{\sm}{\smallsetminus}
\newcommand{\comp}[1]{\overline{#1}}
\newcommand{\rel}{\mathrel{R}}
\newcommand{\divides}{\mathrel{|}}
\newcommand{\nmids}{\nmid}
\newcommand{\class}[1]{ \overline{#1}}
\newcommand{\edgeG}{\mathrel{\displaystyle\mathop{\edge}\limits^G}}
\newcommand{\edgeH}{\mathrel{\displaystyle\mathop{\edge}\limits^H}}
\newcommand{\edgeK}{\mathrel{\displaystyle\mathop{\edge}\limits^K}}
\newcommand{\edgeGone}{\mathrel{\displaystyle\mathop{\edge}\limits^{G_1}}}
\newcommand{\edgeGtwo}{\mathrel{\displaystyle\mathop{\edge}\limits^{G_2}}}
\newcommand{\edgeGthree}{\mathrel{\displaystyle\mathop{\edge}\limits^{G_3}}}
\newcommand{\arc}{\mathrel{\lower3pt\hbox{\LARGE$\rightarrow$}}}
\newcommand{\arcG}{\mathrel{\displaystyle\mathop{\arc}\limits^G}}
\newcommand{\arcH}{\mathrel{\displaystyle\mathop{\arc}\limits^H}}
\renewcommand{\vec}[1]{\overrightarrow{#1}}
\newcommand{\boxprod}{\mathbin{\square}}
\newcommand{\headrulewidth}{0pt}
\renewcommand{\sectionmark}[1]{}
\newcommand{\optional}{{\upshape(optional)}}
\newcommand{\blue}[1]{{\color{blue}#1}}
\newcommand{\faint}[1]{{\scriptsize\color{blue}#1}}
\newcommand{\SL}{Propositional Logic}
\newcommand{\QL}{First-Order Logic}
\newcommand{\univ}{\script{U}}
\renewcommand{\implies}{\eif}
\newcommand{\?}{\mathrel{\displaystyle\mathop{=}\limits^?}}
\newcommand{\pref}[1]{\eqref{#1}}
\newcommand{\fullref}[2]{\ref{#1}\pref{#1-#2}}
\newcommand{\hint}[1]{{\small{[}\textit{Hint:} #1{]}}}
\renewcommand{\natural}{\mathbb{N}}
\newcommand{\rational}{\mathbb{Q}}
\newcommand{\real}{\mathbb{R}}
\newcommand{\integer}{\mathbb{Z}}
\newcommand{\iso}{\cong}
\newcommand{\bibd}{\mathcal{B}}
\newcommand{\code}{\mathcal{C}}
\newcommand{\ul}{\underline}
\newcommand{\mytheoremheaderfont}[1]{{\bfseries\sffamily\MakeUppercase{#1}}}
\newcommand{\optargfont}[1]{{\bfseries\sffamily #1}}
\newcommand{\theexerthm}{\arabic{exerthm}}
\newcommand{\proofnamestyle}{\bfseries\sffamily}
\renewcommand{\thepart}{\Roman{part}}
\renewcommand{\contentsname}{\Huge\bfseries\sffamily Contents}
\newcommand{\tocsectionlabelwidth}{0.9cm}
\newcommand{\tocsummary}[3]{
\indentlabel{\hbox to \tocsectionlabelwidth{\hss}}\enspace#3}
\renewcommand{\solutions}{}
\newcommand{\notationentry}[2]{\item #1, #2 }
\newcommand{\notationindexname}{List of Notation}
\newcommand{\notationchapter}[2]{
\item \hbox{\hskip-\itemindent \chaptername\ #2. #1} }
\renewcommand{\includeonly}[1]{}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\)
Chapter 8 Generating Functions and Recursion
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 \(n\)th term of a recursively-defined sequence, we need to know how to extract coefficients from some more complicated expressions.
Summary.
Method of partial fractions
Formula for factoring quadratic polynomials into the required form
Applying generating functions to recursively-defined sequences