\documentclass{article}
\usepackage{fullpage,amsmath}
\usepackage{hyperref}
\usepackage{amssymb}
\usepackage{listings}
\usepackage{mathtools}


%%  Common macros for the course CSC165H1F,
%%  on the St. George Campus at the University of Toronto.
%%
%%  Copyright (c) 2009-2011 Francois Pitt <fpitt@cs.utoronto.ca>
%%
%%  This work may be distributed and/or modified under the conditions of
%%  the LaTeX Project Public License, either version 1.3 of this license
%%  or (at your option) any later version.
%%  The latest version of this license is in
%%      http://www.latex-project.org/lppl.txt
%%  and version 1.3 or later is part of all distributions of LaTeX
%%  version 2003/12/01 or later.
%%
%%  This work has the LPPL maintenance status "author-maintained".
%%
%%  The Current Maintainer of this work is
%%  Francois Pitt <fpitt@cs.utoronto.ca>.
%%
%%  This work consists of the file macros-165.tex.

% Trick so that math symbols are bold when text is.
\let\seiresfb\bfseries\def\bfseries{\boldmath\seiresfb}
\let\seiresdm\mdseries\def\mdseries{\unboldmath\seiresdm}

% Spacing macros with default argument.
\newcommand*{\vstretch}[1][1]{\vspace*{\stretch{#1}}}
\newcommand*{\hstretch}[1][1]{\hspace*{\stretch{#1}}}

% General fonts and characters.
\let\altemph\textsl  % alternate way to emphasize
\let\strong\textbf  % strong emphasis
\let\latinabb\emph  % abbreviations of latin phrases
\let\code\texttt  % code fragments
\let\const\textsf  % constants
\let\term\textbf  % newly-introduced (or defined) words
\let\var\mathrm  % multi-letter variables (or constants)
\let\pred\mathbf  % predicates
\newcommand*{\txtbksl} {\symbol{"5C}}% \
\newcommand*{\txtcaret}{\symbol{"5E}}% ^
\newcommand*{\txtunder}{\symbol{"5F}}% _
\newcommand*{\txtlcurl}{\symbol{"7B}}% {
\newcommand*{\txtrcurl}{\symbol{"7D}}% }
\newcommand*{\txttilde}{\symbol{"7E}}% ~
\newcommand*{\N}{\ensuremath{\mathbb{N}}}  % requires amssymb
\newcommand*{\Z}{\ensuremath{\mathbb{Z}}}  % requires amssymb
\newcommand*{\Q}{\ensuremath{\mathbb{Q}}}  % requires amssymb
\newcommand*{\R}{\ensuremath{\mathbb{R}}}  % requires amssymb
\newcommand*{\bigOh}{\mathcal{O}}
\newcommand*{\onehalf}{\ensuremath{{}^1\!\!/\!_2}}

% Abbreviations of latin phrases.
\newcommand*{\ie}{\latinabb{i.e.}}
\newcommand*{\eg}{\latinabb{e.g.}}
\newcommand*{\etc}{\latinabb{etc}}
\newcommand*{\vs}{\latinabb{vs}}

% General math macros.
\newcommand*{\comp}[1]{\overline{#1}}  % set complement
\newcommand*{\emptystr}{\varepsilon}  % empty string
\newcommand*{\lequiv}{\mathrel{\ \Longleftrightarrow\ }}  % equivalence
\newcommand*{\lxor}{\oplus}  % exclusive or
\newcommand*{\cat}{\cdot}  % string concatenation
\newcommand*{\invisible}[1]{\mathrel{\hphantom{#1}}}
% floors and ceilings, with optional size-changing command,
% e.g., \floor[\Big]{x/2} generates '\Big\lfloor{x/2}\Big\rfloor'
\newcommand*{\floor}[2][]{{#1\lfloor}{#2}{#1\rfloor}}
\newcommand*{\ceil}[2][]{{#1\lceil}{#2}{#1\rceil}}
\newcommand*{\lcm}{\operatorname{lcm}}  % requires amsmath
\newcommand*{\size}{\operatorname{size}}  % requires amsmath

% Redefined symbols from amssymb.
\renewcommand*{\emptyset}{\varnothing}  % rounder than default
\let\bigiff\iff
\renewcommand*{\iff}{\mathrel{\Leftrightarrow}}  % smaller than default
\let\bigimplies\implies
\renewcommand*{\implies}{\mathrel{\Rightarrow}}  % smaller than default
\renewcommand*{\ge}{\geqslant}  % with slanted line under the > sign
\renewcommand*{\le}{\leqslant}  % with slanted line under the < sign

% For algorithms, in Python.
\let\kw\textbf  % keywords
\let\proc\textsc  % function names
\newcommand*{\opgets}[1]{\mathrel{#1=}}
\newcommand*{\eq}{\mathrel{==}}
\newcommand*{\True}{\const{True}}
\newcommand*{\False}{\const{False}}
\newcommand*{\None}{\const{None}}
\newcommand*{\cmod}{\mathbin{\%}}
\newcommand*{\len}{\operatorname{len}}  % requires amsmath

% Like {itemize} but using less vertical space.
\newenvironment*{points}
 {\ifvmode\else\unskip\par\fi\begin{list}{$\bullet$}
   {\setlength{\topsep}{.25ex plus .125ex minus .1825ex}
    \setlength{\itemsep}{\topsep}\setlength{\parsep}{0ex}
    \setlength{\leftmargin}{1.75em}\setlength{\labelsep}{.5em}
    \setlength{\labelwidth}{1.75em}}\ignorespaces}
 {\ifvmode\else\unskip\fi\end{list}\ignorespaces}

% Checkboxes and checklists.
\newcommand*{\cbox}[1]{{\fboxrule.125ex\fboxsep0ex
    \framebox[2.75ex]{\rule[-.75ex]{0ex}{2.75ex}\smash{#1}}}}
\newcommand*{\cmark}{\raisebox{.0625ex}{$\surd$\kern.125ex}}
\newcommand*{\xmark}{\raisebox{-.1875ex}{\kern.0625ex{X}}}
\newcommand*{\checkbox}{{\sf\cbox{}}}
\newcommand*{\checkedbox}{{\sf\cbox{\cmark}}}
\newcommand*{\markedbox}{{\sf\cbox{\xmark}}}
\newenvironment{checklist}{\begin{list}{\checkbox}{}}{\end{list}}
\newcommand*{\checkeditem}{\item[\checkedbox]}
\newcommand*{\markeditem}{\item[\markedbox]}

% Proof-related environments and macros.
\newcommand*{\just}{{\quad\#\ }}  % justification for a proof step
\newenvironment*{pindent}
   {\begin{list}{}
       {\topsep 0pt
        \partopsep 0pt
        \itemsep 0pt
        \parsep 0pt
        \parskip 0pt}\item\relax}
   {\unskip\end{list}\ignorespaces}
% Usage: \begin{assumption}[<pre-text>]{<assumption>}
%          ...body...
%        \end{assumption}{<conclusion>}
% is formatted as
%    <pre-text> assume <assumption>
%        ...body...
%    <conclusion>
% or if <pre-text> is empty,
%    Assume <assumption>
%        ...body...
%    <conclusion>
\newenvironment*{assumption}[2][]
   {\unskip\ifvmode\else\par\fi
    {#1} \ifx\empty#1\empty\expandafter\uppercase\fi{a}ssume {#2}
    \begin{pindent}}
   {\end{pindent}}
% Usage: \begin{pickavalue}[<pre-text>]{<names>}
%          ...body...
%        \end{pickavalue}{<conclusion>}
% is formatted as
%    <pre-text> let <names>
%    ...body...
%    <conclusion>
% or if <pre-text> is empty,
%    Let <names>
%    ...body...
%    <conclusion>
\newenvironment*{pickavalue}[2][]
   {\unskip\ifvmode\else\par\fi
    {#1} \ifx\empty#1\empty\expandafter\uppercase\fi{l}et {#2}
    \par\ignorespaces}
   {\unskip\par\ignorespaces}



\DeclarePairedDelimiter\abs{\lvert}{\rvert}%
\DeclarePairedDelimiter\norm{\lVert}{\rVert}%



\title{CSC165, Summer 2014\\
Induction examples}

\renewcommand{\today}{~}
\hypersetup{pdfpagemode=Fullscreen,
  colorlinks=true,
  linkfileprefix={}}
\begin{document}
\maketitle


\section{Introduction: the Principle of Simple Induction}

The principle of simple induction is as follows. Assume that $P$ is a predicate. Then:
$$
	[P(0) \land (\forall n \in \mathbb{N}, P(n) \implies P(n+1))] \implies [\forall n \in \mathbb{N}, P(n)]
$$


In other words, if $P(0)$ is true ($n=0$ is called the \textit{base case}) and $P(n)$ implies $P(n+1)$ (this implication is called the \textit{induction step}, then $P(n)$ is true for any n. Why is this true? One way to think about it is that we can ``cook up" a proof that P(n) is true for any $n$ by repeatedly applying the induction step, starting from the claim that $P(n)$ is true: $P(0)$ is true, then $P(1)$ is true (\# implication), so $P(2)$ is true (\# implication),  so $P(3)$ is true (\#implication)... so $P(n)$ is true (\# implication). You can imagine writing a Python script to prove that $P(n)$ is true for any given $n$, so we know that $P(n)$ is true since we can prove it.



\section{Sum of an arithmetic series}

We prove that $0 + 1 + 2 + ... + n = \frac{n(n+1)}{2}$ for any natural $n$ using induction. Note that $0 + 1 + 2 + ... + n$ can be written as 
$$
	\sum_{i=0}^n i
$$

First, we define the predicate:

$$
	P(k) := \sum_{i=0}^k i = \frac{k(k+1)}{2}
$$

Note that $P(k)$ being true for all $k \in \mathbb{N}$ is exactly what we are trying to prove. We just restated the assertion in the form of a predicate.

We first prove the base case:

\begin{pindent}

	$\sum_{i=0}^0 = 0 = \frac{0(0+1)}{2}$\just{algebra}\\
	Then $P(0)$ is true \just{substitute k=0 into the definition of P(k)}\\
\end{pindent}

\newpage

We can now prove the induction step:

\begin{pindent}
	\begin{assumption}{$k \in \mathbb{N}$}
		\begin{assumption}{$P(k)$ is true}
			Then  $\sum_{i=0}^k i = \frac{k(k+1)}{2}$ \just{substitution of the definition of P}\\
			Then  $\sum_{i=0}^{k+1} i = (\sum_{i=0}^{k} i + (k+1)) = \frac{k(k+1)}{2} + k+1$ \just{algebra} \\
			Then  $\sum_{i=0}^{k+1} i = \frac{k(k+1)}{2} + \frac{2(k+1)}{2} = \frac{(k+2)(k+1)}{2} = \frac{(k+1)((k+1)+1)}{2}$\just{algebra}\\
			Then  $P(k+1)$ is true\just{substitution}
		\end{assumption}
		Then $P(k) \implies P(k+1)$\just{introduce implication}
	\end{assumption}
	Then $\forall k, P(k) \implies P(k+1)$ \just{introduce universal}\\
\end{pindent}

We can now conclude
\begin{pindent}
	$P(0)$\just{proven above}\\
	Also, $\forall k \in \mathbb{N}, P(k) \implies P(k+1)$\just{proven above}\\
	Then $\forall n \in \mathbb{N}, P(n)$\just{principle of simple induction}\\
	Then $\forall n \in \mathbb{N}, 0+1+2+4+...+n = \frac{n(n+1)/2}{2}$\just{substitution}
\end{pindent}


This proves the claim.


\section{The number of rows in a truth table}

We would like to prove that if a truth table has $n$ variables, then the table will have $2^n$ rows (i.e., possible values for all the variables.) For example, if there is only one variable in the truth table, $P$, it can have two values and so the table will just have two rows: $P = $ true and $P = $ false. (The number of columns might be larger: maybe one column is $P$, another is $\lnot P$, and another is $P\land P$. The first and third columns are equal, but part of the point of truth tables is that some columns may be equal, so that's okay.

As was pointed out in class, if there are zero variables, arguably the truth table has 0 rows, but $2^0 = 1$. So it makes sense to think about numbers of variables that are at least 1. We can still, of course, start counting from zero by setting up the predicate as:

Q(n) := the number of rows in a truth table with $n+1$ variables is $2^{n+1}$

With this predicate, $Q(0)$ means that the number of rows in  a truth table with one variable is two, which is true.

We generally prefer to implicitly generalize the principle of simple induction a little bit, and implicitly use the fact that 
$$
	\forall n_0 \in \mathbb{N}, [P(n_0) \land (\forall n \in \{n_0, n_0 + 1, n_0 + 2, ...\}, P(n) \implies P(n+1))] \implies [\forall n \in \{n_0, n_0 + 1, n_0 + 2, ...\}, P(n)]
$$

This fact is also referred to as the principle of simple induction. The base case will now be $P(n_0)$ for whatever $n_0$ we pick.

We define the predicate as:

P(n) := the number of rows in a truth table with $n$ variables is $2^{n}$

$P(0)$, unlike $Q(0)$, is false, so we have to use $n_0 = 1$ as the base case:


\begin{pindent}
	\begin{assumption}{ T is a truth table with $n_0 = 1$ variable }
		\begin{assumption}{WLOG the variable is called $P$}
			Then the truth table T contains a row for P = true and a row for P = false and no other row \just{only possible values}\\
			The the truth table T contains two rows \just{we listed all of the two possibilities}
		\end{assumption}
	\end{assumption}
	Then all truth tables with a single variable contains two rows.\just{introduce universal}
\end{pindent}


We can now prove the induction step. The basic idea is to observe that we can list all the lines of a truth table with $(n+1)$ variables by gluing together two truth tables for $n$ variables, and assigning True to the n-th variables the first time, and False the second time.

\newpage

\begin{pindent}
	\begin{assumption}{$n \in \{1,2,3,...\}$}	
		\begin{assumption}{$P(n)$ is true}
			\begin{assumption}{T is a truth table with (n+1) variables (WLOG, call them $P_1$, $P_2$, ..., $P_n$, $P_{n+1}$. Assume WLOG that all the truth tables under consideration only have variables (and not expressions) as columns (since additional columns don't matter)}
			Then we can build the rows of T by taking the rows of the truth table for $P_2$, ..., $P_{n+1}$ twice, setting the value of $P_1$ as true the first time, and as false the second time \just{the possible values of $P_2$...$P_{n+1}$ are the same in the smaller table as in the larger table, and the only possible values of $P_1$ are true and false}\\
				Then T is twice as large as the truth table for $P_2$...$P_{n+1}$ \just{T is built by taking that truth table and writing it twice, varying the values of $P_1$}
				The size of the truth table for $P_2$, ..., $P_{n+1}$ is $2^n$\just{P(n) is true by assumption}\\
				Then the size of T is $2 2^{n} = 2^{n+1}$\just{algebra}
			\end{assumption}
			Then $P(n+1)$\just{substitution all tables with the same number of variables have the same number of rows}
		\end{assumption}
		Then $P(n)\implies P(n+1)$\just{introduce implication}
	\end{assumption}
	Then $\forall n \in \{1,2,3,...\}. P(n)\implies P(n+1)$\just{introduce universal}
\end{pindent}

We can now finish the proof:
\begin{pindent}
	$P(1)$\just{proven above}\\
	Also, $\forall k \in \{1,2,3,...\}, P(k) \implies P(k+1)$\just{proven above}\\
	Then $\forall n \in \{1,2,3,...\}, P(n)$\just{principle of simple induction}\\
	Then for all natural $n \ge 1$, a truth table with $n$ variables has $2^n$ rows\just{substitution}
\end{pindent}




\end{document}