Induction

"induction"即归纳，我觉得它所描述的是一种推广。本文对它进行分析。

维基百科Mathematical induction

数学归纳法

Mathematical induction is a mathematical proof technique. It is essentially used to prove that a property P(n) holds for every natural number n, i.e. for n = 0, 1, 2, 3, and so on. Metaphors can be informally used to understand the concept of mathematical induction, such as the metaphor of falling dominoes（多米诺骨牌） or climbing a ladder（梯子）.

The method of induction requires two cases to be proved. The first case, called the base case (or, sometimes, the basis), proves that the property holds for the number 0. The second case, called the induction step, proves that if the property holds for one natural number n, then it holds for the next natural number n+1. These two steps establish the property P(n) for every natural number n=0,1,2,3...

The method can be extended to prove statements about more general well-founded structures, such as trees; this generalization, known as structural induction, is used in mathematical logic and computer science. Mathematical induction in this extended sense is closely related to recursion. Mathematical induction, in some form, is the foundation of all correctness proofs for computer programs.

对于软件工程师而言，碰到的更多的是 structural induction。

维基百科Structural induction

NOTE: 维基百科的这篇文章总结的非常好

Structural induction is a proof method that is used in mathematical logic (e.g., in the proof of Łoś' theorem), computer science, graph theory, and some other mathematical fields. It is a generalization of mathematical induction over natural numbers and can be further generalized to arbitrary Noetherian induction. Structural recursion is a recursion method bearing the same relationship to structural induction as ordinary recursion bears to ordinary mathematical induction.

NOTE: 最后一段话非常重要，它将表达的含义是：structural recursion 和 structural induction 的关系与recursion 和 mathematical induction 的关系 相同。

Structural induction is used to prove that some proposition P(x) holds for all x of some sort of recursively defined structure, such as formulas, lists, or trees. A well-founded partial order is defined on the structures ("subformula" for formulas, "sublist" for lists, and "subtree" for trees). The structural induction proof is a proof that the proposition holds for all the minimal structures and that if it holds for the immediate substructures of a certain structure S, then it must hold for S also. (Formally speaking, this then satisfies the premises of an axiom of well-founded induction, which asserts that these two conditions are sufficient for the proposition to hold for all x.)

A structurally recursive function uses the same idea to define a recursive function: "base cases" handle each minimal structure and a rule for recursion. Structural recursion is usually proved correct by structural induction; in particularly easy cases, the inductive step is often left out. The length and ++ functions in the example below are structurally recursive.

NOTE: 上面这段话描述了structurally recursive function的实现思路。

NOTE: 上面这段话也说明了recursion和induction之间的关系：recursion用于计算机实现，induction用于数学证明。

维基百科Transfinite induction

“transfinite induction”即“无限归纳”。