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{\mathbb{Z}}}^{\mathbb{+}}$

Proof by structural induction.

1. $S\subseteq 3{\mathbb{\mathbb{Z}}}^{\mathbb{+}}$
2. $3{\mathbb{\mathbb{Z}}}^{\mathbb{+}}\subseteq S$

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

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

Hence $x+y=3k+3l=3(k+l)\in 3{\mathbb{\mathbb{Z}}}^{\mathbb{+}}$. THis proves the inductive step, and $S\subseteq 3{\mathbb{\mathbb{Z}}}^{\mathbb{+}}$ 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\ge 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{\mathbb{Z}}}^{\mathbb{+}}\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\ge 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,\dots ,T_n$ be $n$ disjoint rooted trees such that $n\ge 1$ with corresponding roots $r_1,\dots ,r_n$. Draw edges connecting another distinct root $r$ with each of the roots $r_1,\dots ,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\le n(T)\le 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\le 1\le 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{m}\mathrm{a}\mathrm{x}(h(T_1),h(T_2))+1$

Thus we have $2h(T_i)+1\le n(T_i)\le 2^{h(T_i)+1}-1$ for $i=1,2$

Adding the two formulae together gives

$\begin{array}{rl}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(\mathrm{m}\mathrm{a}\mathrm{x}(h(T_1),h(T_2))+1)\le n(T_1\cdot T_2)& \le 2\cdot 2^{\mathrm{m}\mathrm{a}\mathrm{x}(h(T_1),h(T_2))+1}-1\\ 2h(T_1\cdot T_2)+1\le n(T_1\cdot T_2)& \le 2^{h(T_1\cdot T_2)+1}-1\end{array}$

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)

end

Note: if $\mathrm{g}\mathrm{c}\mathrm{d}(a,b)=1$, then a and b are relatively prime.