\documentclass[12pt, oneside]{article}

\usepackage[letterpaper, scale=0.89, centering]{geometry}
\usepackage{fancyhdr}
\setlength{\parindent}{0em}
\setlength{\parskip}{1em}

\pagestyle{fancy}
\fancyhf{}
\renewcommand{\headrulewidth}{0pt}
\rfoot{\href{https://creativecommons.org/licenses/by-nc-sa/2.0/}{CC BY-NC-SA 2.0} Version \today~(\thepage)}

\usepackage{amssymb,amsmath,pifont,amsfonts,comment,enumerate,enumitem}
\usepackage{currfile,xstring,hyperref,tabularx,graphicx,wasysym}
\usepackage[labelformat=empty]{caption}
\usepackage{xcolor}
\usepackage{multicol,multirow,array,listings,tabularx,lastpage,textcomp,booktabs}

\lstnewenvironment{algorithm}[1][] {   
    \lstset{ mathescape=true,
        frame=tB,
        numbers=left, 
        numberstyle=\tiny,
        basicstyle=\rmfamily\scriptsize, 
        keywordstyle=\color{black}\bfseries,
        keywords={,procedure, div, for, to, input, output, return, datatype, function, in, if, else, foreach, while, begin, end, }
        numbers=left,
        xleftmargin=.04\textwidth,
        #1
    }
}
{}
\lstnewenvironment{java}[1][]
{   
    \lstset{
        language=java,
        mathescape=true,
        frame=tB,
        numbers=left, 
        numberstyle=\tiny,
        basicstyle=\ttfamily\scriptsize, 
        keywordstyle=\color{black}\bfseries,
        keywords={, int, double, for, return, if, else, while, }
        numbers=left,
        xleftmargin=.04\textwidth,
        #1
    }
}
{}

\newcommand\abs[1]{\lvert~#1~\rvert}
\newcommand{\st}{\mid}

\newcommand{\A}[0]{\texttt{A}}
\newcommand{\C}[0]{\texttt{C}}
\newcommand{\G}[0]{\texttt{G}}
\newcommand{\U}[0]{\texttt{U}}

\newcommand{\cmark}{\ding{51}}
\newcommand{\xmark}{\ding{55}}

 
\begin{document}
\begin{flushright}
    \StrBefore{\currfilename}{.}
\end{flushright} \section*{Structural induction example robot grid}


\begin{center}
    \includegraphics[width=3in]{../../resources/images/robot-grid.png}
\end{center}
    
{\bf Theorem}: A robot on an infinite 2-dimensional integer grid starts at $(0,0)$ and at each step moves
to diagonally adjacent grid point. This robot can / cannot {\footnotesize({\it circle one})} reach $(1,0)$.


{\bf Definition} The set of positions the robot can visit  $Pos$ is defined by:
\[
\begin{array}{ll}
    \textrm{Basis Step: } & (0,0) \in Pos \\
    \textrm{Recursive Step: } & \textrm{If } (x,y) \in Pos \textrm{, then } \\
    &\phantom{(x+1, y+1), (x+1, y-1), (x-1, y-1), (x-1, y+1)} \textrm{ are also in } Pos
\end{array}
\]

{\it Example elements of $Pos$ are}:
\vspace{20pt}

\newpage
{\bf Lemma}: $\forall (x,y) \in Pos~~( x+y \textrm{ is an even integer}~)$

{\it Why are we calling this a lemma?}


Proof of theorem using lemma: To show is $(1,0) \notin Pos$. Rewriting the lemma to explicitly 
restrict the domain of the universal, 
we have $\forall (x,y) ~(~ (x,y) \in Pos~~  \to ~~(x+y \textrm{ is an even integer})~)$.  Since
the universal is true, 
$ (~ (1,0) \in Pos~~ \to ~~(1+0 \textrm{ is an even integer})~)$ is a true statement.
Evaluating the conclusion of this conditional statement: 
By definition of long division, since $1 = 0 \cdot 2 + 1$ (where $0 \in \mathbb{Z}$ and 
$1 \in \mathbb{Z}$ and $0 \leq 1 < 2$ mean that $0$ is the quotient and $1$ is the remainder), $1 ~\textrm{\bf mod}~ 2 = 1$ which is not $0$ 
so the conclusion is false.  A true conditional with a false conclusion must have a false hypothesis: $(1,0) \notin Pos$, QED. $\square$

\vspace{20pt}

Proof of lemma by structural induction:

{\bf Basis Step}:

\vspace{100pt}


{\bf Recursive Step}:  Consider arbitrary $(x,y) \in Pos$.  To show is:
\[
(x+y \text{ is an even integer}) \to (\text{sum of coordinates of next position is even integer})
\]
Assume {\bf as the induction hypothesis, IH} that: 


\vspace{400pt} \vfill
\section*{Fundamental theorem proof}


{\bf Theorem}: Every positive integer {\it greater than 1} is a product of (one or more) primes.

{\bf Before we prove, let's try some examples}:

$20 = $

$100 = $

$5 = $


{\bf Proof by strong induction}, with $b=2$ and $j=0$.

{\bf Basis step}:  WTS property is true about  $2$.

Since $2$ is itself prime,
it is already written as a product of (one) prime.


{\bf Recursive step}: Consider an arbitrary integer $n \geq 2$.
Assume (as the strong induction hypothesis, IH) that the property is true about  each of $2, \ldots, n$.  
WTS that the property is true about  $n+1$: We want to show that $n+1$ can be written 
as a product of primes.  Notice that $n+1$ is itself prime or it is composite.

{\it Case 1}: assume $n+1$ is prime and then immediately it is written as a product
of (one) prime so we are done.  

{\it Case 2}: assume that $n+1$ is composite
so there are integers $x$ and $y$ where $n+1 = xy$ and each of them is between $2$ and $n$
(inclusive).  Therefore, the induction hypothesis applies to each of $x$ and $y$ so each 
of these factors of $n+1$ can be written as a product of primes.  Multiplying these products together, 
we get a product of primes that gives $n+1$, as required. 

Since both cases give the necessary
conclusion, the proof by cases for the recursive step is complete. \vfill
\section*{Strong induction making change proof idea}


Suppose we had postage stamps worth $5$ cents and $3$ cents.
Which number of cents can we form using these stamps?
In other words, which postage can we pay?

$11$? 

$15$? 


$4$?



\begin{align*}
    &CanPay(0) \land \lnot CanPay(1) \land \lnot CanPay(2) \land \\
    &CanPay(3) \land \lnot CanPay(4) \land CanPay(5) \land CanPay(6) \\
    &\lnot CanPay(7) \land \forall n \in \mathbb{Z}^{\geq 8} CanPay(n)
\end{align*}

where the predicate $CanPay$ with domain $\mathbb{N}$ is
\[
    CanPay(n) = \exists x \in \mathbb{N} \exists y \in \mathbb{N}  ( 5x+3y = n)
\]


{\bf Proof} (idea): First, explicitly give witnesses or general arguments
for postages between $0$ and $7$. 
To prove the universal claim, we can use mathematical induction or strong induction.

{\it Approach 1, mathematical induction}: if we have
stamps that add up to $n$ cents, need to use them (and others)
to give $n+1$ cents. How do we get $1$ cent with just $3$-cent
and $5$-cent stamps?

\vspace{-10pt}
Either \underline{take away a $5$-cent stamps and add two $3$-cent stamps},

\vspace{-10pt}
or \underline{take away three $3$-cent stamps and add two $5$-cent stamps}.

\vspace{-10pt}
The details of this proof by mathematical induction
are making sure we have enough 
stamps to use one of these approaches.

{\it Approach 2, strong induction}: assuming we know how to make postage
for {\bf all} smaller values (greater than or equal to $8$), when
we need to make $n+1$ cents, \underline{add one $3$ cent stamp to 
however we make $(n+1) - 3$ cents}.

\vspace{-10pt}
The details of this proof by strong induction are making sure we 
stay in the domain of the universal when applying the induction hypothesis.
 \vfill
\section*{Strong induction nim}


Consider the following game: two players start with 
two (equal) piles of jellybeans in front of them.
They take turns removing any positive integer number
of jellybeans at a time from one of two piles in 
front of them in turns.

The player who removes the last jellybean wins the game.

Which player (if any) has a strategy to guarantee
to win the game?


Try out some games, starting with $1$ jellybean in each pile,
then $2$ jellybeans in each pile, then $3$ jellybeans in each pile.
Who wins in each game?

\vspace{200pt}


Notice that reasoning about the strategy for the $1$ jellybean 
game is easier than about the strategy for the $2$ jellybean game.

{\it Formulate a winning strategy by working to 
transform the game to a simpler one we know we can win.}

\newpage

{\it Player 2's Strategy}: Take the same number of jellybeans that Player 1 did, 
but from the opposite pile. 


{\it Why is this a good idea}: If Player 2 plays this strategy, at the next turn
Player 1 faces a game with the same setup as the original, just with fewer
jellybeans in the two piles. Then Player 2 can keep playing this strategy to win.

{\bf Claim}: Player 2's strategy guarantees they will win the game.

{\bf Proof}: By strong induction, we will prove that for all positive 
integers $n$, Player 2's strategy guarantees a win in the game that starts with 
$n$ jellybeans in each pile.

{\bf Basis step}: WTS Player 2's strategy guarantees a win 
when each pile starts with $1$ jellybean.

In this case, Player 1 has to take the jellybean from one of the piles
(because they can't take from both piles at once).
Following the strategy, Player 2 takes the jellybean from the 
other pile, and wins because this is the last jellybean.

{\bf Recursive step}: Let $n$ be a positive integer. 
As the strong induction hypothesis, assume that
Player 2's strategy guarantees a win in the games 
where there are $1, 2, \ldots, n$ many jellybeans in each 
pile at the start of the game.

WTS that Player 2's strategy guarantees a win in the game where
there are $n+1$ in the jellybeans in each pile at the start of the game.

In this game, the first move has Player 1 take 
some number, call it $c$ (where $1 \leq c \leq n+1$),
of jellybeans from one of the piles. 
Playing according to their strategy, Player 2 then 
takes the same number of jellybeans from  the other pile.

Notice that $(c = n+1) \lor (c \leq n)$.

{\it Case 1}: Assume $c = n+1$, then in their first move, 
Player 2 wins because they take all of the second pile, which 
includes the last jellybean.

{\it Case 2}: Assume $c \leq n$. Then after Player 2's first move,
the two piles have an equal number of jellybeans. The number
of jellybeans in each pile is 
\[
    (n+1) - c
\]
and, since $1 \leq c \leq n$, this number is between $1$ and $n$.
Thus, at this stage of the game, the game appears identical to a new 
game where the two piles have an equal number of jellybeans between $1$
and $n$. Thus, the strong induction hypothesis applies, and Player 2's
strategy guarantees they win.

 \vfill
\end{document}