Generating Functions
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 7 Generating Functions
Recall that the basic goal with a recursively-defined sequence, is to find an explicit formula for the \(n\)th term of the sequence. Generating functions will allow us to do this.
Summary.
If \(n>0\) is an integer, then
\begin{equation*}
\binom{-n}{r}=(-1)^r\binom{n+r-1}{r}\text{.}
\end{equation*}
The Generalised Binomial Theorem
\(\displaystyle 1+x+\ldots +x^k= (1-x^{k+1})/(1-x)\)
using generating functions for counting things
Important definitions: