\documentclass{article}
\input{preamble.tex}
\title{Day 7}
\date{Wednesay May 30, 2012}
\newcommand{\df}{\textbf}
\def\Display{\@empty}
\newcommand{\Hide}[2]{\ifx \Display\undefined \strut \\ \vspace{#1} \\ \strut \else {\color{blue} #2} \fi }
\newcounter{clm}[thm]
\renewcommand{\theclm}{\arabic{clm}}
\def\claim{\par\medskip\noindent\refstepcounter{clm}\hbox{\bf Claim \arabic{clm}.}
\it\ %\ignorespaces
}
\def\endclaim{
\par}
\newenvironment{clm}{\begin{changemargin}{1.75cm}{1.5cm}\claim}{\endclaim\end{changemargin}}
\newenvironment{clmpf}{ \renewcommand{\qedsymbol}{\subqed} \begin{changemargin}{2cm}{1.5cm}\begin{proof}}{\end{proof}\end{changemargin}}
\def\changemargin#1#2{\list{}{\rightmargin#2\leftmargin#1}\item[]}
\let\endchangemargin=\endlist
\begin{document}
\maketitle
\section{Induction}
Recall the principle of induction says that if we prove $\phi(0)$ and prove $\A n\in\N \st \phi(n)\to\phi(n+1)$ then we can conclude $\A n\in\N\st \phi(n)$. Proving $\phi(0)$ is called the \df{base case}, proving $\A n\in\N \st \phi(n) \to \phi(n+1)$ is called the \df{inductive step}; the assumption you will get from proving this (namely $\phi(n)$) is called the \df{induction hypothesis}.
Let's take a minute to fully appreciate what is going on. Why would someone care if $\A n\in \N \st \phi(n)$? Well, as we know, the way that you use a universal quantifier is to instantiate the quantifier at values; for instance, you might prove $\A n \st \phi(n)$ to know that $\phi(75)$ is true.
The principle of induction essentially gives you a procedure to get the proof of $\phi(n)$ for any $n$, and hence proves it for any $n$. For instance, if you proved $\A n\in\N\st \phi(n)$ so you'd be able to conclude $\phi(75)$, you actually didn't need to do induction; from your proof, you could get the following proof of $\phi(75)$:
\begin{align*}
\phi(0) \\
\phi(0)\to\phi(1) && \mbox{therefore } \phi(1) \\
\phi(1)\to\phi(2) && \mbox{therefore } \phi(2) \\
\phi(2)\to\phi(3) && \mbox{therefore } \phi(3) \\
\vdots && \vdots \\
\phi(74)\to\phi(75) && \mbox{therefore } \phi(75)
\end{align*}
But, the induction principle tells us because we can ``read off'' this kind of proof from our induction proof for any value of $n$, not just $75$, we have it for every $n\in\N$. It is important to note though that this is was is actually going on in an inductive proof. After you do an inductive proof you should mentally check that it is possible to conclude any value $n\in\N$ by doing the above kind of procedure.
\subsection{Some Examples}
\begin{thm}
$n(n+1)$ is even for every $n$ in the naturals.
\end{thm}
\begin{proof}
\Hide{3cm}{
We proceed by induction on $n$.
For the base case, $n=0$, and $0$ is even, so we are done.
Assume that we have $n(n+1)$ is even for some arbitrary $n\in \N$. We seek to show that $(n+1)(n+2)$ is even. Well, $(n+1)(n+2) = n(n+1) + 2(n+1)$. By our induction hypothesis, the left term of the sum is even, and as the second is multiplied by $2$ it is even. Therefore, the sum is even.
So, by induction, the statement is true for all $n\in\N$.
}
\end{proof}
\begin{thm}
\[
\sum_{i=1}^{n} i^2 = \frac{ n(n+1)(2n+1) }{6}
\]
\end{thm}
\begin{proof}
\Hide{1.5in}{
We do induction on $n$.
If $n = 0$ then, obviously the sunm if $0$, which satisfies the formula.
Otherwise, let $n$ be arbitrary and assume that $\sum_{i=1}^n i^2 = \frac{ n(n+1)(2n+1) }{6}$. This is our induction hypothesis. We want to show that it true for $n+1$. Well
\begin{align*}
\sum_{i=1}^{n+1} i^2 &= (n+1)^2 + \sum_{i=1}^n i^2 \\
&= (n+1)^2 + \frac{ n(n+1)(2n+1) }{6} \\
&= \frac{ 6(n+1)^2 + n(n+1)(2n+1) }{6} \\
&= \frac{ (n+1)( 6(n+1) + n(2n+1) )}{6} \\
&= \frac{ (n+1)( 2n^2 + 7n + 6 ) }{6} \\
&= \frac{ (n+1)(n+2)(2n+3)}{6} \\
&= \frac{ (n+1)( (n+1) + 1)(2(n+1)+1)}{6}
\end{align*}
So by induction, it is true for every $n\in\N$.
}
\end{proof}
\begin{eg}
Consider a $2^n \times 2^n$ chessboard for $n$ natural, $n>0$. Remove a corner. Prove that you can then cover the board with L shaped triominoes.
\begin{proof}
\Hide{1.5in}{
Go by induction on $n$. In the case when $n=1$, a $2\times 2$ chessboard with a corner removed is a L shapes triomino.
Assume it is true for $n$, and now consider a $2^{n+1} \times 2^{n+1}$ board. Remove a corner. Divide the board into 4 quadrants, each of which is a $2^n \times 2^n$ board. One of those has a corner removed. By IH, we can cover that quadrant. Then, put a triomino in the center of the board so that exactly one corner is removed from each of the smaller boards. Now, us the IH on each of these, and you are done.
}
\end{proof}
What about if you remove any corner?
\end{eg}
\begin{eg}
Play a game with $2$ people. You start with $0$, and then alternate adding either $1$, $2$, or $3$ to a running total. The first person to add to $1000$ wins. Prove Player 2 has a winning strategy.
\end{eg}
\begin{proof}
\Hide{1.5in}{
We prove that if $n>0$ is divisible by $4$ player $2$ has a winning strategy. So, we do induction on $m$ to prove player 2 wins if you are trying to get $n=4m$.
Suppose that $n=4$. Then no matter what Player 1 does, Player 2 can get to 4.
Suppose that Player 2 can successfully get to $4m$ first, for some $m$. Then we want to show he can get to $4(m+1) = 4m+4$. Well, he first plays the strategy which allows him to get to $4m$, which he can do by induction hypothesis. Then, Player 1 moves; as in the base case, player 2 always has a corresponding move to get him to $4m+4$.
}
\end{proof}
\begin{eg}
For every positive integer $n$
\[
5^n + 5 < 5^{n+1}
\]
\begin{proof}
\Hide{1in}{
By induction on $n$. For our base case, we have $n=1$. $5^1 + 5 = 10 < 25 = 5^2$
Assume it is true for $n$; so $5^n + 5 < 5^{n+1}$. Want to show that it is true for $n+1$. So we have
\begin{align*}
5^n + 5 < 5^{n+1} &\implies 5^{n+1} + 5^2 < 5^{n+2}
\end{align*}
So, as $5 < 5^2$ we have
\[
5^{n+1} + 5 < 5^{n+1} + 5^2
\]
Putting it all together
\[
5^{n+1} + 5 < 5^{n+1} + 5^2 < 5^{n+2}
\]
So, but induction, it is true for all $n$
}
\end{proof}
\end{eg}
\subsection{A Dual Notion: Recursion}
Induction is a way to prove things about all natural numbers. The dual notion to this is the notion of \df{recursion}. Recursion is a way to define something for all natural numbers. It has a similar metaphor as the dominoes: we define something for the first natural number, and then assume that we have it for the $n$th natural, and define it for the $n+1$th natural number.
You have seen this before.
\begin{eg}
A \df{sequence} of natural numbers is an infinite ordered set of natural numbers. We will talk about sequence in great detail soon in the course, but you have already seen many sequence in your life. We will write sequence as $\< a_i \>_{i\in\N}$, and each $a_i$ is a natural number for each $i$ which is a natural number. Let's consider the following sequence:
We define $a_0 := 1$, and we suppose that we have defined $a_n$ for some $n\in \N$ and define
\[
a_{n+1} := 2 a_n
\]
Let's look at the first few values of the sequence
\Hide{1cm}{
\[\< 1, 2, 4, 8, 16, 32, \cdots \>\]
}
Do you have a conjecture about what this sequence could be?
\begin{clm}
For every $n\in \N$ we have $a_n = 2^n$
\end{clm}
\begin{clmpf}
\Hide{2cm}{
We say recursion is a dual notion of induction because they are related. We often prove claims about recursively defined objects by induction.
So, we proceed by induction on $n$.
$a_0 = 1 = 2^0$, thus the base case is satisfied.
For our inductive hypothesis, we let $n$ be an arbitrary value and assume that $a_n = 2^n$. Now, we hope to prove that $a_{n+1} = 2^{n+1}$.
Well,
\[
a_{n+1} = 2\cdot a_n = 2\cdot 2^{n} = 2^{n+1}
\]
Thus, by induction we have the result for all $n\in \N$.
}
\end{clmpf}
\end{eg}
We can also have recursive sequences which are defined with more complications.
\begin{eg}
Define the sequence $a_i$ as follows:
\begin{alignat*}{3}
a_0 &= 0 \\
a_1 &= 2 \\
a_n &= 4(a_{n-1} - a_{n-2}) & \qquad\mbox{\it for $n\in \N$ and $n>1$}
\end{alignat*}
Let's look at this sequence
\Hide{1cm}{
\[
\< 2, 8, 40, 96, \ldots \>
\]
}
\end{eg}
Let's prove something about these numbers.
\begin{thm}
For all $n$, $a_n = n\cdot 2^n$.
\end{thm}
\begin{proof}
\Hide{1in}{
Note that $a_0 = 0$ which is $0\cdot 2^0$.
Now, suppose that $n$ is arbitrary, $n\geq 0$ and it is true for $n$. We want to show it is true for $n+1$.
We do {\bf not} have that $a_{n+1} = 4(a_{n} - a_{n-1})$. This is because $n$ could be $0$, and that formula only holds for $n>1$. Therefore, we have to do cases on whether $n$ is $0$ or not. Alternatively, we could have done $2$ base cases to ``bootstrap'' the inductive case.
If $n=0$, then similarly, $1\cdot 2^1 = 2 = a_1$.
So, we can assume $n>0$. Then $a_{n+1} = 4(a_n - a_{n-1})$. By our induction hypothesis, $a_n = n\cdot 2^n$ and $a_{n-1} = (n-1)\cdot 2^{n-1}$. So we have
\[
a_{n+1} = 4( n\cdot 2^n - (n-1)\cdot 2^{n-1} ) = 4\cdot 2^{n-1} ( 2n - n + 1) = 2^{n+1}(n+1)
\]
}
\end{proof}
\subsection{Stronger IH}
So far we've been essentially doing $\A n\in\N \stt \phi(n) \to \phi(n+1)$ in our induction step. This is all fine, but can we do better? More assumptions are good.
For example, back to the dominoes, why did we just assume that the domino $i$ fell to ask if the $i+1$th domino will fall? We actually really knew that all of the previous dominoes fell.
Therefore, we allow ourselves a stronger inductive step, which is to prove:
\[
\A n\in \N \stt \left( \A m \in \N \st m 15$, and so $n-4$ is on this interval. So by our induction hypothesis there is some combinations of stamps that allow us to make $n-4$ cent postage. Then, use that combination of postage, and add one additional $4$ cent stamp, and we have made the correct postage.
}
\end{proof}
\end{eg}
\begin{eg}
Every positive integer greater than $1$ can be factored as the product of powers of prime numbers.
\begin{proof}
\Hide{1in}{
We do this by induction on $n$. For $n=2$, we are done, as $2$ itself is prime.
Let $n$ be an arbitrary integer greater than $2$, and suppose it is true for every $1 < m < n$, and we seek to prove that is is true for $n$.
If $n$ is prime, then we are done. Otherwise, $n$ is not prime. Not prime means it has a proper factor (ie. not $1$ and not $n$). Call these factors $a$ and $b$, ie. $a\cdot b = n$. By induction $a$ and $b$ both have factors into powers of prime factors. Therefore $n$ is written as a product of prime powers.
}
\end{proof}
\end{eg}
Moreover, we can prove the following:
\begin{eg}
Every positive integer has a unique prime factorization.
\end{eg}
What are your ideas for how to prove this uniqueness result?
There two results together are called the \df{Fundamental Theorem of Arithmetic}
\end{document}