\newlec

\ic{If you did the surveys, you could go over them at the beginning}

\hdc

\textbf{Fibonacci Sequence}
\defn Define a sequence by $f_{1} = 1$, $f_{2} = 1$ and 
\[
f_{n} = f_{n-1} + f_{n-2} \quad\quad \text{For all $n \geq 3$}
\]
so $f_{3} = 2$, $f_{4} = 3$, $f_{5} = 5$, and so on. 

\vskip1em
\begin{enumerate}
\item Prove that $\displaystyle \sum_{r=1}^{n} f_{r}^{2} = f_{n}f_{n+1}$ for all $n \in \mathbb{N}$.
\item Prove that $f_{n} < \left(\frac{7}{4}\right)^{n}$ for all $n \in \mathbb{N}$.
\end{enumerate}

\vskip3em
\soln We prove only the first one. The second can be found on the Math 135 resources page
\begin{center}
\url{http://www.cemc.uwaterloo.ca/~cbruni/Math135Resources.php}
\end{center}
\begin{enumerate}
\item Base case: $n=1$
\begin{align*}
\text{LHS} &=  \sum_{r=1}^{n} f_{r}^{2} \\
&=  \sum_{r=1}^{1} f_{r}^{2} \\
&=  f_{1}^{2}\\
&= 1^{2}\\
&= 1
\end{align*}
and
\begin{align*}
\text{RHS} &= f_{n}f_{n+1} = f_{1} f_{2} = (1)(1) = 1 = \text{LHS}
\end{align*}
\item Inductive Hypothesis. Assume that
$$
\sum_{r=1}^{k} f_{r}^{2} = f_{k}f_{k+1}
$$
holds for some $k \in \mathbb{N}$.
\item Inductive Step. We want to show that
$$
\sum_{r=1}^{k+1} f_{r}^{2} = f_{k+1}f_{k+2}.
$$
We begin with the left and proceed towards the right
\begin{align*}
\text{LHS} &=\sum_{r=1}^{k+1}f_{r}^{2} \\
&= \sum_{r=1}^{k}f_{r}^{2}  + f_{k+1}^{2}\\
&= f_{k}f_{k+1} + f_{k+1}^{2} && \text{Induction Hypothesis}\\
&= f_{k+1}(f_{k} + f_{k+1})\\
&= f_{k+1}f_{k+2} && \text{By definition of Fibonacci Sequence}\\
&= \text{RHS}
\end{align*}
Hence  $\displaystyle \sum_{r=1}^{n} f_{r}^{2} = f_{n}f_{n+1}$ for all $n \in \mathbb{N}$ by the Principle of Mathematical Induction. \qed
\end{enumerate}

\ic{This easily is the 20-30 minute mark. Students might struggle with the notation.}

\newpage

\defn Closed form: ``Easy to put into a calculator'' (This is not a formal definition!)
\vskip1em
\ex Find a closed form expression for 
\[
P_{n} = \prod_{r=2}^{n}\left(1 - \frac{1}{r^{2}}\right)
\]
where $n \geq 2$ and prove it is correct by induction.
\vskip1em
\pf We begin with some guessing and napkin (discovery) work.
\begin{align*}
P_{2} &= \prod_{r=2}^{2}\left(1 - \frac{1}{r^{2}}\right) = \left(1 - \frac{1}{2^{2}}\right) = 1 - \tfrac{1}{4} = \tfrac{3}{4}\\
P_{3} &= \prod_{r=2}^{3}\left(1 - \frac{1}{r^{2}}\right) = \left(1 - \frac{1}{2^{2}}\right)\left(1 - \frac{1}{3^{2}}\right)  = (1 - \tfrac{1}{4} )(1-\tfrac{1}{9})= \tfrac{3}{4}\cdot \tfrac{8}{9} = \tfrac{2}{3} = \tfrac{4}{6}\\
P_{4} &= \prod_{r=2}^{4}\left(1 - \frac{1}{r^{2}}\right) = \left(1 - \frac{1}{2^{2}}\right)\left(1 - \frac{1}{3^{2}}\right) \left(1 - \frac{1}{4^{2}}\right)  = (1 - \tfrac{1}{4} )(1-\tfrac{1}{9})(1 - \tfrac{1}{16})= \tfrac{3}{4}\cdot \tfrac{8}{9}\cdot\tfrac{15}{16} = \tfrac{5}{8}
\end{align*}
Claim: $P_{5} = \tfrac{6}{10}$ and in general $P_{n} = \tfrac{n+1}{2n}$ for all $n\geq 2$. We prove this by induction.
\begin{enumerate}
\item Base case: $n=2$
\begin{align*}
P_{2} &= \prod_{r=2}^{2}\left(1 - \frac{1}{r^{2}}\right) = \left(1 - \frac{1}{2^{2}}\right) = 1 - \tfrac{1}{4} = \tfrac{3}{4} = \tfrac{n+1}{2n}
\end{align*}
\item Inductive Hypothesis. Assume that $P(k)$ is true for some $k \geq 2$ and $k \in \mathbb{N}$, that is, assume
\begin{align*}
\prod_{r=2}^{k}\left(1 - \frac{1}{r^{2}}\right) = \frac{k+1}{2k}
\end{align*}
\item Inductive Step. We want to show that 
\begin{align*}
\prod_{r=2}^{k+1}\left(1 - \frac{1}{r^{2}}\right) = \frac{(k+1)+1}{2(k+1)} = \frac{k+2}{2k+2}
\end{align*}
We proceed starting from the left.
\begin{align*}
\text{LHS} &= \prod_{r=2}^{k+1}\left(1 - \frac{1}{r^{2}}\right) \\
&= \prod_{r=2}^{k}\left(1 - \frac{1}{r^{2}}\right) \cdot \left(1 - \frac{1}{(k+1)^{2}}\right) \\
&= \frac{k+1}{2k} \cdot\frac{(k+1)^{2} - 1}{(k+1)^{2}}&&\text{Inductive Hypothesis}\\
&= \frac{k+1}{2k} \cdot\frac{k^{2} + 2k}{(k+1)^{2}}\\
&= \frac{k+1}{2k} \cdot\frac{k(k + 2)}{(k+1)^{2}}\\
&= \frac{k+2}{2(k+1)}\\
&= \text{RHS}
\end{align*}
Therefore, by the Principle of Mathematical Induction, we have that 
$$P_{n} = \tfrac{n+1}{2n}$$
 for all $n\geq 2$. \qed
\end{enumerate}

\ic{This is the 50 minute mark.}

