MATH 302 Lecture 13

« previous | Wednesday, October 12, 2011 | next »

Strong Induction (cont'd)

"Once you see one you've seen them all."

Well-ordering Principle

Every non-empty subset $S\subseteq {\mathbb{\mathbb{Z}}}^{\mathbb{+}}$ or $S\subseteq \mathbb{\mathbb{N}}$ has a smallest element.

Division Algorithm

Take an integer $b$ and a positive integer $a$, then we have for some $q,r\in \mathbb{\mathbb{Z}}$ with $0\le r<a$, that $b=aq+r$

For example: $10=3(3)+1$

With these conditions, $q$ and $r$ are unique.

Given a set $S=\{b-at|t\in \mathbb{\mathbb{Z}}\text{ and }b-at\ge 0\}$, then

b	a	t	b − at
10	3	0	10
		1	7
		-1	13
		2	4
		3	1

We can show that

1. $S$ is non-empty
2. Let $r$ be the minimal element in $S$. Then $r=b-aq$ for $q\in \mathbb{\mathbb{Z}}$ and $0\le r<a$

Structural Induction and Recursion

Define $n!$ for $n\in {\mathbb{\mathbb{Z}}}^{\mathbb{+}}$ recursively and uniquely for all positive integers:

Basis step. $0!=1$

Recursive step. $n!=n\cdot (n-1)!$ for $n\ge 1$

Exercises

fa :: Integer -> Integer fa n

 | n < 0     = fail "n must be positive"
 | n == 0    = 1
 | otherwise = 3 * fa (n-1)

fb :: Integer -> Integer fb n

 | n < 0     = fail "n must be positive"
 | n == 0    = 1
 | otherwise = 3 * fb (n-1) + 2

fc :: Integer -> Integer fc n

 | n < 0     = fail "n must be positive"
 | n == 0    = 1
 | otherwise = 2^(fc (n-1))

Fibonacci Numbers

Basis step. $f_0=0$, and $f_1=1$

Recursive step. $f_n=f_{n-1}+f_{n-2}$

We want to show that ${\alpha }^{n-2}<f_n<{\alpha }^n$ for $n\ge 2$, where $\alpha =\frac{1+\sqrt{5}}{2}$

Proof by strong induction.

Basis step. for $n=2,3$, we have:

• 2: $1<1<{\alpha }^2$. True.
• 3: $\alpha <2<{\alpha }^3$. True.

Inductive step. For some $k\ge 3$, we assume that all preceding values are true. Then by the recursive relation, we have

$f_{k+1}=f_k+f_{k-1}$
${\alpha }^{k-2}\le f_k\le {\alpha }^k$

…

Thus the general result follows by the principle of strong mathematical induction.

Structural definition of sets

• Σ: alphabet (set of acceptable chars)
• Σ*: words in the alphabet

Basis step. The empty word: λ ∈ Σ*

Recursive step. if w ∈ Σ* and x ∈ Σ, then wx ∈ Σ*.

Definition of Concatenation

Basis step. For w ∈ Σ and λ ∈ Σ*, we have wλ = w

Recursive step. For w ∈ Σ, v ∈ Σ and x ∈ σ*, if wv is defined, then w(vx) = (wv)x.