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 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 S \subseteq \mathbb{Z^+}} or 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 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. 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! = n \cdot (n-1)!} 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 \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. 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 f_0 = 0} , 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 f_1 = 1}

Recursive step. 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 f_n = f_{n-1} + f_{n-2}}

We want to show 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 \alpha^{n-2} < f_n < \alpha^n} 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 \ge 2} , 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 \alpha = \frac{1 + \sqrt{5}}{2}}

Proof by strong induction.

Basis step. 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 = 2,3} , we have:

• 2: 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 < 1 < \alpha^2} . True.
• 3: 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 \alpha < 2 < \alpha^3} . True.

Inductive step. For some 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 \ge 3} , we assume that all preceding values are true. Then by the recursive relation, we have

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 f_{k+1} = f_k + f_{k-1}}
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 \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.