神奇的数学归纳法

大部分数学都是让人昏昏欲睡，但是有一个点，其实很吸引人，那就是数学归纳法。因为它确实很神奇。

规则看上去很简单，功能却超乎常人想像：

1. 基础情况满足

2. 假设 n 成立，可推出 n+1 成立，则全体满足

如汉诺塔问题。从大到小堆叠的圆盘，保持大小顺序关系，在三个柱子中的a柱移动到另一个柱子。看上去好像可以，又好像很难，仔细琢磨还挺高难度的，因为实际完成的操作动作特别复杂。但是数学归纳法能够证明其可行性。

1. 一个圆盘时可以直接移动到另一个柱子

2. 分割成两部分，最后一个和之前的n个。假设 n 个是可以移动到另一个柱子，那么可以证明 n+1 是能做到的：

1. 首先将 n 移动到 abc编号的 b柱， a柱放着最后一个圆盘，因为基于假设，这一步是可以做到的

2. 将最后一个圆盘移到 c 柱

3. 将 b 柱剩余圆盘移到 c 柱，基于假设，n 是可以做到的，证明 n+1 完成。

因此，基于以上数学归纳法的技巧，就能证明汉诺塔确实可以移动。

为啥两个这么简单的条件，就能证明如此复杂的难题？数学归纳法为何能够成立？

基础条件简单且容易一眼看穿。

第二步的证明很有艺术性，因为它实际上是一个高度抽象，n 推导 n+1，这个 n 可以是集合的任何数，也就是实际证明了基础情况到某个 n 的过程是可以做到的，并且也证明了后续n+1...end 也是可以做到的。

也就是因为有这个推导结构，从而能证明整个空间都能满足这个性质。

具体过程：

1 : 1 0 0 -> 0 0 1

2 : 1 1 0 -> 0 1 1 -> 0 0 2

3 : 1 2 0 ->0  2 1 -> 0 0 3

4: 1 3 0 -> 0 3 1 -> 0 0 4

...

n: 1 f(n-1) 0 -> 0 f(n-1) 1 -> 0 0 n

...

不管上一步多么复杂，它最终也会回溯到f（1）这个最简单的情况。既然 f(1)可以完成，当前这一步永远可以基于上一步将 n 堆叠到 b，然后按步骤搬运即可。

当然上面的细节可能还需要补充，比如为什么可以永远形成这个局面，会不会发生干涉，还有交换柱子编号等等。这些就交给专业人士来证明了。