CSCE 222 Lecture 18

« previous | Monday, March 7, 2011 | next »

Review: Proof by Induction

Let n be a natural number. Show that P(n) is true: for every $2^n\times 2^n$ checkerboard with one square removed can be tiled using right "triominoes"

Basis Step

$P(1)$ is true, as a 2 × 2 checkerboard can be covered by a triomino.

Induction Step

uppose that $P(k)$ is true for some $k\ge 1$. Does this imply $P(k+1)$? A $2^{k+1}\times 2^{k+1}$ checkerboard implies that we have four sub-checkerboards of size $2^k\times 2^k$. If we remove one square from each checkerboard (three at the central "intersection"), we can cover that empty space with a triomino. Therefore, only one square remains that has not been covered.

Strong Induction

$\begin{array}{ll}\text{Basis Step:}& P(1)\\ \text{Induction Step:}& P(1)\wedge P(2)\wedge \dots \wedge P(k)\to P(k+1)\end{array}$

Example

An integer $n>1$ can be written as a product of primes.

Proof: Let $P(n)$ denote the predicate: "$n$ can be written as a product of primes."

Basis Step

$P(2)$ is true since $2=\prod _{k=1}^{1}2$

Inductive Hypothesis

Suppose that $P(j)$ is true for all $j$ in the range $2\le j\le k$.

Induction Step

(we need to show that $P(k+1)$ is true)

Case 1: $k+1$ is prime, then $k+1=\prod _{l=1}^1(k+1)$, so P(k+1) is true

Case 2: $k+1$ is not prime, say, $k+1=ab$ , where $a$ and $b$ are natural numbers (excluding 1). both of these numbers are less than or equal to $k$, so $P(a)$ and $P(b)$ are true. So $a$ and $b$ can both be written as a product of primes. Thus $k+1=ab$ can be written as a product of primes.

Difficult Example

Suppose a sequence is defined as the sum of the previous three elements, where the first three elements are $(1,2,3,\dots )$. Prove that $a_n\le 2^n$.

Basis Step

The claim is true for $n=0$: $(a_0=1)\le (2^0=1)$, $n=1$, and $n=2$

Induction Step

For any $k>2$, assume that $P(i)$ is true for all $i$ in the range $0\le i\le k$. (i.e. $a_i\le 2^i$)

$\begin{array}{rl}{a}_k& =a_{k-1}+a_{k-2}+a_{k-3}\\ & \le 2^{k-1}+2^{k-2}+2^{k-3}\\ & \le 2^{k-1}+2^{k-2}+2^{k-3}+\dots +2^1+2^0\\ & =2^k-12-1\\ & \le 2^k\end{array}$