\newlec

\hdc

\ic{In this lecture, you might want to consider giving a midterm survey of your teaching.}

Prove $P(n): 6 \mid (2n^{3} + 3n^{2} + n)$ holds $\forall n \in \mathbb{N}$.
\vskip3em
\soln 
\begin{enumerate}
\item Base case
\begin{align*}
2n^{3} + 3n^{2} + n = 2 + 3 + 1 = 6
\end{align*}
and $6 \mid 6$. Hence $P(1)$ is true.
\item Inductive Hypothesis. Assume $P(k)$ is true for some $k \in \mathbb{N}$, that is, $\exists \ell \in \mathbb{Z}$ such that $6\ell = 2k^{3} + 3k^{2} + k$.
\item Inductive Step: Prove that $P(k+1)$ is true.
\begin{align*}
2(k+1)^{3} + 3(k+1)^{2} + (k+1) &= 2k^{3} + 6k^{2} + 6k + 2 + 3k^{2} + 6k + 3 + k + 1\\
&= (2k^{3} + 3k^{2} + k) + 6k^{2} + 12k + 6\\
&= 6\ell + 6(k^{2} + 2k + 1) &&\text{IH}\\
&= 6(\ell + (k+1)^{2})
\end{align*}
Hence, $6 \mid 2(k+1)^{3} + 3(k+1)^{2} + (k+1)$. Thus $P(k+1)$ is true. Hence by the Principle of Mathematical Induction, we have that $P(n)$ is true for all $n \in \mathbb{N}$. \qed
\end{enumerate}

\ic{This is the 10 minute mark}

\newpage
\hdc
\ic{This illustrates the need for something ``stronger'' than induction.}

Let $\{x_{n}\}$ be a sequence defined by $x_{1} = 4$, $x_{2} = 68$ and $$x_{m} = 2x_{m-1}+15x_{m-2} \quad\quad \text{ for all } m \geq 3$$ 
Prove that $x_{n} = 2(-3)^{n} + 10\cdot 5^{n-1}$ for $n \geq 1$.

\vskip1em
\soln We proceed by induction. 
\vskip1em
\textbf{Base Case:} For $n=1$, we have $$x_{1} = 4 = 2(-3)^{1} + 10\cdot 5^{0} =  2(-3)^{n} + 10\cdot 5^{n-1}.$$
 \vskip1em
 \textbf{Inductive Hypothesis:} Assume that $$x_{k} = 2(-3)^{k} + 10\cdot 5^{k-1}$$ is true for some $k \in \mathbb{N}$.
 \vskip1em
 \textbf{Inductive Step:} Now, for $k+1$, 
 \begin{align*}
 x_{k+1} &= 2x_{k}+15x_{k-1} &&\text{ Only true if $k \geq 2$!!!}\\
 &= 2( 2(-3)^{k} + 10\cdot 5^{k-1}) + 15x_{k-1}\\
 &= 4(-3)^{k} + 20\cdot 5^{k-1} + 15x_{k-1}\\
 &= ...?
 \end{align*}
 \vskip3em

\ic{This is the 15 minute mark}
\newpage


\textbf{Principle of Strong Induction (POSI)}
\vskip1em
\noindent \textbf{Axiom: } If sequence of statements $P(1)$, $P(2)$, ... satisfy
\begin{enumerate}
\item $P(1)\wedge P(2) \wedge... \wedge P(b)$ are true for some $b \in \mathbb{N}$
\item $P(1) \wedge P(2) \wedge ... \wedge P(k)$ are true implies that $P(k+1)$ is true for all $k \in \mathbb{N}$
\end{enumerate}
then $P(n)$ is true for all $n \in \mathbb{N}$.
\vskip1em
\note This is equivalent in strength to the Principle of Mathematical Induction and to the Well Ordering Principle!
\vskip1em 

