Skip to main content
Contents Index Dark Mode Prev Up Next \(\def\versionnumber{1.54}
\def\JPicScale{0.7}
\def\versionyear{2018}
\def\JPicScale{0.7}
\def\versionmonth{July \versionyear}
\def\JPicScale{0.7}
\def\JPicScale{0.7}
\newcommand{\ix}[1]{#1\index{#1}}
\def\JPicScale{0.7}
\newcommand{\Z}{\mathbb{Z}}
\def\JPicScale{0.7}
\newcommand{\Q}{\mathbb{Q}}
\def\JPicScale{0.6}
\newcommand{\R}{\mathbb{R}}
\def\JPicScale{0.6}
\newcommand{\C}{\mathbb{C}}
\def\s{\sum_{k \geq 0}}
\newcommand{\N}{\mathbb{N}}
\def\sz{\sum_{ k \in \Z }}
\newcommand{\Chat}{\hat\C}
\def\JPicScale{0.7}
\newcommand{\Rhat}{\hat\R}
\def\i{\int_\gg}
\newcommand{\gd}{\delta}
\def\JPicScale{0.7}
\renewcommand{\gg}{\gamma}
\newcommand{\D}{\Delta}
\newcommand{\Dp}{\check{D}}
\DeclareMathOperator{\length}{length}
\DeclareMathOperator{\dist}{dist}
\DeclareMathOperator{\fLog}{\mathcal{L}\!og}
\DeclareMathOperator{\fArg}{\mathcal{A}rg}
\DeclareMathOperator{\Log}{Log}
\DeclareMathOperator{\Arg}{Arg}
\let\Im\relax
\let\Re\relax
\DeclareMathOperator{\Im}{Im}
\DeclareMathOperator{\Re}{Re}
\def\sz{\sum_{ k \in \Z }}
\def\s{\sum_{k \geq 0}}
\DeclareMathOperator{\Res}{Res}
\renewcommand{\emptyset}{\varnothing}
\newcommand{\Def}[1]{\textbf{#1}}
\newcommand{\hint}[1]{(\emph{Hint}: #1)}
\newcommand{\histremark}[1]{}
\newcommand{\histremarktwo}[2]{}
\newcommand{\listset}[1]{\left\{#1\right\}}
\newcommand{\makeset}[2]{\listset{#1\colon\,#2}}
\newcommand{\listseq}[1]{\left\langle#1\right\rangle}
\newcommand{\makeseq}[2]{\listseq{#1\colon\,#2}}
\newcommand{\ds}{\displaystyle}
\newcommand{\conj}[1]{\overline{#1}}
\newcommand{\abs}[1]{\left|#1\right|}
\newcommand{\zbar}{\overline{z}}
\def\o{\overline}
\newcommand{\fderiv}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\sderiv}[2]{\frac{\partial^2 #1}{\partial #2^2}}
\newcommand{\mderiv}[3]{\frac{\partial^2 #1}{\partial #2 \, \partial #3}}
\newcommand{\mat}[1]{\displaystyle\begin{bmatrix} #1 \end{bmatrix}}
\newcommand{\disp}[1]{$\displaystyle#1$}
\renewcommand{\th}{^{ th}}
\newcommand{\boldcdot}{\boldsymbol{\cdot}}
\newcommand{\diff}[1]{{d#1}}
\newcommand{\itref}[1]{\eqref{#1}}
\def\newnotes{
\begin{remarks}
\thenotes.
}
\def\writenote{
\vspace{10pt} \thenotes.
}
\newcommand{\putqed}{\pushQED{\qed}\popQED}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\newcommand{\fillinmath}[1]{\mathchoice{\underline{\displaystyle \phantom{\ \,#1\ \,}}}{\underline{\textstyle \phantom{\ \,#1\ \,}}}{\underline{\scriptstyle \phantom{\ \,#1\ \,}}}{\underline{\scriptscriptstyle\phantom{\ \,#1\ \,}}}}
\)
Section 10.3 Fibonacci Numbers
The Fibonacci numbers are a sequence of integers defined recursively through
\begin{align*}
f_0 \amp = 0\\
f_1 \amp = 1\\
f_n \amp = f_{n-1} + f_{n-2} \qquad \text{ for \(n \geq
2\) }\text{.}
\end{align*}
Let \(F(z) = \s f_k \, z^k\text{.}\)
Show that
\(F\) has a positive radius of convergence.
Show that the recurrence relation among the
\(f_n\) implies that
\(F(z) = \frac{z}{1 - z - z^2}\text{.}\) (
Hint : Write down the power series of
\(z \, F(z)\) and
\(z^2 \, F(z)\) and rearrange both so that you can easily add.)
Verify that
\begin{equation*}
\Res_{z=0} \left( \frac{1}{z^n (1 - z - z^2)} \right) \ = \ f_n\,\text{.}
\end{equation*}
Use the Residue
Theorem 9.2.2 to derive an identity for
\(f_n\text{.}\) (
Hint : Integrate
\begin{equation*}
\frac{1}{z^n (1 - z - z^2)}
\end{equation*}
around \(C[0,R]\) and show that this integral vanishes as \(R \to \infty\text{.}\) )
Your identity should involve the
golden ratio \(\frac{ 1 + \sqrt 5 }{ 2 }\text{.}\) Explain what is going on in the output of the following
SageMath prompt:
Generalize to other sequences defined by recurrence relations, e.g., the Tribonacci numbers
\begin{align*}
t_0 \amp = 0\\
t_1 \amp = 0\\
t_2 \amp = 1\\
t_n \amp = t_{n-1} + t_{n-2} + t_{n-3} \qquad \text{
for \(n \geq 3\). }
\end{align*}
