Chapter.5 - Induction and Recursion¶

约 837 个字预计阅读时间 4 分钟

Section.1 Mathematical Induction¶

1.1 The Well-Ordering Property¶

Every nonempty set of nonnegative integers has a least element.
A set $S$ is said to be well-ordered if every nonempty subset of $S$ has a least element.

Why mathematical induction is valid?

Assume that there is at least one nonnegative integer $n$ for which $P(n)$ is false.

Let $S$ be the set of all nonnegative integers for which $P(n)$ is false.

Then $S$ is nonempty.

By the well-ordering property, $S$ has a least element, say $m$.

Since $P(0)$ is true, $m$ is positive, so $m - 1$ is a nonnegative integer.

Since $m - 1 < m$, $m - 1$ is not in $S$. So $P(m - 1)$ is true.

Since the implication $P(m - 1) \rightarrow P(m)$ is true, $P(m)$ must be true.

1.2 The first principle of mathematical induction¶

$(P(1) \wedge \forall k(P(k)\rightarrow P(k+1)))\rightarrow \forall n P(n) $
- Inductive base: Establish $P(1)$
- Inductive step: Prove that $P(k)\rightarrow P(k+1)$ for $k\geqslant 1$
- Conclusion: $P(n) \forall n \geqslant 1$

1.3 More general form¶

$\forall n[n \geqslant k \rightarrow P(n)] $
- Inductive base: Establish $P(k)$
- Inductive step: Prove that $P(n)\rightarrow P(n+1)$ for $n\geqslant k$
- Conclusion: $P(n) \forall n \geqslant k$

Section.2 Strong Induction and Well-Ordering¶

2.1 The second principle of mathematical induction (Strong Induction,Complete Induction)¶

$(P(n_0) \wedge \forall k(k\geqslant n_0 \wedge P(n_0) \wedge P(n_0+1) \wedge \cdots \wedge P(k)\rightarrow P(k+1)))\rightarrow \forall n(n\geqslant n_0 \rightarrow P(n)) $

Inductive base: Establish $P(n_0)$

Inductive step: Prove that $P(n_0) \wedge P(n_0+1) \wedge \cdots \wedge P(k)\rightarrow P(k+1)$ for $k\geqslant n_0$

Conclusion: $P(n) \forall n \geqslant n_0$

Some items in example:

polygon 多边形; side 边; vertex 顶点; diagonal 对角线; convex 凸的; concave 凹的; triangulation 三角剖分;

LEMMA 1: Every simple polygon with at least four sides has an interior diagonal.

Theorem 1: A simple polygon with $n$ sides, where $n$ is an integer with $n\geqslant 3$, can be triangulated into $n-2$ triangles.(Use Strong Induction to prove it)

In fact, mathematical induction, strong induction, and well-ordering are all equivalent principles.

Section.3 Recursive Definitions and Structural Induction¶

3.1 Recursive Definitions¶

In a recursive definition, a function or a set is defined in terms of itself.
Recursively defined functions, with the set of nonnegative integers as the domain:
- $f(0)$ is defined to be a particular number.
- $f(n)$ is defined in terms of $f(n-1)$, for all integers $n\geqslant 1$.
Recursively defined functions are well-defined.

Let $P(n)$ be the statement that "$f$ is well-defined at $n$".

P(0) is true, since $f(0)$ is defined to be a particular number.

For all integers $n\geqslant 1$, if $P(n-1)$ is true, since $f(n)$ is defined in terms of $f(n-1)$, then $P(n)$ is true.

3.2 The Complexity of Euclidean algorithm¶

LAME's theorem: The number of steps required by the Euclidean algorithm to compute the greatest common divisor of two positive integers $m$ and $n$, where $a\geqslant b$, is at most five times the number of digits in $b$.

Proof: Recall that when the Euclidean algorithm is applied to find $gcd(a,b)$, with $a\geqslant b$, this sequence of equations (where $a=r_0$ and $b=r_1$) is obtained:

$r_0 = r_1q_1 + r_2$ , $0\leqslant r_2 < r_1$

$r_1 = r_2q_2 + r_3$ , $0\leqslant r_3 < r_2$

$\cdots$

$r_{n-2} = r_{n-1}q_{n-1} + r_n$ , $0\leqslant r_n < r_{n-1}$

$r_{n-1} = r_nq_n$

So $r_n$ is $gcd(a,b)$. Beacuse $r_i>r_{i+1}$, so $q_{i+1}\geqslant 2$.

$r_n\geqslant 1 = f_2$

$r_{n-1}\geqslant 2r_n \geqslant 2f_2\geqslant f_3$

$r_{n-2}\geqslant r_{n-1}+r_n \geqslant f_2+f_3\geqslant f_4$

$\cdots$

$r_1\geqslant r_2+r_3 \geqslant f_{n-1}+f_n\geqslant f_{n+1}$

Hence, $b=r_1\geqslant f_{n+1}$.

Because $f_{n+1} > \frac{(1+\sqrt{5})}{2}\cdot f_n > [\frac{(1+\sqrt{5})}{2}]^{n-1}$ $\Rightarrow$ $\lg b > (n-1)\lg \frac{(1+\sqrt{5})}{2}> \frac{n-1}{5}$ $\Rightarrow$ $n<5\lg b + 1$.

Suppose that $b$ has $k$ digits, so $b < 10^k$, then $ \lg b < k$, so $n<5k + 1$.

So $n\leqslant 5k$.

Q.E.D.

So the complexity of Euclidean algorithm is $O(\log b)$.

3.3 Recursive Definitions of Sets¶

Sets can also be defined recursively:

Basis step: Specify an initial collection of elements.

Recursive step: Describe how new elements can be formed from the elements already known to be in the set.

Exclusion rule: the set contains nothing other than those elements specified in the basis step and generated by applications of the rules in the recursive step.（有且仅有初值和递归规则生成的元素）

The set of rooted trees, extended binary trees, full binary trees, and binary search trees can all be defined recursively.