MATH 302 Lecture 14

« previous | Monday, October 17, 2011 | next »

Recursively Defined Sets

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 3 \in S}

Inductive step. if $x,y\in S$ , then $x+y\in S$ .

Example property: $S=3\mathbb {Z^{+}}$

Proof by structural induction.

$S\subseteq 3\mathbb {Z^{+}}$
$3\mathbb {Z^{+}} \subseteq S$

(1) Basis step. $3=3\cdot 1\in 3Z^{+}$

Inductive step. Assume $x,y\in 3\mathbb {Z^{+}}$ for $x,y\in S$ . Then $x=3k$ and $y=3l$ for some $k,l\in \mathbb {Z^{+}}$ .

Hence $x+y=3k+3l=3(k+l)\in 3\mathbb {Z^{+}}$ . THis proves the inductive step, and $S\subseteq 3\mathbb {Z^{+}}$ followl by structural principle of mathematical induction.

(2) Basis step. $3\cdot 1=3\in S$ by definition of $S$

Inductive step. Assume $3k\in S$ for $k\geq 1$ , then $3(k+1)=3k+3\in S$ by recursive step definition of $S$ . This proves the inductive step and thus the general result $3\mathbb {Z^{+}} \subseteq S$ follows by the principle of mathematical induction.

Properties of S

Basis step. 3 has a property $P$

Recursive step. If $x,y$ have the property $P$ , then 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 x + y} has the property 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}

This is an example of structural induction.

Strong Properties of S

Basis Step. Something has a certain property 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}

Inductive Step. Any element which can be obtained either by the basis step or up 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} iterations 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 0} of recursive step has property 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} . Show any such element that can be obtained by 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} iterations of recursive steps has property 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} .

Trees

Basis step. A root 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 r} is a tree

Inductive step. Let 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 T_1,\ldots,T_n} be 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} disjoint rooted trees such 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 n\ge 1} with corresponding roots 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 r_1,\ldots,r_n} . Draw edges connecting another distinct root 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 r} with each of the roots 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 r_1,\ldots,r_n} . 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 T} , the resulting graph, is a rooted tree.

Example Structural Proof

This proof is for full binary trees in which each node is a leaf or has exactly two children.

Theorem. 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 2h(T) + 1 \le n(T) \le 2^{h(T)+1}-1} , 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 n(T)} is the number of vertices 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 h(T)} is the height.

Proof by Structural Induction.

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 T} is a root alone: 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 h(T) = 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 n(T) = 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 1 \le 1 \le 1} true.

Recursive step. Assume 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 T_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 T_2} are full binary trees satisfying the theorem

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(T_1 \cdot T_2) = n(T_1) + n(T_2) + 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 h(T_1 \cdot T_2) = \mathrm{max}(h(T_1),\ h(T_2)) + 1}

Thus 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 2h(T_i) + 1 \le n(T_i) \le 2^{h(T_i)+1}-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 i=1,2}

Adding the two formulae together gives

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} 2h(T_1)+2h(T_2) + 2+1 \le n(T_1)+n(T_2) + 1 & \le 2^{h(T_1)+1}-1 + 2^{h(T_2) + 1} - 1 + 1 \\ 2\left( \mathrm{max}(h(T_1),\ h(T_2)) + 1 \right) \le n(T_1 \cdot T_2) & \le 2\cdot 2^{\mathrm{max}(h(T_1),\ h(T_2))+1}-1 \\ 2 h(T_1 \cdot T_2) +1 \le n(T_1 \cdot T_2) & \le 2^{h(T_1 \cdot T_2) + 1}-1 \end{align}}

This proves the inductive step, and the general result follows by the structural principle of mathematical induction.

Q.E.D.

And now for something completely different.

Recursive Algorithms

Solving a problem by reducing it to the same problem with a smaller input.

Simple definition for Factorial

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 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 > 0}

def factorial n

 raise Exception.new("must be nonnegative") if n < 0
 return 1 if n == 0
 n * factorial(n-1)

end

Greatest Common Divisor

def gcd a, b

 return b if a == 0
 gcd(b % a, a)