【具体数学--读书笔记】1.1 The Power of Hanoi

这一节借助汉诺塔问题引入了"Reccurent Problems"。

(Reccurence, 在这里解释为“the solution to each problem depends on the solutions to smaller instances of the same problem”. 即由相同的规模更小的问题的到原问题的解)

Hanoi问题描述：

　　"given a tower of eight disks, initially stacked in decreasing size on peg A.

　　Our task: transfer the entire tower to tower C, moving only one disk at a time and never mobing a larger one onto a smaller.

　　Question: How many moves are necessary and sufficient to perform the task?"

作者按照如下步骤分析求出n层汉诺塔的最少移动次数的通项公式：

1. generalize：最初是法国数学家Edouard Lucas提出的8层汉诺塔玩具，后来Lucas又创造了一个64层汉诺塔的故事。这里我们把汉诺塔的层数泛化为n

2. introduce appropriate notation, name and conquer：引入记号Tn表示n层的汉诺塔问题的最少移动次数

3. look at small cases：易知T1=1, T2=3, T3 = 7

4. find and prove a reccurence relation：找到并证明递推关系

(1) find a sufficient solution: 找到一个充分（可行）的解；

　　具体地，将求解small cases的方法推广，把除最底层以外的前n-1层看成一个整体，得到一个可行的方案Tn-1 + 1 + Tn-1，由此可得Tn <= 2*Tn-1 + 1

(2) prove it necessary: 证明它的必要性；

　　具体地，分析移动过程，移动最底层盘子之前，至少已花费Tn-1步将前n-1层移至辅助桩；最底层盘子就位后，同样至少要花费Tn-1将前n-1层从辅助桩移到目标桩，由此可得Tn >= 2*Tn-1 + 1

(3) yeild recurrence relation:v由(1)(2)得到等式，加上对平凡(trivial)情况的约定，构成如下递推关系

　　T0 = 0　　

　　Tn = 2*Tn-1 + 1

注：递推关系给出的是"indirect, local information"，已知局部的一个值可以方便地求出邻近的值，好比链表

5. find and prove a closed form expression: 找到并证明通项式

(1) 方法一：列出small cases观察 -> 猜一个式子 -> 用数学归纳法(mathematical induction)验证

(2) 方法二：直接从递推式推导：

1) add 1 to both sides of the equations:把右侧化成和左侧类似的形式

　　 T0 + 1= 1

　　 Tn + 1= 2*Tn-1 + 2 = 2*(Tn-1 + 1)

2) let Un = Tn + 1, we have 引入另一个记号，换元

　　U0 = 1

　　Un = 2*Un

由此构造出等比数列Un, 首项为1，公比为2，所以通项Un = U0*2^n = 2^n

3) 带回T, 得到通项公式Tn = Un - 1 = 2^n - 1

作者说这本书主要关注讨论的就是类似第5步方法二的方法，通过推导，而不是“猜测+验证”的方式来由递推式得到通项式

"to explain how a person can solve recurrences without being clairvoyant."

巴特西