\newlec

\textbf{Principle of Mathematical Induction (POMI)}
\vskip1em
\noindent \textbf{Axiom: } If sequence of statements $P(1)$, $P(2)$, ... satisfy
\begin{enumerate}
\item $P(1)$ is true
\item For any $k \in \mathbb{N}$, if $P(k)$ is true then $P(k+1)$ is true
\end{enumerate}
then $P(n)$ is true for all $n \in \mathbb{N}$. 
\ic{Here describe the domino analogy. Explain that you're creating a chain of implications $P(1) \Rightarrow P(2)$, $P(2) \Rightarrow P(3)$, and so on and you want the chain to begin.}
In practice, these arguments proceed as follows:
\begin{enumerate}
\item Prove the base case, that is, verify that $P(1)$ is true
\item Inductive hypothesis: Let $k \in \mathbb{N}$ be an arbitrary number. Assume that $P(k)$ is true.
\item Inductive conclusion. Deduce that $P(k+1)$ is true.
\item Then conclude by the Principle of Mathematical Induction (POMI) that $P(n)$ holds
\end{enumerate}
\ic{Emphasize the for some part in the IH step. Note also that the induction proof needn't start at $1$ (it could start at $0$ or $-1$ etc.)}
\ex Prove that
$$
\sum_{i=1}^{n} i^{2} = \frac{n(n+1)(2n+1)}{6}
$$
for all $n \in \mathbb{N}$.
\vskip1em
\pf  Let $P(n)$ be the statement that
$$
\sum_{i=1}^{n} i^{2} = \frac{n(n+1)(2n+1)}{6}
$$
holds. We prove $P(n)$ is true for all natural numbers $n$ by the Principle of Mathematical Induction. 
\begin{enumerate}
\item Base case: When $n=1$, $P(1)$ is the statement that
$$
\sum_{i=1}^{1} i^{2} = \frac{(1)((1)+1)(2(1)+1)}{6}.
$$
This holds since
$$
\frac{(1)((1)+1)(2(1)+1)}{6} = \frac{1(2)(3)}{6} = 1 = \sum_{i=1}^{1} i^{2}.
$$
\item Inductive Hypothesis. Assume that $P(k)$ is true {\color{red} for some} $k \in \mathbb{N}$. This means that
$$
\sum_{i=1}^{k} i^{2} = \frac{k(k+1)(2k+1)}{6}.
$$
\item Inductive Step. We now need to show that 
$$
\sum_{i=1}^{k+1} i^{2} = \frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}.
$$
To do this, we will start with the left hand side, reduce to the assumption made in the inductive hypothesis and then conclude the right hand side.
\begin{align*}
\text{LHS} &= \sum_{i=1}^{k+1} i^{2} \\
&= \sum_{i=1}^{{\color{red} k}} i^{2}  + {\color{red} (k+1)^{2}} \\
&= \frac{k(k+1)(2k+1)}{6} + (k+1)^{2} && \text{Inductive Hypothesis}\\
&= (k+1)\left( \frac{k(2k+1)}{6} + k+1\right)\\
&= (k+1)\left( \frac{2k^{2} + k}{6} + \frac{6k+6}{6}\right)\\
&= (k+1)\left( \frac{2k^{2} + 7k+ 6}{6}\right)\\
&= \frac{(k+1)(k+2)(2k+3)}{6}\\
&= \text{RHS}
\end{align*}
\end{enumerate}
Hence, 
$$
\sum_{i=1}^{n} i^{2} = \frac{n(n+1)(2n+1)}{6}
$$
is true for all natural numbers $n$ by the Principle of Mathematical Induction. \qed
\ic{It is important to note where you used the inductive hypothesis!}

\note Now, we can finally solve the Tower of Hanoi example for the 100 level tower:
\begin{align*}
V_{tower} &= \sum_{i=1}^{100} V_{i}\\
&= \sum_{i=1}^{100} \pi i^{2}(1)\\
&= \pi \sum_{i=1}^{100} i^{2}\\
&= \pi \frac{(100)(101)(2(100)+1)}{6} \\
&= 338350\pi
\end{align*}

\ic{This could easily be 25-30 minutes of your lecture. The rest of the time is spent doing examples:}

\hdc
Prove that
$$
\sum_{i=1}^{n}i = \frac{n(n+1)}{2}
$$
holds for all natural numbers $n$.
\vskip3em
\soln 
\begin{enumerate}
\item Base case: 
$$
\frac{(1)(1+1)}{2} = 1 = \sum_{i=1}^{n}i.
$$
\item Inductive Hypothesis. Assume that
$$
\sum_{i=1}^{k}i = \frac{k(k+1)}{2}
$$
holds for some $k \in \mathbb{N}$
\item Inductive step. For $k+1$, 
\begin{align*}
\sum_{i=1}^{k+1}i &= \sum_{i=1}^{k}i + (k+1) \\
&= \frac{k(k+1)}{2} + (k+1) && \text{ Inductive Hypothesis}\\
&= (k+1)(\tfrac{k}{2}+1)\\
&=\frac{(k+1)(k+2)}{2}
\end{align*}
Therefore, the claim holds by the Principle of Mathematical Induction for all $n \in \mathbb{N}$. \qed
\end{enumerate}
\ic{This is the 40 minute mark}

\newpage
\ic{An example where we don't start at 1}
\ex Prove that $n! > 2^{n}$ for all $n \in \mathbb{N}$ with $n \geq 4$.
\vskip1em
\pf We proceed by mathematical induction.
\begin{enumerate}
\item Base case: When $n=4$, notice that $4! = 24 > 16 = 2^{4}$ so the inequality holds in this case.
\item Inductive Hypothesis: Assume that $k! > 2^{k}$ for some $k \in \mathbb{N}$ with $k \geq 4$. 
\item Inductive Step: Notice that
\begin{align*}
(k+1)! &= (k+1)k!\\
&> (k+1)2^{k} & \text{ Inductive Hypothesis}\\
&> (1 + 1)2^{k} & \text{ Since $k \geq 4 > 1$}\\
&= 2^{k+1}
\end{align*}
Thus, the conclusion holds for all $k \in \mathbb{N}$ with $k \geq 4$ by the Principle of Mathematical Induction. \qed
\end{enumerate}

\newpage

\hdc

Examine the following induction ``proofs''. Find the mistake
\vskip1em
\textbf{Question:} For all $n \in \mathbb{N}$, $n > n + 1$.
\vskip1em
\textbf{Proof:} Let $P(n)$ be the statement: $n > n + 1$. Assume that $P(k)$ is true for some integer $k \geq 1$. That is, $k > k + 1$ for some integer $k \geq 1$. We must show that $P(k+1)$ is true, that is, $k+1>k+2$. But this follows immediately by adding one to both sides of $k > k+1$. Since the result is true for $n = k+1$, it holds for all $n$ by the Principle of Mathematical Induction.
\vskip2em
\ic{No base cases!}
\textbf{Question:} All horses have the same colour. (Cohen 1961).
\vskip1em
\textbf{Proof:} 
\vskip1em
\textbf{Base Case:} If there is only one horse, there is only one colour.
\vskip0.1em
\textbf{Inductive hypothesis and step:} Assume the induction hypothesis that within any set of $n$ horses for any $n \in \mathbb{N}$, there is only one colour. Now look at any set of $n + 1$ horses. Number them: $1, 2, 3, ..., n, n + 1$. Consider the sets $\{1, 2, 3, ..., n\}$ and $\{2, 3, 4, ..., n + 1\}$. Each is a set of only $n$ horses, therefore by the induction hypothesis, there is only one colour. But the two sets overlap, so there must be only one colour among all $n + 1$ horses.
\vskip3em
\ic{ However, the logic of the inductive step is incorrect for n = 1, because the statement that "the two sets overlap" is false (there are only n + 1 = 2 horses prior to either removal, and after removal the sets of one horse each do not overlap. This is the 50 minute mark}



