Exercise 8.4

Question

\def\l{\lambda}
The \emph{Fibonacci numbers} of number theory are defined recursively by the formula
\begin{align*}
\l_1 &= \l_2 = 1 \,, \
\l_n &= \l_{n-1} + \l_{n-2} \hspace{1cm} 	ext{for $n>2$.}
\end{align*}
Define them rigorously by use of Theorem~8.4.

Dan Whitman · Accepted Answer

ewcommand\seqinf[1]{\left(#1_1, #1_2, \ldotsight)}
\defest{estriction}
\def{ho}
\def\l{\lambda}

First, note that the Fibonacci numbers are all positive integers.
So, for any function $f: \left\{1, \ldots, might\} 	o {{\mathbb{Z}}_+}$ define
\begin{gather*}
(f) = \begin{cases}
1 & m = 1 \
f(m) + f(m-1) & m > 1 \,,
\end{cases}
\end{gather*}
noting that clearly the range of $$ is still ${{\mathbb{Z}}_+}$ since that is the range of $f$.
Then, by Theorem~8.4, there is a unique function $F : {{\mathbb{Z}}_+} 	o {{\mathbb{Z}}_+}$ such that
\begin{align*}
F(1) &= 1 \,, \
F(n) &= (F est \left\{1, \ldots, n-1ight\}) \hspace{1cm} 	ext{for $n>1$.}
\end{align*}
We claim that the Fibonacci numbers are $\l_n = F(n)$ for $n \in {{\mathbb{Z}}_+}$.
\begin{proof}
To show that the numbers $\l_n$ satisfy the inductive definition of the Fibonacci numbers, first note that we clearly have $\l_1 = F(1) = 1$.
We also have that
\begin{gather*}
\l_2 = F(2) = (F est \left\{1ight\}) = 1 \,.
\end{gather*}
Lastly, for any $n > 2$, clearly $ n > 1$ also and $n - 1 > 1$ so that
\begin{gather*}
\l_n = F(n) = (F est \left\{1, \ldots, n-1ight\}) = F(n-1) + F([n-1]-1) = \l_{n-1} + \l_{n-2} \,,
\end{gather*}
which shows that the inductive definition is satisfied.
\end{proof}

Exercise 8.4

Answers

Comments

Exercise 8.4

Answers

Comments

Add answer