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\geq 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}{\mbox{Basis Step:}}&P(1)\\{\mbox{Induction Step:}}&P(1)\wedge P(2)\wedge \ldots \wedge P(k)\rightarrow P(k+1)\\\hline &\therefore \forall nP(n)\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\leq j\leq 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,\ldots )$. Prove that $a_{n}\leq 2^{n}$.

Basis Step

The claim is true for $n=0$: $(a_{0}=1)\leq \left(2^{0}=1\right)$, $n=1$, and $n=2$

Induction Step

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

${\begin{aligned}a_{k}&=a_{k-1}+a_{k-2}+a_{k-3}\\&\leq 2^{k-1}+2^{k-2}+2^{k-3}\\&\leq 2^{k-1}+2^{k-2}+2^{k-3}+\ldots +2^{1}+2^{0}\\&={2^{k}-1}{2-1}\\&\leq 2^{k}\end{aligned}}$