CMSC-27100

Discrete Math

Winter Quarter, 2019

Home Lectures Policies

---

Piazza

Lecture 8: Induction, III

\( \newcommand{\set}[1]{\{#1\}} \newcommand{\comprehension}[2]{\{#1\,\vert\,#2\}} \newcommand{\size}[1]{\vert#1\vert} \newcommand{\true}{\top} \newcommand{\false}{\bot} \newcommand{\limplies}{\rightarrow} \newcommand{\divides}{\mathbin{\vert}} \newcommand{\mult}{\mathbin{\cdot}} \newcommand{\xor}{\oplus} \newcommand{\union}{\cup} \newcommand{\intersect}{\cap} \newcommand{\complement}[1]{\overline#1} \newcommand{\powerset}{\mathcal{P}} \newcommand{\ixUnion}{\bigcup} \newcommand{\ixIntersect}{\bigcap} \newcommand{\Div}{\mathrm{div}} \newcommand{\gcd}{\mathrm{gcd}} \newcommand{\divmod}{\mathop{\mathbf{divmod}}} \newcommand{\div}{\mathop{\mathbf{div}}} \newcommand{\mod}{\mathop{\mathbf{mod}}} \)

Let's begin by once again recalling the template for a proof by induction:

1. Statement: Begin with a precise statement of the formula to be proven, and the variable of induction.
2. The Basis Case: State the number $k$ where you're starting your induction, and the formula $\varphi(k)$ to be proven, and then prove it.
3. The Induction Case: State the inductive hypothesis $\varphi(n)$, and the formula $\varphi(n+1)$ to be proven. Prove the result, clearly indicating where the inductive hypothesis (often abbreviated IH) is used.

as well as the template for a proof by strong induction:

1. Statement: Begin with a precise statement of the formula to be proven, and the variable of induction.
2. The Induction Case: State the inductive hypothesis $\forall k \lt n,\, \varphi(k)$, and the formula $\varphi(n)$ to be proven. Prove the result, clearly indicating where the inductive hypothesis is used.

Tiling Problems

Tiling problems represent a kind of geometric problem, in which you're given an area to cover, and a number of different pieces with which to cover it. We're going to analyze some fairly simple tiling games today.

We'll start with the simple checkerboards:

and a blank domino tile large enough to cover exactly two squares:

It's easy to see that we can tile the 2x2 and 4x4 checkerboard:

How can we generalize this? Here's a first attempt:

Theorem 8.1 For all $n\geq 1$, the $2^n\times 2^n$ checkerboard can be tiled with dominos.

Proof Induction on $n$.

Basis Case $n=1$, we can tile the $2\times 2$ checkerboard. Note that we did so above.

Induction Case Our inductive hypothesis is that we can tile the $2^n\times 2^n$ checkerboard, and we have to prove that we can tile the $2^{n+1}\times 2^{n+1}$ checkerboard. But this is easy, because we can divide a $2^{n+1}\times 2^{n+1}$ checkerboard into four disjoint $2^n\times 2^n$ checkerboards, as we do here for the $n=2$ case:

And then use our inductive hypothesis to tile each of the $2^n\times 2^n$ checkerboards

And then merge the solutions of the $2^n\times 2^n$ checkerboard into a solution of the $2^{n+1}\times 2^{n+1}$ checkerboard:

$\Box$ Theorem 8.1

Thinking about a bit, we might wonder about checkerboards that aren't positive powers of $2$. In this, it's natural to consider to consider $2^0=1$. Pretty clearly, we can't tile a $1 \times 1$ checkerboard, as each tile takes up $2$ squares. And if our formula isn't right for the $n=0$ case, maybe we have the wrong formula.

Still, we can see that $n$ tiles will cover exactly $2n$ squares, and therefore the $1\times 1$ region is simply a special case of the fact that we can't tile regions with odd areas. Indeed, all of the odd-squares have odd areas, ruling out the possibility of tiling any of the $(2n+1) \times (2n+1)$ checkerboards.

This naturally leads us to consider $2n \times 2n$ checkerboards. Can we tile all of them? Pretty clearly, we can: we can sub-divide a $2n \times 2n$ checkerboard into an $n \times n$ checkerboard of $2\times 2$ checkerboards. We know how to tile the $2 \times 2$ pieces, and so can tile the whole, cf., the $n=3$ case:

Next, let's consider a slightly quirkier tile, a “corner piece”:

What can we do with it?

Theorem 8.4 For all $n$, we can tile the $2^n \times 2^n$ checkerboard, leaving a single, arbitrary, square uncovered.

Proof By induction on $n$.

Basis case $n=1$. Consider the $2\times 2$ checkerboard. By rotational symmetry, we can assume without loss of generality that the designated square not to be covered is at the upper right. We can now tile all the rest:

An even slicker base case comes from considering $n=0$, in which case we have the $1\times 1$ checkerboard. The only square to leave uncovered is the only square on the board, and so we don't need to place any times to produce the required tiling.

Inductive case. Assume we can produce the required tilings for the $2^n\times 2^n$ board. Consider a $2^{n+1} \times 2^{n+1}$ board, with a designated square. As before, we can consider this to be a $2\times 2$ board of $2^n \times 2^n$ boards. One of those four boards will have a missing square, and so can be tiled by our inductive hypothesis. For the other three boards, designate the inside corner as the square not to be tiled, and appeal to the inductive hypothesis to them. These inner three corner squares can be tiled by a corner tile, completing the proof.

Let's visualize this by considering an $8\times 8$ checkerboard, with an indicated square left uncovered

First, we decompose this into four $4\times 4$ checkerboards, designating the inside corners of the three sub-boards that don't contain the designated square

We then appeal to our inductive hypothesis for tilings of each of the sub-boards, leaving only the square designated in each uncovered

The four sub-boards are then combined

And the triangular hole in the center is filled, completing the required tiling.

$\Box$ Theorem 8.4

Round Robin Tournament

Recall, induction proofs are ultimately templates for arguing that there is no counter-example to a stated theorem. We can sometimes give a clean proof by assuming the existence of a least counter-example, and deriving a contradiction..

Definition 8.5 A round-robin tournament is a competition involving $n$ players, $p_1, p_2, \ldots, p_n$, in which every pair of players plays exactly one game. A cycle is a sequence of players $p_1',p_2', \ldots, p_k'$, such that each $p_i'$ beat $p_{i+1}'$, and $p_k'$ beats $p_1'$.

Theorem 8.6 Any tournament containing a cycle must contain a cycle of length $3$.

Proof Note that no cycle of length less than $3$ can exist, because there's only a single game between each pair of players. Assume we have a tournament with a cycle, and let $p_1, p_2, \ldots, p_k$ be the shortest cycle $C$. If $k=3$, we're done. Otherwise, we have at least $4$ members of the cycle, cf., the following, where an arrow from a node $a$ to node $b$ means that $a$ beat $b$.

Now, the critical observation is that $p_1$ and $p_3$ played, and one of them won.

Case I $p_1$ beat $p_3$. In this case, we can build a shorter cycle, cutting $p_2$ out of $C$, contradicting the minimality of $C$.

Case II $p_3$ beat $p_1$. In this case, we end up with a triangular cycle $p_1, p_2, p_3$, both establishing the required result, and contradicting the minimality of $C$.

$\Box$ Theorem 8.6

Recursive Definitions

It is common practice to define functions and sets via recursive definitions, i.e., definitions in which the set being defined is being used in the body of the definition. This might seem to be quite problematic, but in typical cases, it's easy to justify that the function or set is well defined. E.g., in a common case, we define a function $f: \mathbb{N} \to \mathbb{N}$ by defining $f(n)$ in terms of $f(k)$ for $k \lt n$. We can then appeal to strong induction to prove that the resulting function is well-defined, i.e., that it is total and single-valued.

Let's consider a celebrated example:

Definition 8.7 The Fibonacci numbers $f_n$ are defined recursively as follows:

\begin{equation*} f_n = \begin{cases} 0, &\text{if $n$ = 0}\\ 1, &\text{if $n$ = 1}\\ f_{n-1} + f_{n-2}, &\text{if $n > 1$} \end{cases} \end{equation*}

It is easy to see that this fits the pattern we described before, regarding defining a function based on its values on smaller arguments. In the case of $n=0$ and $n=1$, there is no dependency on other function values (and so the requirement that it depend only on the values of the function on smaller arguments is trivially satisfied), and in the $n>1$ case, the value of $f_n$ depends only on $f_{n-1}$ and $f_{n-2}$, i.e., smaller indexes/arguments.

Fibonacci numbers arise with some frequency in mathematics, so it's worth understanding them well. We might begin with a table of a few values:

$n$	$f_n$
$\phantom{0}0$	$\phantom{0}0$
$\phantom{0}1$	$\phantom{0}1$
$\phantom{0}2$	$\phantom{0}1$
$\phantom{0}3$	$\phantom{0}2$
$\phantom{0}4$	$\phantom{0}3$
$\phantom{0}5$	$\phantom{0}5$
$\phantom{0}6$	$\phantom{0}8$
$\phantom{0}7$	$13$
$\phantom{0}8$	$21$
$\phantom{0}9$	$34$
$10$	55

We might reflect for a moment on the calculation (valid for $n>1$)

\begin{align*} f_n &= f_{n-1} + f_{n-2}\\ f_n - f_{n-1} &= f_{n-2}\\ \nabla f_n &= f_{n-2} \end{align*}

Stated a bit differently, the rate of growth of $f$ is somehow related to the value of $f$, and in the land of calculus, this is indicative of exponential functions.

So we might guess that $f_n = x^n$ for some $x$, and calculate

\begin{align*} f_n &= f_{n-1} + f_{n-2}\\ x^n &= x^{n-1} + x^{n-2}\\ x^n - x^{n-1} + x^{n-2} &= 0\\ x^{n-2}(x^2 - x - 1) &= 0\\ \end{align*}

The roots of this equation are $0$ (if $n>2$), and $1 \pm \sqrt{5} \over 2$, via the quadratic equation.

The particular number $\phi = {1 \pm \sqrt{5} \over 2}$ is a familiar mathematical constant, the Golden Ratio, and we'll use $\overline{\phi}$ to denote $1-\sqrt{5}\over 2$.

So the functions $\phi^n$ and ${\overline\phi}^n$ satisfy the recurrence $f_n = f_{n-1} + f_{n-2}$. Unfortunately, neither satisfies the initial conditions that $f_0 = 0$ and $f_1 = 1$. But here's a cute observation. Suppose we have a function $g(n) = a \phi^n + b{\overline\phi}^n$, for some constants $a$ and $b$. We can easily see that $g$ must also be a solution of the recurrence, i.e.,

\begin{align*} g(n) &= a \phi^n + b {\overline\phi}^n\\ &= a (\phi^{n-1} + \phi^{n-2}) + b ({\overline\phi}^{n-1} + {\overline\phi}^{n-2})\\ &= (a \phi^{n-1} + b {\overline\phi}^{n-1}) + (a \phi^{n-2} + b {\overline\phi}^{n-2})\\ &= g(n-1) + g(n-2) \end{align*}

This gives us enough freedom to choose $a$ and $b$ to satisfy our initial conditions:

\begin{align*} 0 &= a \phi^0 + b {\overline\phi}^0\\ &= a + b \end{align*}

and

\begin{align*} 1 &= a \phi^1 + b{\overline\phi} ^ 1\\ &= a \phi + b {\overline\phi} \end{align*}

Solving the first equation gives us $b = -a$, and we can substitute this into the second equation gives us

\begin{align*} 1 &= a \phi - a {\overline\phi} \\ &= a (\phi - {\overline\phi}) \\ &= a \sqrt{5} \end{align*}

So... $$f_n = {\phi^n - {\overline\phi}^n \over \sqrt{5}}.$$ If we note that $\overline\phi \approx -0.6180$, we can see that the ${\overline\phi}^n$ term tends to $0$ (and quickly), so $f_n \approx \phi^n / \sqrt{5}$.

Here's a nice application of Fibonacci numbers:

Theorem 8.10 (Lamé's Theorem) Suppose $a_n > a_{n-1} > \cdots >a_1 > a_0 = 0$ is the sequence of numbers and remainders encountered in Eulid's algorithm. Then $a_i \geq f_i$ for all $i \leq n$.

Proof We prove this by induction on $n$.

Basis Cases By our hypotheses, $a_0 = f_0$, and $0 \lt a_1$, so $f_1 = 1 \leq a_1$, as required.

Induction Case Assume $a_{n-1} \geq f_{n-1}$ and $a_{n-2} \geq f_{n-2}$. We know that there exist $q$ such that $a_n = q \cdot a_{n-1} + a_{n-2}$, and that $a_{n-2} \lt a_{n-1}$. Thus $q$ must be at most $1$, whence,

\begin{align*} a_n &= q \cdot a_{n-1} + a_{n-2} \\ &\geq a_{n-1} + a_{n-2}\\ &\geq f_{n-1} + f_{n-2}\tag{By IH}\\ &= f_n \end{align*}

as required.

$\Box$ Theorem 8.10

Corollary 8.11 Let $a \gt b \geq 0$ be natural numbers such that the representation of $a$ requires $d$ decimal digits, and the calculation of $\gcd(a,b)$ via Eulclid's algorithm requires $k$ division/remainder steps. Then $k \leq 5\mult d$.

Rosen gives one proof, this sketches out a somewhat different proof, which makes the underlying idea clearer.

Proof (sketch) As the decimal representation of $a$ requires $d$ digits, $a \lt 10^d$. As the calculation of $\gcd(a,b)$ via Euclid's algorithm requires $k$ division remainder steps, $f_k \le a$. If we put this together, we have \begin{align*} f_k &\lt 10^d\\ \phi^k / \sqrt{5} &\le 10^d\\ k \log{\phi} - \log{5}/2 &\le d \log{10}\\ k &\le d \mult {\log{10}/\log{\phi}} - {\log{5}\over 2 \mult \log{\phi}}\\ k &\le 4.789 \mult d + 1.673 \end{align*}

For large $d$, we have $k \leq 5 d$ as required. For small $d$, we have only finitely many numbers to check, which is easily done via computation.

$\Box$ Corollary 8.11

---

© 2016–2019 Stuart A. Kurtz
Last modified: March 13, 2019