跳转至

Part 5 Induction and Recursion

约 342 个字 预计阅读时间 1 分钟

5.2 Strong Induction and Well-Ordering

Strong Induction: To prove a statement \(P(n)\) for all \(n\in \mathbb{Z}\), we need to complete the following steps:

  • Basis Step: Prove \(P(1)\) is true.
  • Inductive Step: Show that \([P(1) \land P(2) \land \cdots \land P(k)] \rightarrow P(k+1)\) is true for all \(k\geq 1\).

Strong Induction is sometimes called the Second Principle of Mathematical Induction.

Well-Ordering Property: Every nonempty set of nonnegative integers has a least element.

Generalized Definition: A set is well-ordered if every subset has a least element.

5.3 Recursive Definitions and Structural Induction

Recursive Definition: A recursive or inductive definition of a function consists of two steps.

  • Basis Step: Specify the value of the function at zero. (Specifies an initial collection of elements)
  • Recursive Step: Give a rule for finding its value at an integer from its values at smaller integers. (Gives the rules for forming new elements in the set from those already in the set)

Sometimes the recursive definition has an exclusion rule, which specifies that the set contains nothing other than those elements specified in the basis step and generated by applications of the rules in the recursive step.

Structural Induction: To prove a property of the elements of a recursively defined set, we use structural induction.

  • Basis Step: Show that the result holds for all elements specified in the basis step of the recursive definition.
  • Recursive Step: Show that if the statement is true for each of the elements used to construct new elements in the recursive step of the definition, the result holds for these new elements.

Generalized induction is used to prove results about sets other than the integers that have the well-ordering property.

5.4 Recursive Algorithms

Recursive Algorithms: An algorithm is called recursive if it solves a problem by reducing it to an instance of the same problem with smaller input.For the algorithm to terminate, the instance of the problem must eventually be reduced to some initial case for which the solution is known.