MATH 302 Lecture 14

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

Recursively Defined Sets

Basis step. $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 $x+y$ has the property $P$

This is an example of structural induction.

Strong Properties of S

Basis Step. Something has a certain property $P$

Inductive Step. Any element which can be obtained either by the basis step or up to $k$ iterations for some $k\geq 0$ of recursive step has property $P$ . Show any such element that can be obtained by $k+1$ iterations of recursive steps has property $P$ .

Trees

Basis step. A root $r$ is a tree

Inductive step. Let $T_{1},\ldots ,T_{n}$ be $n$ disjoint rooted trees such that $n\geq 1$ with corresponding roots $r_{1},\ldots ,r_{n}$ . Draw edges connecting another distinct root $r$ with each of the roots $r_{1},\ldots ,r_{n}$ . $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. $2h(T)+1\leq n(T)\leq 2^{h(T)+1}-1$ , where $n(T)$ is the number of vertices and $h(T)$ is the height.

Proof by Structural Induction.

Basis step. $T$ is a root alone: $h(T)=0$ , $n(T)=1$ . $1\leq 1\leq 1$ true.

Recursive step. Assume $T_{1}$ and $T_{2}$ are full binary trees satisfying the theorem

n(T_{1}\cdot T_{2})=n(T_{1})+n(T_{2})+1

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. $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)