\documentclass{beamer}
\title{CS173 Lecture B, September 3, 2015}
\author{Tandy Warnow}
\begin{document}
\frame{\titlepage}
CS 173, Lecture B\\
September 3, 2015\\
Tandy Warnow\\
\begin{frame}
\frametitle{Induction Proofs}
The {\em idea} behind induction is simple.
If I have a very contagious cold, and I sneeze then the person to my right
will catch the cold; then she will sneeze, and the person
to her right will catch it; and then he will sneeze, etc.
Eventually everyone (to my right) will catch the cold.
\end{frame}
\begin{frame}
\frametitle{An easy induction proof}
\noindent
{\bf Theorem}: For all $n \in N$,
$\sum_{i=1}^n i = n(n+1)/2$
\vspace{.1in}
\noindent
{\bf Proof.}
We prove this theorem by induction.
Our {\bf inductive hypothesis} is that for some
natural number $K$, and for all natural numbers $k$ with
$1 \leq k \leq K$, $\sum_{i=1}^k i = k(k+1)/2$.
We now wish to show that this statement is also true for $K+1$.
Consider
$\sum_{i=1}^{K+1} i$.
By definition this is
$$\sum_{i=1}^{K+1} i = \sum_{i=1}^K i + (K+1)$$
By the inductive hypothesis,
$$\sum_{i=1}^{K} i = K(K+1)/2$$
\end{frame}
\begin{frame}
\frametitle{Induction proof, continued}
So far we have:
$$\sum_{i=1}^{K+1} i = \sum_{i=1}^K i + (K+1)$$
and
$$\sum_{i=1}^{K} i = K(K+1)/2$$
Hence,
$$\sum_{i=1}^{K+1} i = \sum_{i=1}^K i + (K+1) $$
$$= K(K+1)/2 + (K+1) $$
$$=(K+1)(K/2 +1)$$
$$=(K+1)(K+2)/2$$
Since $K$ was arbitrary, our theorem is proved.
Q.E.D.
\end{frame}
\begin{frame}
\frametitle{Necessary parts of induction proofs}
\begin{itemize}
\item
Inductive Hypothesis
\item
Base case
\item
Use the inductive hypothesis (that a statement is
true for some value $K$) to prove it true for the next
value ($K+1$).
\item
Point out that $K$ was arbitrary so the result holds for
all $K$.
\item
Optional: say ``Q.E.D."
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{The Inductive Hypothesis}
The inductive hypothesis must be a statement
that that depends on a parameter $K$
and that is either true or false.
Your inductive hypothesis must be that the statement is
true for all values $k$ between some base case $n_0$ and
some specific (but arbitrary) value $K$.
Example of bad inductive hypotheses:
\begin{itemize}
\item The inductive hypothesis is that $f(n)$ is even
\item The inductive hypothesis is that $g(n) >n$ for all $n$
\item The inductive hypothesis is $n^2+3$
\item The inductive hypothesis is that $f(3)=17$
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{The base case}
The base case is the first value(s) for which you
want to prove the statement true.
Often $n_0=1$, but not always. Be careful to check.
Sometimes you need to establish several base cases.
Typically the base case is done properly. But sometimes
it's missing - and that's a bit mistake.
\end{frame}
\begin{frame}
\frametitle{Recurrence relations}
Recurrence relations are generally
functions defined recursively, as in
\begin{enumerate}
\item
$g(1)=3$ and $g(n)=3+g(n-1)$ for $n \geq 2$
\item
$h(3)=5$ and $h(n) = 2 h(n-1)$ for $n \geq 4$
\item
$f(1)=f(2)=1$ and
$f(n) = f(n-1) + f(n-2)$ for $n \geq 3$.
\item
$k(3)=7$ and $k(n) = 2k(n-1)-1$ for $n \geq 4$
\end{enumerate}
Sometimes it is easy to find closed form
solutions for recursively defined functions,
but not always.
For example, can you find a closed form
solution for all the functions above?
Or perhaps just a lower (or upper) bound?
Induction gives you a way of proving closed
form solutions, or upper and lower bounds, on
recursively defined functions (i.e., recurrence relations).
\end{frame}
\begin{frame}
\frametitle{Another induction proof}
Let $f(n)$ be a function that maps the set of
integers greater than $3$ to the set of
integers, defined by:
\begin{itemize}
\item[]$f(4) = f(5) = 1$
\item[]$f(n) = 2f(n-1)+f(n-2)$ if $n>5$
\end{itemize}
Prove that $f(n) \geq 2^{n-5}$ for $n > 5$.
\vspace{.1in}
{\bf Proof:} by induction on $n$.
{\bf We will need two base cases: $n=6$ and $n=7$.}
By definition, $f(6) = 2f(5)+f(4) = 3$.
Note that $2^{6-5}=2^1=2$, and so $f(n)> 2^{n-5}$
for $n=6$.
For $n=7$, note that $f(7) = 2 \times f(6) + f(5) = 6+1 = 7$.
Note also that $2^{7-5}=2^2 = 4$, so that
%Note also that $f(5) = 1$ and that $n-5=0$ when $n=5$.
$f(n) \geq 2^{n-5}$ when $n=7$.
Hence, both base cases hold.
\end{frame}
\begin{frame}
\frametitle{Induction proof, continued}
The {\bf inductive hypothesis} is that for some arbitrary
$K \geq 7$, $f(n) \geq 2^{n-5}$ for all $n = 5, 6, \ldots, K$.
We wish to show that this statement holds for $K+1$.
By definition, $$f(K+1) = 2f(K) + f(K-1)$$
Therefore, by the inductive hypothesis,
$$ f(K+1) \geq 2\times 2^{K-5} + 2^{K-6} $$
$$ \geq 2^{K-4} = 2^{(K+1)-5}$$
Since $K$ was arbitrary, the result holds for all $K$.
Q.E.D.
\end{frame}
\begin{frame}
\frametitle{Another induction proof}
Let $f:NxN \rightarrow N$ be defined by
\begin{itemize}
\item
$f(n,m) = n+m$ if $n=1$ or $m=1$,
\item
$f(n,m) = f(n-1,m) + f(n,m-1)$, otherwise
\end{itemize}
\vspace{.1in}
We would like to prove that $f(n,m) \geq n+m$ for all $n \geq 1$ and
$m \geq 1$.
\vspace{.1in}
Base case: $n=1$ or $m=1$ follows immediately.
So we prove the rest by induction.
What is our inductive hypothesis?
\end{frame}
\begin{frame}
\frametitle{Another induction proof, continued}
Recall that
\begin{itemize}
\item
$f(n,m) = n+m$ if $n=1$ or $m=1$,
\item
$f(n,m) = f(n-1,m) + f(n,m-1)$, otherwise
\end{itemize}
Our inductive hyopthesis will be:
\begin{itemize}
\item[]
$f(n,m) \geq n+m$ for all natural numbers $n,m$ with
$n+m \leq K$
\end{itemize}
The base case is $K=2$; hence $n=m=1$ and the statement holds.
Now assume that for some arbitrary $K$, the statement holds.
We wish to show it holds also for $K+1$.
\end{frame}
\begin{frame}
\frametitle{Another induction proof, continued}
Let $n,m$ be given so that $n+m = K+1$.
If $n=1$ or $m=1$, then $f(n,m) = m+m$, and the
statement holds.
So assume $n \geq 2$ and $m \geq 2$, so that
$f(n,m) = f(n-1,m)+f(n,m-1)$.
Then, by the inductive hypothesis,
$$f(n-1,m) \geq n+m-1$$
and $$f(n,m-1) \geq n+m-1$$
Hence $$f(n,m) \geq 2(n+m-1) = 2n+2m-2 >n+m-1$$
Since $K$ was arbitrary, the statement holds for all $K$.
Q.E.D.
\end{frame}
\begin{frame}
\frametitle{What we learned}
We learned:
\begin{itemize}
\item The base case is sometimes more than one value.
\item The inductive hypothesis is sometimes not on an
obvious parameter, but on something built using
obvious parameters (like the sum)
\item Induction can be used to prove upper or lower
bounds on recursively defined functions.
\item Induction proofs are not difficult!
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{Two-person games}
Remember the original two person game?
Who wins?
Prove your assertion true by induction on the
total number of rocks in the game.
\end{frame}
\end{document}