【具体数学 Concrete Mathematics】1.1 递归问题 讲义

【具体数学 Concrete Mathematics】1.1 递归问题 导入

本节(1.1、1.1.1-1.1.3)主要围绕《具体数学》第一章 递归问题（Recurrent Problems）讲义部分的三个问题展开，分别是汉诺塔、平面上的直线以及约瑟夫问题。下面简单介绍一下递归问题和数学归纳法，做一个简单的导入，具体的递归应用可以在三个例子（1.1.1-1.1.3）中获得更好的体现：

1. 递归问题：

递归问题的主要思想是将大的问题分解成小的问题，然后只要提供最小的问题的具体解决方案即可。这样实际上递归方案并没有给出原问题的具体解决方案，而是给了一个解决问题的步骤。
一个典型的例子是《线性代数》中计算行列式的值$D={\sum }_{j=1}^n{A}_{ij}$。这里就是将计算$n$维行列式$D$分解成$n$个$n-1$维行列式$A_{ij}$的计算。最后可以展开到$1$维行列式$|x|=x$。整个过程中直接计算的只有最小的问题模块——$1$维行列式，其他维度都是直接根据递归方案来计算的。
通过这个小例子我们也可以看到递归方案只有到最后一步才真正解决具体问题，此前我们都假设更小的问题答案已知，如$D={\sum }_{j=1}^n{A}_{ij}$中，我们假设$A_{ij}$都已知，但是其实$A_{ij}$的值还需要进一步递归直到$1$维行列式才能计算出具体值。
如果这个例子没能理解，请看下面三个具体的例子，然后再回来看这个小例子，相信读者会有新的理解。
，

2. 数学归纳法

数学归纳法是证明某个命题$P$对所有满足$n\ge n_0$的整数$n$都成立的一种方法。
首先我们在$n=n_0$时，证明$P(n_0)$成立，这一步称为基础（Basis）；
接着对于$n>n_0$，假设$n_0$到$n-1$之间（包含两端）的所有值都证明成立，即$P(n_0),\dots ,P_{(}n-1)$都被证明成立，在此基础上证明$P(n)$成立，这一步称为归纳（Induction）。
由此可以证得命题$P$对所有满足$n\ge n_0$的整数$n$都成立。
下面举两个例子：

例子1： 证明$P(n):1+2+\cdots +n=\frac{n(n+1)}{2}$对任意$n\ge 1$成立。
证明：
Basis： $P(1)=1=\frac{1+2}{2}$。
Induction：当$n>1$时，假设$P(n-1)$成立，则有$P(n-1)=1+2+\cdots +n-1=\frac{(n-1)n}{2}$。
那么$P(n)=1+2+\cdots +(n-1)+n=P(n-1)+n=\frac{(n-1)n}{2}+n=\frac{n(n+1)}{2}$。
由此原命题得证。

例子2（习题1）： 证明所有的马都是同样的颜色。
证明：假设有$n$匹马，下面证明$P(n):$$n$匹马都是同样的颜色对任意$n\ge 1$成立。
Basis：$P(1)$只有1匹马，显然其与自身有相同的颜色。
Induction：当$n>1$时，假设$P(n-1)$成立，则有任意$n-1$匹马都是相同的颜色。
那么根据归纳假设可知，$1\sim (n-1)$号马颜色相同，$2\sim n$号马颜色相同，而处于中间位置标号$2\sim (n-1)$的马在不同的马群中不可能改变颜色，因为这是马，不是变色龙。故而根据传递性可知，标号$1\sim n$的马颜色相同。
由此原命题得证。

例子2的证明其实是存在问题的，读者能发现吗？
这个证明绕开了2匹马的情况，因为根据归纳证明，当$n=2$时，$1$和$2$之间不存在任何中间标号的马匹，由此可知Induction在$n=2$时不成立。