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 $2h(T_{i})+1\leq n(T_{i})\leq 2^{h(T_{i})+1}-1$ for $i=1,2$

Adding the two formulae together gives

{\begin{aligned}2h(T_{1})+2h(T_{2})+2+1\leq n(T_{1})+n(T_{2})+1&\leq 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)\leq n(T_{1}\cdot T_{2})&\leq 2\cdot 2^{\mathrm {max} (h(T_{1}),\ h(T_{2}))+1}-1\\2h(T_{1}\cdot T_{2})+1\leq n(T_{1}\cdot T_{2})&\leq 2^{h(T_{1}\cdot T_{2})+1}-1\end{aligned}}

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. $n!=n\cdot (n-1)!$ for $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)