这是一个称为河内塔的精巧智力题。它由法国数学家爱德华·卢卡斯于1883年发明：
“
给定一个由8个圆盘组成的塔，这些圆盘按照大小递减的方式套在三根桩柱中的一根上。
我们的目的是要将整个塔移动到另一根桩柱上，每次只能移动一个圆盘，且较大的圆盘在移动过程中不能放置在较小的圆盘上面。
问要完成这项任务移动多少次才是必须且足够的？
”
卢卡斯给这个玩具赋予了一个罗曼蒂克的传说，说的是一个大得多的婆罗贺摩塔（Tower of Brahma），它由64个纯金的圆盘堆放在三座钻石做成的方尖塔上．他说，上帝一开始把这些金圆盘放到了第一座方尖塔上，并命令一组牧师按照上面的规则把它们移动到第三座方尖塔上。据说牧师们夜以继日地工作，当他们完成任务时，那座塔就将坍塌，世界也将毁灭。
这个智力题有解，只是并非显而易见，不过只要稍加思考（或者此前看见过这个问题）就能使我们确信的确如此。现在问题来了：我们能做到的最好的解法是什么？也就是说，要完成这项任务移动多少次才是必须且足够的？
解决这样问题的最好方法是对它稍加推广．婆罗贺摩塔有64个圆盘，河内塔有8个圆盘，让我们来考虑一下，如果有n个圆盘将会怎样？
这样推广的一个好处是，我们可以大大简化问题。事实上，先研究小的情形是大有裨益的。移动只有一两个圆盘的塔十分容易。再通过少量的尝试就能看出如何移动有3个圆盘的塔。
求解问题的下一步是引入适当的记号：命名并求解。我们称Tn是根据卢卡斯的规则将n个圆盘从一根桩柱移动到另一根桩柱所需要的最少移动次数．那么，T1显然是1，而T2=3。
考虑所有情形中最小的情形还可以轻松得到另一条信息，即显然有T0=0，因为一个有n=0个圆盘的塔根本无需做任何挪动！聪明的数学家们不会羞于考虑小问题，因为当极端情形（即便它们是平凡的情形）弄得明明白白时，一般的形式就容易理解了。
现在让我们改变一下视角，来考虑大的情形：怎样才能移动一个大的塔呢？移动3个圆盘的试验表明，获胜的思路是将上面两个圆盘移动到中间的桩柱上，然后移动第三个圆盘，接着再把其余两个放到它上面。这就为移动n个圆盘提供了一条线索：首先把n-1个小的圆盘移动到一个不同的桩柱上（需要Tn-1次移动），然后移动最大的圆盘（需要一次移动），最后再把那n -1个小的圆盘移回到最大圆盘的上面（这需要另外的Tn-1次移动）．这样，至多需要2Tn-1+1次移动就能移动n（n ＞ 0）个圆盘了：
这个公式用的是符号“≤”，而不是“ = ”，因为我们的构造仅仅证明了2Tn-1+1次移动就足够了，而没有证明2Tn-1+1次移动是必需的。智者或许能想到一条捷径。
还有更好的方法吗？实际上没有。我们迟早必须移动最大的那个圆盘．当我们这样做的时候，那n-1个小的圆盘必须已经在某根桩柱上，而这至少需要Tn-1次移动才能把它们放置到那儿。如果我们不太精明，则移动最大的圆盘可能会多于一次。但是在最后一次移动最大的那个圆盘之后，我们必须把那n-1个小的圆盘（它们必须仍然在同一根桩柱上）移回到最大圆盘的上面，这也需要Tn-1次移动．从而
把这两个不等式与n = 0时的平凡解结合在一起就得到
（注意，这些公式与已知的值T1= 1以及T2=3相一致．关于小的情形的经验不仅能帮助我们发现一般的公式，而且还提供了一种便利的核查方法，看看我们是否犯下愚蠢的错误。在以后涉及更为复杂的操作策略时，这样的核查尤为重要．）
像式（1.1）这样的一组等式称为递归式（recurrence，也称为递归关系或者递推关系）。它给出一个边界值，以及一个用前面的值给出一般值的方程。有时我们也把单独的一般性方程称为递归式，尽管从技术上来说它还需要一个边界值来补足。
我们可以用递归式对任何n计算Tn。然而，当n很大时，并没有人真愿意用递归式进行计算，因为太耗时了。递归式只给出了间接、局部的信息。得出递归式的解我们会很愉悦。这就是说，对于Tn ，我们希望给出一个既漂亮又简洁的“封闭形式”，它使我们可以对其进行快捷计算，即便对很大的n 亦然．有了一个封闭形式，我们才能真正理解Tn 究竟是什么．
那么怎样来求解一个递归式呢？一种方法是猜出正确的解，然后证明我们的猜想是正确的。猜测解的最好方法是（再次）研究小的情形。我们就这样连续计算T3= 2*3+1 = 7，T4=2*7 +1 = 15， T5= 2*15+1=31， T6=2*31+1=63。啊哈！这看起来肯定像是有
至少这对n≤6是成立的。
数学归纳法（mathematical induction）是证明某个命题对所有满足n≥n0 的整数n都成立的一般方法．首先我们在n取最小值n0时证明该命题，这一步骤称为基础（basis）；然后对n＞n0 ，假设该命题对n0与n-1之间（包含它们在内）的所有值都已经被证明，再证明该命题对n 成立，这一步骤称为归纳（induction）。这样一种证明方法仅用有限步就得到无限多个结果。
递归式可以用数学归纳法完美地确立起来．例如在我们的情形中，式（1.2）很容易由式（1.1）推出：其基础是显然的，因为T0=2º-1=0．而如果我们假设当n被n-1取代时式（1.2）成立，则对n＞ 0用归纳法就得出
从而式（1.2）对n 也成立。好的！我们对Tn 的探求就此成功结束。
牧师的任务自然还没有完成，他们仍在负责任地移动圆盘，而且还会继续一段时间，因为对n =64有2的64次方-1次移动（大约1.8*10的19次方次）。即便是按照每微秒移动一次这个不可能实现的速度，也需要5000多个世纪来移动婆罗贺摩塔。而卢卡斯的智力问题更切合实际，它需要2的8次方-1=255次移动，快手大概四分钟就能完成。
河内塔的递归式是在各种应用中出现的诸多问题的一个典范。在寻求像Tn 这样有意义的量的封闭形式的表达式时，我们经过了如下三个阶段。
(1) 研究小的情形．这有助于我们洞察该问题，而且对第二和第三阶段有所帮助。
(2) 对有意义的量求出数学表达式并给出证明。对河内塔，这就是递归式（1.1），它允许我们对任何n 计算Tn （假设我们有这样的意向）。
(3) 对数学表达式求出封闭形式并予以证明。对河内塔，这就是递归解（1.2）。
第三阶段是我们要由始至终集中探讨的。实际上，我们将频繁跳过第一和第二阶段，因为我们以给定一个数学表达式作为出发点。即便如此，我们仍然会深入到各个子问题中，寻求它们的解将会贯穿所有这三个阶段。
我们对于河内塔的分析引导出了正确的答案，然而它要求“归纳的跳跃”，依赖于我们对答案的幸运猜测。我们的一个主要目的就是说明不具备超人洞察力的人如何求解递归式。例如，我们将会看到，在递归式（1.1）中方程的两边加上1可以使其变得更简单
现在如果令Un=Tn+1 ，那么就有
不必是天才，就能发现这个递归式的解正是Un=2ⁿ，从而有Tn=2ⁿ-1。即便是一台计算机也能发现这个结论。
用一把比萨刀直直地切n刀，可以得到多少块比萨饼？或者说得更有学术味儿点：平面上n条直线所界定的区域的最大个数Ln是多少？这个问题于1826年被一位瑞士数学家斯坦纳首先解决。
我们再次从研究小的情形开始，记住，首先研究所有情形中之最小者。没有直线的平面有1个区域，有一条直线的平面有2个区域，有两条直线的平面有4个区域（每条直线都在两个方向无限延伸）：
我们一定会想到有Ln=2ⁿ，当然！增加一条新的直线直接使区域的个数加倍。遗憾的是，这是错误的．如果第n条直线能把每个已有区域分为两个，那么就能加倍。它肯定能把一个已有区域至多分成两个，这是因为每一个已有区域都是凸的（一条直线可以把一个凸区域分成至多两个新区域，这些新的区域也将是凸的）．但是当增加第三条直线（图中的那条粗线）时，我们很快就会发现，不论怎样放置前面两条直线，它只能至多分裂3个已有的区域：
从而L₃=4+3=7是我们能做到的最好结果。
略加思考之后，我们给出适当的推广。第n（n ＞ 0）条直线使得区域的个数增加k 个，当且仅当它对k 个已有区域进行了分裂；而它对k 个已有区域进行分裂，当且仅当它在k-1个不同的地方与前面那些直线相交。两条直线至多相交于一点，因而这条新的直线与那n - 1条已有直线至多相交于n - 1个不同的点，故必定有k≤n 。我们就证明了上界
此外，用归纳法容易证明这个公式中的等号可以达到。我们径直这样来放置第n 条直线，使得它不与其他直线中的任何一条平行（从而它与它们全都相交），且它不经过任何已经存在的交点（从而它与它们全都在不同的点相交）。于是该递归式即为
核查一下就发现，已知的L₁、L₂和L₃的值在这里完全正确，所以我们接受这一结果。
现在需要一个封闭形式的解。我们可以再次来玩猜测游戏，但是1,2,4,7,11,16,…看起来并不熟悉，故而我们另辟蹊径。我们常常可以通过将它从头到尾一直“展开”或者“解开”来弄清楚递归式，如下：
换句话说，Ln比前n个正整数的和Sn大1。
量Sn不时地冒出来，故而值得对较小的值做出一张表。这样，我们下次看到它们时，或许会更容易辨认出这些数：
这些值也称三角形数，因为Sn是一个有n行的三角形阵列中保龄球瓶的个数。例如，通常的四行阵列
有S4=10个瓶子。
为计算Sn，我们可以利用据说是高斯在1786年就想出来的一个技巧，那时他只有9岁（阿基米德也曾在他关于螺旋线的经典著作的命题10和命题11中用到过）：
只要把Sn和它的反向书写相加，就能使得右边n列的每一列中的诸数之和都等于n+1．简化即得
好的，我们就有解答
作为专家，我们或许很满意于这个推导，并认为它是一个证明，尽管在做展开和合并时我们付出了一点点努力。但是学数学的学生应该能够适应更严格的标准，故而最好用归纳法构造出一个严格的证明。归纳法的关键步骤是
现在对于封闭形式（1.6）就不再有疑问了。
我们谈到了“封闭形式”而没有具体说明它的含义。通常，它的含义是极其明晰的像（1.1）和（1.4）这样的递归式不是封闭形式的，它们用其自身来表示一个量；但是像（1.2）和（1.6）这样的解是封闭形式的。像1+2+......+n 这样的和不是封闭形式——它们用“…”企图蒙混过关，然而像n（n+1）/2这样的表达式则是封闭形式的。我们可以给出一个粗略的定义：如果可以利用至多固定次数（其次数与n无关）的“人人熟知的”标准运算来计算量f (n)的表达式，那么这个表达式是封闭形式的。例如，2ⁿ -1和n（n+1）/2都是封闭形式，因为它们仅仅显式地包含了加法、减法、乘法、除法和幂指运算。
简单封闭形式的总数是有限的，且存在没有简单封闭形式的递归式。当这样的递归式显现出重要性时（由于它们反复出现），我们就把新的运算添加到整套运算之中，这可以大大扩展用“简单的”封闭形式求解的问题的范围。例如，前n个整数的乘积n!已经被证明是如此重要，故而现在我们都把它视为一种基本运算。于是公式n!就是封闭形式，尽管与它等价的1* 2*......* n并非是封闭形式。
现在，我们简要谈谈平面上直线问题的一个变形：假设我们用折线代替直线，每一条折线包含一个“锯齿”。平面上由n条这样折线所界定的区域的最大个数Zn是多少？我们或许期待Zn大约是Ln的两倍，或者也可能是它的三倍．我们看到：
从这些小的情形出发并稍加思考，我们意识到，除了这“两条”直线不经过它们的交点延伸出去而使得区域相融合之外，一条折线与两条直线相似：
区域2、3和4对于两条直线来说它们是不同的区域，但在一条折线的情形下是单独的一个区域，于是我们失掉了两个区域．然而，如果放置得当——锯齿点必须放在它与其他直线的交点“之外”——那就是我们失去的全部，也就是说，对每条折线我们仅仅损失两个区域．从而
比较封闭形式（1.6）和（1.7），我们发现对于大的n 有
所以用折线所能得到的区域是用直线所能得到的区域的大约四倍。
——
是不是不知不觉看完了？这样学数学是不是很有效率，以后再也不会看见数学公式就头疼了。
——本文内容节选自《具体数学：计算机科学基础》
下面把这本书分享给大家，由当今顶级数学家和计算机科学家联合著作。
书中主要讲解了计算机科学中用到的数学知识及技巧，教人如何把实际问题一步步演化为数学模型，然后通过计算机解决它，特别着墨于算法分析方面。
本书成形于斯坦福大学的同名课程讲义，该课自1970年以来每年都会开设。每年大约有50名学生选学这门课，有本科生，主要是研究生。
具体数学究竟是什么呢？我们在书中能获得什么？
它融合了连续数学和离散数学。更具体地说，它是利用一组求解问题的技术对数学公式进行有控制的操作。理解了本书的内容之后，你所需要的就是一颗冷静的头脑、一大张纸以及较为工整的书写，以便对看上去令人恐怖的和式进行计算，求解复杂的递归关系，以及发现数据中隐藏的精妙规律。你会对代数技巧得心应手，从而常常会发现，得到精确的结果比求出仅在一定意义下成立的近似解更为容易。
具体数学的英文Concrete取自连续（CONtinuous）和离散（disCRETE）两个单词，具体数学是通向抽象数学的桥梁
这本书要探讨的主题包括和式、递归式、初等数论、二项式系数、生成函数、离散概率以及渐近方法。其重点是强调处理技术，而不是存在性定理或者组合推理，目的是使每一位读者熟悉离散性运算（如最大整数函数以及有限求和），就好像每一位学习微积分的学生都熟悉连续性运算一样（如绝对值函数以及不定积分）。
“略过看似基础内容的高水平读者，比略过看似复杂内容的较低水平读者，可能错失更多的东西。”——G. 波利亚[297]
注意，这些主题与当今大学本科中的“离散数学”课程的内容截然不同。因此，这门课程需要一个不同的名称，而“具体数学”可谓恰如其分。
这本书还包含了500多道习题，分成如下六大类。
书的最后，附录A中给出了所有习题的答案，常常还附有相关的解题思路。附录C中，作者还尝试说明每道习题的出处，因为一个富有教益的问题常常融会了大量的创造性思想或者运气。很遗憾，数学家们有个不好的传统：借用了习题，而不表示感谢。我们相信，相反的做法，例如棋类书籍和杂志中的做法（通常都会指出最初棋类问题的名字、时间和地点），要远胜于此。
联系客服