\qn Let $\{x_{n}\}$ be a sequence defined by $x_{1} = 4$, $x_{2} = 68$ and $$x_{m} = 2x_{m-1}+15x_{m-2} \quad\quad \text{ for all } m \geq 3$$ 
Prove that $x_{n} = 2(-3)^{n} + 10\cdot 5^{n-1}$ for $n \geq 1$.

\vskip1em
\textbf{Solution:} We proceed by strong induction. 
\vskip1em
\textbf{Base Case:} For $n=1$, we have $$x_{1} = 4 = 2(-3)^{1} + 10\cdot 5^{0} =  2(-3)^{n} + 10\cdot 5^{n-1}.$$
For $n=2$, we have $x_{2} = 68$ and $$2(-3)^{2} + 10\cdot 5^{2-1} =  18 + 50 = 68.$$
\vskip1em
\textbf{Inductive Hypothesis:} Assume that $$x_{i} = 2(-3)^{i} + 10\cdot 5^{i-1}$$ is true for all $i \in \{1,2,...,k\}$ for some $k \in \mathbb{N}$ and $k \geq 2$.
\vskip1em
\textbf{Inductive Step:} Now, for $k+1$, 
\begin{align*}
x_{k+1} &= 2x_{k}+15x_{k-1} &&\text{ Valid since $k \geq 2$}\\
&= 2( 2(-3)^{k} + 10\cdot 5^{k-1}) + 15 (2(-3)^{k-1} + 10\cdot 5^{k-2}) \\
&= 4(-3)^{k} + 20\cdot 5^{k-1} + 30(-3)^{k-1} + 150\cdot 5^{k-2} \\
&= -12(-3)^{k-1} + 100\cdot 5^{k-2} + 30(-3)^{k-1} + 150\cdot 5^{k-2} \\
&= 18(-3)^{k-1} + 250\cdot 5^{k-2} \\
&= 2\cdot(-3)^{2}(-3)^{k-1} + 10\cdot5^{2}\cdot 5^{k-2} \\
&= 2(-3)^{k+1} + 10\cdot 5^{k}
\end{align*}
Hence, $x_{k+1} = 2(-3)^{k+1} + 10\cdot 5^{k}$. Thus, by the Principle of Strong Induction, we have that $x_{n} = 2(-3)^{n} + 10\cdot 5^{n-1}$ for all $n \geq 1$. \qed
 
\ic{This is the 40 minute mark}

\newpage
\hdc

\ic{I would make them do half of this example - say the base cases and the inductive hypothesis}

Suppose $x_{1} = 3$, $x_{2} = 5$ and for all $m\geq 3$,  $$x_{m} = 3x_{m-1} + 2x_{m-2}.$$
Prove that $x_{n} < 4^{n}$ for all $n \in \mathbb{N}$.
\vskip3em
\pf Let $P(n)$ be the given statement. We prove $P(n)$ by strong induction.
\begin{enumerate}
\item Base cases: $P(1)$ is true since $x_{1} = 3 < 4$ and $P(2)$ is true since $x_{2} = 5 < 16 = 4^{2}$.
\item Inductive Hypothesis: Assume that $P(i)$ is true for all $i \in \{1,2,...,k\}$ for some $k \in \mathbb{N}$ with $k \geq 2$.
\item Inductive Step. For $k\geq2$, we have
\begin{align*}
x_{k+1} &= 3x_{k} + 2x_{k-1} &&\text{ Valid since $k+1 \geq 3$}\\
&< 3\cdot4^{k} + 2\cdot 4^{k-1} \\
&< 4^{k-1}(3\cdot 4 + 2)\\
&= 4^{k-1}(14)\\
&< 4^{k-1}(16)\\
&= 4^{k+1}
\end{align*}
Hence $P(k+1)$ is true and thus $P(n)$ is true for all $n \in \mathbb{N}$ by the Principle of Strong Induction.
\end{enumerate}

\newpage

\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
\note For a cool link between this sequence and music, check out Tool - Lateralus on Youtube!

\ic{This is the 50 minute mark}
