Skip to main content
Contents Embed Prev Up Next \(\newcommand{\set}[1]{\{#1\}}
\newcommand{\ints}{\mathbb{Z}}
\newcommand{\posints}{\mathbb{N}}
\newcommand{\rats}{\mathbb{Q}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\complexes}{\mathbb{C}}
\newcommand{\twospace}{\mathbb{R}^2}
\newcommand{\threepace}{\mathbb{R}^3}
\newcommand{\dspace}{\mathbb{R}^d}
\newcommand{\nni}{\mathbb{N}_0}
\newcommand{\nonnegints}{\mathbb{N}_0}
\newcommand{\dom}{\operatorname{dom}}
\newcommand{\ran}{\operatorname{ran}}
\newcommand{\prob}{\operatorname{prob}}
\newcommand{\Prob}{\operatorname{Prob}}
\newcommand{\height}{\operatorname{height}}
\newcommand{\width}{\operatorname{width}}
\newcommand{\length}{\operatorname{length}}
\newcommand{\crit}{\operatorname{crit}}
\newcommand{\inc}{\operatorname{inc}}
\newcommand{\HP}{\mathbf{H_P}}
\newcommand{\HCP}{\mathbf{H^c_P}}
\newcommand{\GP}{\mathbf{G_P}}
\newcommand{\GQ}{\mathbf{G_Q}}
\newcommand{\AG}{\mathbf{A_G}}
\newcommand{\GCP}{\mathbf{G^c_P}}
\newcommand{\PXP}{\mathbf{P}=(X,P)}
\newcommand{\QYQ}{\mathbf{Q}=(Y,Q)}
\newcommand{\GVE}{\mathbf{G}=(V,E)}
\newcommand{\HWF}{\mathbf{H}=(W,F)}
\newcommand{\bfC}{\mathbf{C}}
\newcommand{\bfG}{\mathbf{G}}
\newcommand{\bfH}{\mathbf{H}}
\newcommand{\bfF}{\mathbf{F}}
\newcommand{\bfI}{\mathbf{I}}
\newcommand{\bfK}{\mathbf{K}}
\newcommand{\bfP}{\mathbf{P}}
\newcommand{\bfQ}{\mathbf{Q}}
\newcommand{\bfR}{\mathbf{R}}
\newcommand{\bfS}{\mathbf{S}}
\newcommand{\bfT}{\mathbf{T}}
\newcommand{\bfNP}{\mathbf{NP}}
\newcommand{\bftwo}{\mathbf{2}}
\newcommand{\cgA}{\mathcal{A}}
\newcommand{\cgB}{\mathcal{B}}
\newcommand{\cgC}{\mathcal{C}}
\newcommand{\cgD}{\mathcal{D}}
\newcommand{\cgE}{\mathcal{E}}
\newcommand{\cgF}{\mathcal{F}}
\newcommand{\cgG}{\mathcal{G}}
\newcommand{\cgM}{\mathcal{M}}
\newcommand{\cgN}{\mathcal{N}}
\newcommand{\cgP}{\mathcal{P}}
\newcommand{\cgR}{\mathcal{R}}
\newcommand{\cgS}{\mathcal{S}}
\newcommand{\bfn}{\mathbf{n}}
\newcommand{\bfm}{\mathbf{m}}
\newcommand{\bfk}{\mathbf{k}}
\newcommand{\bfs}{\mathbf{s}}
\newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}}
\newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}}
\newcommand{\surjection}{\xrightarrow[\text{onto}]{}}
\newcommand{\nin}{\not\in}
\newcommand{\prufer}{\text{prüfer}}
\DeclareMathOperator{\fix}{fix}
\DeclareMathOperator{\stab}{stab}
\DeclareMathOperator{\var}{var}
\newcommand{\inv}{^{-1}}
\newcommand{\ds}{\displaystyle}
\newcommand{\mbf}[1]{\mathbf{#1}}
\newcommand{\mc}[1]{\mathcal{#1}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Handout 9.1 Introduction to Advancement Operators
Rabbits
\(f_{n}= f_{n-1}+f_{n-2}\text{,}\) \(f_{1}=1\text{,}\) \(f_{2}=1\)
Strings
\(t_{n+2}= 3t_{n+1}-t_{n}\text{,}\) \(t_{1}=3\text{,}\) \(t_{2}=8\)
Regions
\(r_{n+1}= r_{n} + (n+1)\text{,}\) \(r_{1}=2\)
Definition 9.1 .
A linear recurrence equation is of the form
\begin{equation*}
c_{0}(n)a_{n+k}+ c_{1}(n)a_{n+k-1}+ c_{2}(n)a_{n+k-2}+ \dots+c_{k}(n)a_{n}= g(n),
\end{equation*}
where \(k\ge1\) is an integer and \(g\colon\mathbb{Z}\to\mathbb{R}\) is a function.
If each
\(c_{0}(n),c_{1}(n),\dots,c_{k}(n)\) is a contant with
\(c_{0}(n),c_{k}(n)\neq0\text{,}\) then we say the equation has
constant coefficients .
Peer instruction question 1.
Definition 9.2 .
The linear recurrence equation
\begin{equation*}
c_{0}(n)a_{n+k}+ c_{1}(n)a_{n+k-1}+ c_{2}(n)a_{n+k-2}+ \dots+c_{k}(n)a_{n}= g(n),
\end{equation*}
is called homogeneous if \(g(n)=0\) for all \(n\text{.}\)
Peer instruction question 2.
An analogy to calculus (or differential equations).
Let’s write \(D\) for the differential operator \(d/dx\text{.}\) Solve the equation
\begin{equation*}
Df = 5f
\end{equation*}
where \(f\) is a differentiable function of \(x\) with \(f(0)=3\) and
Let
\(f\colon \mathbb{Z}\to \mathbb{R}\text{.}\) The
advancement operator \(A\) is defined so that
\(Af(n) = f(n+1)\) for all
\(n\in \mathbb{Z}\text{.}\)
For
\(p\) a positive integer,
\(A^{p}f(n)\) denotes applying
\(A\) to
\(f(n)\) \(p\) times.
Activity 9.1.1 .
Rewrite each of the following expressions so that it does not use the advancement operator.
\(\displaystyle A^2f(4)\)
\(\displaystyle A^2f(n)\)
\(\displaystyle A^7f(n)\)
\(\displaystyle A^pf(n)\)
Activity 9.1.2 .
(a) Let
\(f(n) = 3n+4\text{.}\) Verify that
\((A^{3}-2A^{2}+7A+2)f(2) = 98\text{.}\)
(b)
Write each of the following recurrence equations as advancement operator equations.
\(\displaystyle t_{n+2}= 3t_{n+1}-t_{n}\)
\(\displaystyle r_{n+1}= r_{n} + (n+1)\)
\(\displaystyle f_{n}= f_{n-1}+f_{n-2}\)
