<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass{article}

\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{changepage}  % For adjustwidth environment
\usepackage{environ}
\usepackage{framed}  % For leftbar environment
\usepackage[hidelinks]{hyperref}  % For \autoref
\usepackage{mathtools}  % For \shortintertext
\usepackage{parskip}  % Don't indent paragraphs; skip instead.
\usepackage{tikz}
\usepackage{url}

\newenvironment{indentone}{\begin{adjustwidth}{3em}{0em}}{\end{adjustwidth}}

% Binary and unary all-uppercase text operators. \mathop gives too little space
% around the binary ones; e.g. \(P \op{AND} Q\) needs lots of space between
% those capital letters.
\newcommand\op[1]{{\ \mathrm{#1}\ }}
\newcommand\uop[1]{{\mathrm{#1}}}

\newcommand\AND{{\op{AND}}}
\newcommand\IFF{{\op{IFF}}}
\newcommand\IMPLIES{{\op{IMPLIES}}}
\newcommand\NOT{{\uop{NOT}}}
\newcommand\OR{{\op{OR}}}
\newcommand\XOR{{\op{XOR}}}

\newcommand\FALSE{{\mathrm{F}}}
\newcommand\TRUE{{\mathrm{T}}}

\newcommand\Ints{{\mathbb{Z}}}
\newcommand\Nats{{\mathbb{N}}}
\newcommand\Reals{{\mathbb{R}}}

\newtheorem{theorem}{Theorem}

\begin{document}

These are \emph{rough notes} based on my own notes I prepared for the Week~4
lecture. They go with the annotated lecture slides you can see on the ``More''
page of the course website. Although they are rough, I'm providing them here in
case they help you remember what we did in lecture.

\section{Induction}

\subsection{Introduction: Tiling a chess board}

\begin{theorem}\label{thm:tileChess}
Consider any square chessboard whose sides have length which is a power of 2.
If any one square is removed, then then the resulting shape can be tiled using
only 3-square L-shaped tiles.
\end{theorem}

\[
\vcenter{\hbox{
\begin{tikzpicture}[scale=0.5]
\draw[fill=white] (0,0) rectangle (8,8);
\draw (0,0) grid (8,8);
\draw[style=fill] (5,3) rectangle (6,4);
\end{tikzpicture}
}}
\Longrightarrow
\vcenter{\hbox{
\begin{tikzpicture}[scale=0.5]
\draw[fill=white] (0,0) rectangle (8,8);
\draw (0,0) grid (8,8);
\draw[style=fill] (5,3) rectangle (6,4);
\foreach \p/\a in {(4,2)/0,(7,1)/90,(8,4)/180,(8,0)/90,(4,0)/0,(3,5)/270,(2,2)/0,(1,1)/0,(4,0)/90,(0,0)/0,(0,4)/270,(2,6)/270,(1,7)/270,(0,4)/0,(0,8)/270,(4,8)/180,(6,6)/180,(7,7)/180,(4,8)/270,(8,8)/180,(8,4)/90}
\draw[style={fill=green!20},shift=\p,rotate=\a] (0.2,0.2) -- (1.8,0.2) -- (1.8,0.8) -- (0.8,0.8) -- (0.8,1.8) -- (0.2,1.8) -- (0.2,0.2);
\end{tikzpicture}
}}
\]

A proof you should be suspicious of:

Divide the board into four equal quadrants.

The quadrant with the missing square meets the conditions for
\autoref{thm:tileChess}, so it can be tiled.

Place one tile in the middle covering the corners of the three remaining
quadrants. After removing that corner square from a quadrant, the rest of the
quadrant can be tiled using \autoref{thm:tileChess}. So we have tiled
everything. \qed

(The $\square$ symbol means the proof is done.)

Problems:

\begin{itemize}
\item We're assuming \autoref{thm:tileChess} is true in order to prove it. You
should be very suspicious of this proof.
\item Our proof doesn't work for a 1x1 board. This is easy to fix by splitting
the proof into 1x1 and not 1x1 cases.

\emph{Insert before proof:}

Case 1: board is 1x1. Then after removing the square, the board is empty, so it
can be tiled with 0 tiles.

Case 2: board is not 1x1.
\end{itemize}

Even though the proof has this suspicious circularity, the tiling method it
describes still works, as you can see in the diagram above.

How can we make this proof more convincing?
Before we get there, I'm going to make a small detour.

\subsection{Simple Induction Example}

Suppose all these propositions are true:
\begin{itemize}
\item A
\item A IMPLIES B
\item B IMPLIES C
\item[\vdots]
\item Y IMPLIES Z
\end{itemize}
What can you conclude about the values of A, B, \ldots, Z?

Answer: you can conclude they're all true, by starting with \(A=\TRUE\), then
concluding \(B=\TRUE\), and so on.

We're going to do the same thing with numbers.

\begin{theorem}
\(\sum_{k=0}^nk=\tfrac12n^2+\tfrac12n\) for every natural number
\(n\).
\end{theorem}

There are different ways to prove this, but I'm going to do it using our
current topic, which is induction.

Proof by induction:

For \(n\in\Nats\), let \(P(n)=\) ``\(\sum_{k=0}^nk=\tfrac12n^2+\tfrac12n\)''.

Base case: \\
\(0 = \tfrac120^2+\tfrac120\). \\
So \(P(0)\).

Induction step:
\begin{indentone}
Let \(n\in\Nats\) be arbitrary.
\begin{indentone}
Assume \(P(n)\). \quad (Induction Hypothesis)
\begin{flalign*}
  &amp; \tfrac12(n+1)^2+\tfrac12(n+1) &amp; \\
  =&amp; \tfrac12(n^2+2n+1)+\tfrac12(n+1) \\
  =&amp; \tfrac12n^2+\tfrac12n+n+1 \\
  =&amp; \underbrace{\left( \sum_{k=0}^n k \right)}_{\text{by Induction Hypothesis}} + (n+1) \\
  =&amp; \sum_{k=0}^{n+1} k
\end{flalign*}
So \(P(n+1)\).
\end{indentone}
So \(P(n) \IMPLIES P(n+1)\).
\end{indentone}
So \(\forall n\in\Nats.\&gt;(P(n) \IMPLIES P(n+1))\).

By induction, \(\forall n\in\Nats.\&gt;P(n)\). \qed

\subsection{Induction inference rule}

Here's the rule for using induction in a proof:

\textbf{Inference rule for induction:}

Define some predicate \(P:\Nats\to\{\TRUE,\FALSE\}\).

\begin{itemize}
\item[\vdots]
\item[10.] \(P(0)\)
\begin{itemize}
\item[11.] Let \(n\in\Nats\) be arbitrary.
\begin{itemize}
\item[12.] Assume \(P(n)\)
\item[\vdots]
\item[18.] \(P(n+1)\)
\end{itemize}
\item[19.] \(P(n)\IMPLIES P(n+1)\) \quad direct proof 12,18
\end{itemize}
\item[20.] \(\forall n\in\Nats.\&gt;(P(n)\IMPLIES P(n+1))\) \quad generalization 11,19
\item[21.] \(\forall n\in\Nats.\&gt;P(n)\) \quad induction 10,20
\end{itemize}

Line 10 is the ``base case'' or ``basis''. Line 12 is the ``induction hypothesis''. Lines 11-20 as ``induction step''.

Lines 19 and 20 are optional. If you don't use them, you could justify line~21 as ``induction 10,11..18'' instead of ``induction 10,20''.

\subsection{Tiling a chessboard with induction}

(Repeat statement of \autoref{thm:tileChess}.)

So, let's try proving this by induction. One problem is that we only know how
to use induction to prove things that start with ``for all natural numbers n''.

So, we should find some predicate \(P:\Nats\to\{\TRUE,\FALSE\}\) such that the
theorem is logically equivalent to \(\forall n\in\Nats.\&gt;P(n)\).

What can we use for \(P(n)\)?

This works: \(P(n)=\) ``Every \(2^n \times 2^n\) chessboard with one square
removed can be tiled using \emph{(draw L-shaped tile)}.''

Proof:

We wish to prove \(\forall n\in\Nats.P(n)\).

Base case. \\
A \(2^0\times2^0=1\times1\) chessboard with one square removed has no squares.
We can tile it with no tiles. \\
So \(P(0)\).

Induction step.
\begin{indentone}
Let \(n\in\Nats\) be arbitrary.
\begin{indentone}
Assume \(P(n)\). \quad (Induction Hypothesis)
\begin{indentone}
Consider any \(2^{n+1}\times2^{n+1}\) chessboard. \\
\emph{Copy and paste previous proof.}
\emph{Replace references to ``\autoref{thm:tileChess}'' with ``by I.H.''.}
\end{indentone}
So \(P(n+1)\).
\end{indentone}
So \(P(n) \IMPLIES P(n+1)\).
\end{indentone}
So \(\forall n\in\Nats.\&gt;(P(n) \IMPLIES P(n+1))\).

By induction, \(\forall n\in\Nats.\&gt;P(n)\). \qed

\subsection{Strengthening the induction hypothesis}

(Repeat \autoref{thm:tileChess}.)

\begin{theorem}\label{thm:tileChessMiddle}
All square chessboards with sides of length a power of 2 and with one square
removed from the middle can be tiled using L-tiles.
\end{theorem}

\autoref{thm:tileChess} implies \autoref{thm:tileChessMiddle}. What if we try
to prove \autoref{thm:tileChessMiddle} directly?

It doesn't work. In the induction step, there's a square taken out of the
corner, so the induction hypothesis is useless.

\autoref{thm:tileChess} is easier to prove.

\textbf{Strengthening the induction hypothesis}: a method for proving
\(\forall n\in\Nats.\&gt;P(n)\). Choose a ``stronger'' predicate \(Q\):
\(\forall n\in\Nats.\&gt;(Q(n)\IMPLIES P(n))\). Prove
\(\forall n\in\Nats.\&gt;Q(n)\). This way, assuming the induction hypothesis is
more useful.

\subsection{Different structures}

\subsubsection{Starting at 3}

\begin{theorem}\label{thm:linLeExp}
\ [This was a deliberately false statement, corrected a bit later in the
lecture.]

\(\forall n\in\Nats.\&gt;2n+1\le2^n\)
\end{theorem}

Proof:

For \(n\in\Nats\), let \(Q(n)=\) ``\(2n+1\le 2^n\)''.

Base case: \\
\(2\cdot0+1=1\le1=2^0\) \\
So \(Q(0)\).

Induction step:
\begin{indentone}
Let \(n\in\Nats\) be arbitrary
\begin{indentone}
Assume \(Q(n)\). \\
\begin{flalign*}
&amp; 2(n+1)+1 &amp; \\
=&amp; (2n+1)+2 \\
\le&amp; 2^n+2 \\
\le&amp; 2^{n+1}\ ??
\end{flalign*}
\vdots \\
\(Q(n+1)\).
\end{indentone}
\end{indentone}

Doesn't work. \(Q(1),Q(2)\) false. \(Q(n)\) true for \(n\ge 3\).

Replace statement of \autoref{thm:linLeExp} with:
\(\forall n\in\Nats.\&gt;(n\ge 3\IMPLIES2n+1\le2^n)\). Or,
\(\forall n\in M.\&gt;2n+1\le2^n\), where \(M=\{n\in\Nats|n\ge3\}\).

How can we use induction to prove this?

Proof:

\begin{tabular}{p{0.45\hsize}|p{0.45\hsize}}
  Idea~1: For \(n\in\Nats\), let \(P(n)=Q(n+3)\). Then \autoref{thm:linLeExp}
  equivalent to \(\forall n\in\Nats.\&gt;P(n)\).
  &amp;
    Idea~2: \\
  Base case: P(0) &amp; Base case: Q(3) \\
  \\
  Induction step: \\
  \quad Let \(n\in\Nats\) be arbitrary. &amp; \quad Let \(m\in M\) be arbitrary. \\
  \qquad Assume \(P(n)\). &amp; \qquad Assume \(Q(m)\). \\
  \qquad \vdots &amp; \qquad \vdots \\
  \qquad \(P(n+1)\) &amp; \qquad \(Q(m+1)\) \\
  \quad \(P(n)\IMPLIES P(n+1)\) &amp; \quad \(Q(n)\IMPLIES Q(n+1)\) \\
  \(\forall n\in\Nats.\&gt;(P(n)\IMPLIES P(n+1))\) &amp; \(\forall m\in M.\&gt;(Q(m)\IMPLIES Q(m+1))\) \\
  \(\forall n\in\Nats.\&gt;P(n)\) &amp; \(\forall m\in M.\&gt;Q(m)\)
\end{tabular}

Two different ways to prove the same thing. Use either one.

There's a third way: on the ``Further reading'' page of the home page, see ``An
alternative to a proof presented in Week 4'' in the ``Week 4'' section.

\subsubsection{Even numbers}

What if we want to prove a predicate is true only for even numbers?

Suppose we have a predicate \(Q:\Nats\to\{\TRUE,\FALSE\}\), and we want to
prove
\[\forall n\in\Nats.\&gt;((\text{\(n\) is even})\IMPLIES Q(n))\]
using induction.

One approach: for \(k\in\Nats\), let \(P(k)=Q(2k)\).

Then \(\forall n\in\Nats.\&gt;((\text{\(n\) is even})\IMPLIES Q(n))\) means same
as \(\forall k\in\Nats.\&gt;P(k)\).

Base case: \(P(0)=Q(0)\).

Induction step: given \(k\), prove \(P(k)\IMPLIES P(k+1)\). Same as \(Q(2k)\IMPLIES Q(2k+2)\).

So, enough to prove: \\
\(Q(0)\) \\
\(\forall n\in\Nats.\&gt;(Q(n)\IMPLIES Q(n+2))\).

\(Q(0)\IMPLIES Q(2)\), \(Q(1)\IMPLIES Q(3)\), \ldots

However, \(Q(1)\IMPLIES Q(3)\) is a stronger statement than we actually need to
prove. It may not be true, even if \(P(n)\) is true for all even \(n\).

Enough to prove: \\
\(Q(0)\) \\
\(\forall n\in\Nats.\&gt;((\text{(\(n\) is even)}\AND Q(n))\IMPLIES Q(n+2))\).

On a slide: four number lines 0 1 \(\cdots\) 10

So, let's review the ways we've done induction.

\emph{(Beside the first number line)} \\
\(P(0)\) \\
\(\forall n\in\Nats.\&gt;(P(n)\IMPLIES P(n+1))\) \\
\emph{Draw an arrow into 0, and arrows from 0 to 1, 1 to 2, etc. Put checkboxes in all numbers.}

\emph{(Beside the second number line)} \\
\(P(3)\) \\
\(\forall n\in\Nats.\&gt;((n\ge 3\AND P(n))\IMPLIES P(n+1))\) \\
\emph{Draw an arrow into 3, and arrows from 3 to 4, 4 to 5, etc. Put checkboxes
  in all numbers starting from 3.}

\emph{(Beside the third number line)} \\
\(P(0)\) \\
\(\forall n\in\Nats.\&gt;((\text{(\(n\) is even)}\AND P(n))\IMPLIES P(n+2))\)
\emph{Draw an arrow into 0, and arrows from 0 to 2, 2 to 4, etc. Put checkboxes
  in all even numbers.}

Here's a new one.

\emph{(Beside the fourth number line)} \\
\(P(1)\) \\
\(\forall n\in\Ints^+.\&gt;(P(n)\IMPLIES P(2n))\) \\
\(\forall n\in\Ints^+.\&gt;(P(n+1)\IMPLIES P(n))\) \\
\emph{Add arrows and check boxes until all the boxes are checked except 0.}

We're going to use it to prove this theorem.

\begin{theorem}
For any \(n\in\Ints^+\) and any non-negative real numbers \(a_1,\dotsc,a_n\),
\[(a_1 a_2 \dotsb a_n)^{1/n} \le \frac{a_1 + a_2 + \dotsb + a_n}n\]
\end{theorem}

\((a_1 a_2 \dotsb a_n)^{1/n}\) is called the ``geometric mean'' and
\(\frac{a_1 + a_2 + \dotsb + a_n}n\) is called the ``arithmetic mean''.

Proof:

For \(n\in\Ints^+\), let \(P(n)=\) ``for all
\(a_1,\dotsc,a_n\in\Reals^{\ge0}\),
\((a_1+\dotsb+a_n)^{1/n}\le\frac{a_1+\dotsb+a_n}n\)''.

(\(\Reals^{\ge0}\) is the set of non-negative real numbers.)

Base case: \(n=1\). Let \(a_1\) be a nonneg real. \(a_1^{1/1}\le a_1/1\). By
generalization, forall \(a_1\in\Reals^{\ge0}.\&gt;a_1^{1/1}\le a_1/1\). So
\(P(1)\).

First induction step ($2\rightarrow 2n$):
\begin{indentone}
Let \(n\in\Ints^+\) be arbitrary.
Assume \(P(n)\). \quad I.H.
\begin{indentone}
Let \(a_1,\dotsc,a_{2n}\in\Reals^{\ge0}\) be arbitrary.
\[
  (a_1 \dotsb a_{2n})^{1/2n}
  = \underbrace{[(a_1 \dotsb a_n)^{1/n}]^{1/2}}_x\underbrace{[(a_{n+1} \dotsb a_{2n})^{1/n}]^{1/2}}_y
\]
\begin{align*}
  (x-y)^2\ge&amp;0 \\
  x^2-2xy+y^2\ge&amp;0 \\
  x^2+y^2\ge&amp;2xy \\
  (a_1\dotsb a_n)^{1/n}+(a_{n+1}\dotsb a_{2n})^{1/n}\ge&amp;2(a_1\dotsb a_{2n})^{1/{2n}} \\
  \shortintertext{by I.H, LHS \(\le (a_1+\dotsb+a_n)/n+(a_{n+1}+\dotsb+a_{2n})/n\)}
  (a_1+\dotsb+a_{2n})/n\ge&amp;2(a_1\dotsb a_{2n})^{1/2n} \\
  (a_1\dotsb a_{2n}^{1/2n}\le&amp;\frac{a_1+\dotsb+a_{2n}}{2n}
\end{align*}
\end{indentone}
So \(\forall a_1,\dotsb,a_{2n}\in\Reals^{\ge0}.\cdots\), i.e\ \(P(2n)\).
\end{indentone}
So \(\forall n\in\Ints^+.\&gt;(P(n)\IMPLIES P(2n))\).

Second induction step (\(n+1\rightarrow n\)):
\begin{indentone}
Let \(n\in\Ints^+\) be arbitrary. Assume \(P(n+1)\). \quad I.H.
\begin{indentone}
Let \(a_1,\dotsc,a_n\in\Reals^{\ge0}\) be arbitrary. \\
Let \(b_1=a_1,b_2=a_2,\dotsc,b_n=a_n,b_{n+1}=\frac{a_1+\dotsb+a_n}n\).
By I.H,
\begin{align*}
  (b_1 \dotsb b_{n+1})^{1/(n+1)} \le&amp; \tfrac1{n+1}(b_1+\dotsb+b_{n+1}) \\
  =&amp; \tfrac1{n+1}(n\frac{b_1+\dotsb+b_n}n+b_{n+1}) \\
  =&amp; \tfrac1{n+1}(nb_{n+1}+b_{n+1}) \\
  =&amp; \tfrac1{n+1}(n+1)b_{n+1} \\
  =&amp; b_{n+1} \\
  (b_1\dotsb b_n)^{1/(n+1)} \le&amp; b_{n+1}^{n/(n+1)} \\
  (b_1\dotsb b_n)^{1/n} \le&amp; b_{n+1}
\end{align*}
\end{indentone}
So \(\forall b_1,\dotsc,b_n\in\Reals{\ge0}.\cdots\), i.e.\ \(P(n)\).
\end{indentone}
So \(\forall n\in\Ints^+.\&gt;(P(n+1)\IMPLIES P(n))\).

By induction, \(\forall n\in\Ints^+.\&gt;P(n)\). \qed

\subsubsection{Induction over a finite range}

What if we want to prove a predicate is true for a finite range of integers?

How can we prove \(\forall n\in\{0,1,\dotsc,n\}.\&gt;P(n)\) using induction?

Base case: \(P(0)\).

Induction step:
\begin{indentone}
Let \(k\in\{0,1,\dotsc,n-1\}\) be arbitrary.
\begin{indentone}
Assume \(P(k)\). \\
\vdots \\
\(P(k+1)\)
\end{indentone}
\(P(k)\IMPLIES P(k+1)\) \quad direct proof \quad \emph{(this line optional)}
\end{indentone}
\(\forall k\in\{0,1,\dotsc,n-1\}.\&gt;(P(k)\IMPLIES p(k+1))\) \quad generalization \quad \emph{(this line optional)} \\
\(\forall k\in\{0,1,\dotsc,n\}.\&gt;P(n)\) \quad induction

\subsection{Complete/strong induction}

From
\begin{itemize}
\item \(P(0)\)
\item \(P(0)\IMPLIES P(1)\)
\item \((P(0)\AND P(1))\IMPLIES P(2)\)
\item \((P(0)\AND P(1)\AND P(2))\IMPLIES P(3)\)
\item \((P(0)\AND P(1)\AND P(2)\AND P(3))\IMPLIES P(4)\)
\item[\vdots]
\end{itemize}
we can conclude \(\forall n\in \Nats.\&gt;P(n)\)

\textbf{Complete induction} (strong induction)

To prove \(\forall n\in\Nats.\&gt;P(n)\), prove
\[\forall n\in\Nats.\&gt;((\forall k\in\Nats.\&gt;(k&lt;n\IMPLIES P(k)))\IMPLIES P(n))\]

\textbf{Complete induction template}

\begin{indentone}
Let \(n\in\Nats\) be arbitrary.
\begin{indentone}
Assume \(\forall k\in\Nats.\&gt;(k&lt;n\IMPLIES P(k))\). \\
\vdots \\
\(P(n)\)
\end{indentone}
\((\forall k\in\Nats.\&gt;(k&lt;n\IMPLIES P(k)))\IMPLIES P(n)\) \quad direct proof
\end{indentone}
\(\forall n\in\Nats.\&gt;((\forall k\in\Nats.\&gt;(k&lt;n\IMPLIES P(k)))\IMPLIES P(n))\) \quad generalization \\
\(\forall n\in\Nats.\&gt;P(n)\) \quad strong induction

(\emph{The second-last and third-last lines (direct proof, generalization) are optional.}

Why don't we need a base case?

Case \(P(0)\) handled by \(n=0\):
\[(\forall k\in\Nats.(k&lt;0\IMPLIES P(k)))\IMPLIES P(0)\]
\emph{Mark the LHS of the IMPLIES as ``vacuously true''.}

But you could put one in anyway if you like:

\textbf{Alternative complete induction template}

Base case: \\
\vdots \\
\(P(0)\)

\begin{indentone}
Let \(n\in\Ints^+\) be arbitrary.
\begin{indentone}
Assume \(\forall k\in\Nats.\&gt;(k&lt;n\IMPLIES P(k))\). \\
\vdots \\
\(P(n)\)
\end{indentone}
\end{indentone}
\(\forall n\in\Nats.\&gt;P(n)\) \quad strong induction
\end{document}
</pre></body></html>