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 {Z^{+}}$ or $S\subseteq \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 {Z}$ with $0\leq r<a$, that $b=aq+r$

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

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

Given a set $S=\left\{b-at~|~t\in \mathbb {Z} {\mbox{ and }}b-at\geq 0\right\}$, 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 {Z}$ and $0\leq r<a$

Structural Induction and Recursion

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

Basis step. $0!=1$

Recursive step. $n!=n\cdot (n-1)!$ for $n\geq 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\geq 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\geq 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}\leq f_{k}\leq \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.