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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} are natural numbers (excluding 1). both of these numbers are less than or equal to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} , so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(a)} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(b)} are true. So Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} can both be written as a product of primes. Thus Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1,2,3,\ldots)} . Prove that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_n \le 2^n} .

Basis Step

The claim is true for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=0} : Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (a_0=1) \le \left(2^0 = 1\right)} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=1} , and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=2}

Induction Step

For any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k>2} , assume that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(i)} is true for all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} in the range Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \le i \le k} . (i.e. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_i \le 2^i} )

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} 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}+\ldots+2^1+2^0 \\ & = {2^k-1}{2-1} \\ & \le 2^k \end{align}}