连接我们将要去的地方和我们去过的地方的数学|广达杂志

假设您和其他九个人参加一个聚会，每个人都只与其他人握手一次。进行了多少次握手？

这就是“握手问题”，也是我最喜欢的问题之一。作为一名数学老师，我喜欢它，因为你可以通过多种不同的方式找到解决方案，而这些策略的多样性和相互关联性完美地说明了数学中创造性思维的力量。

一种解决方案是这样的：首先每个人都与其他人握手。十个人，每人握手 9 次，总共握手 10 × 90 = 90 次。但这会将每次握手计算两次（从每个摇动者的角度来看一次），因此实际握手次数为 $latex frac{2}{45} = XNUMX$。一个简单而可爱的获胜计数论点！

还有一种完全不同的方法来解决问题。想象一下，客人一次一位到达，当他们到达那里时，他们与在场的每个人握手。第一个人没有握手的机会，因此在一个人的聚会中，握手次数为零。现在第二个人到达并与第一个人握手。这使得握手总数增加了 0 次，因此在两人聚会中，握手总数为 1 + 1 = XNUMX 次。当第三个人到达并与前两位客人握手时，握手总数就增加了两次。第四个人的到来使握手次数增加了三次，以此类推。

该策略以递归方式对握手序列进行建模，这意味着序列中的每个术语都是相对于其之前的术语进行定义的。您可能熟悉斐波那契数列，这是最著名的递归数列。它从 1、1、2、3、5、8、13、21 开始，并继续，后续每一项都等于前两项之和。

正如我们将在下面看到的，递归是一个灵活而强大的框架，用于思考各种数学思想。尽管像 Hemachandra 这样的古印度学者早在 1150 年就已了解此类序列，但它们仍然为当今的数学家带来了有趣的挑战。

让我们看看递归思维如何帮助解决握手问题。如果我们让 $latex a_n$ 等于 a 处的握手次数 n-person party，我们可以用下面的公式来表示这种递归关系：

$乳胶a_n = a_{n-1} + n–1$

这告诉我们，一次握手的次数 n-person party ($latex a_n$) 等于在 (n − 1) 人聚会 ($latex a_{n-1}$) plus n - 多握手1次，体现了这样的想法：当新人到来时，他们会在已经发生的握手的基础上添加一定数量的新握手。

在我们特定版本的握手问题中，我们想知道$latex a_{10}$，10人聚会的握手次数，因此发现我们使用了递归关系

$乳胶a_{10} = a_9 + 9$

要找到 $latex a_{10}$ 的值，我们只需要知道 $latex a_9$ 的值并加 9 即可。我们如何找到 $latex a_9$ 的值？当然是通过使用递归！

$乳胶a_9 = a_8 + 8$

现在，要找到$latex a_8$的值，我们需要找到$latex a_7$的值，这需要知道$latex a_6$，依此类推。此时，您可能会担心这会以一种无限下降的方式永远持续下去，但是一旦我们到达 $latex a_1$ 我们就完成了，因为我们知道在一个人的聚会上握手总数为零。

$乳胶a_1 = 0$

这个初始值或“种子”值是递归序列的关键特征。它保证使用递归关系对序列进行回溯的过程将会结束。一旦达到种子值，回溯就会停止，然后您可以在列表中前进以获得您想要的值。

$乳胶a_1 = 0$

$乳胶a_2 = a_1 + 1 = 0 + 1 = 1$

$乳胶a_3 = a_2 + 2 = 1 + 2 = 3$

$乳胶a_4 = a_3 + 3 = 3 + 3 = 6$

$乳胶cdots$

$乳胶a_{10} = a_9 + 9 = 36 + 9 = 45$

通过查看该列表，我们发现 45 人聚会中总共有 10 次握手，这与我们最初的计算一致。如果您像我的学生一样，您可能会问，当我们已经知道答案时，为什么我们需要另一种方法来解决这个问题，特别是因为第二种方法似乎需要更长的时间。

这是一个好问题。一个答案是，递归方法让我们对这个问题的情况有了完全不同的看法，不同的观点在数学中很有用，就像在所有事情中一样。它们为我们提供了不同的机会来理解概念，并允许我们使用不同的工具，这可以在我们陷入困境时提供帮助。

特别是，递归非常有用，因为它在数学中无处不在。例如，它出现在每个人在数学课上学到的线性关系中——这些线性关系的特征是恒定的变化率，并用平面上的线表示。像 $latex f(x) = 3x + 5$ 这样的线性函数可以被认为是一个递归公式：

$乳胶a_0 = 5$

$乳胶a_n = a_{n-1} + 3$

虽然考虑 $latex f(2)$ 的更明显的方式可能是 $latex f(2) = 3 乘以 2 + 5 = 11$，但另一种方式是 $latex a_2 = a_1 + 3 = a_0 + 3 + 3 = 11 美元。对线性函数的基本特征（恒定变化率）进行递归建模为我们提供了另一种思考这种关系的方式。对于以恒定乘法变化为特征的指数函数也可以做到这一点。

递归思维也适用于数字序列之外的情况。如果您曾经求解过方程组，那么您可能已经应用过递归方法。解决系统

$乳胶 2x + y = 10$

$乳胶 3x – y = 5$

您可以先将两个方程相加以消除 y 变量，得出方程 $latex 5x = 15$。解决这个问题得到 $latex x =$ 3，代之以找到 $latex y = 4$，就完成了。这种方法利用递归算法，其中系统的解决方案是根据较小的相关系统的解决方案构建的。例如，要求解 3 × 3 系统，可以消除一个变量，将其转变为 2 × 2 系统，然后再次将其转变为 1 × 1 系统。这个易于求解的单个方程就像这个递归过程的种子值。它标志着回溯的结束，从这里开始，您将沿着方程链返回，就像递归序列一样。

甚至还有递归证明技术。例如，几何中一个著名的公式是多边形角和公式，它表示一个多边形的内角的测量值之和。 n边多边形是 $latex (n-2) 乘以 180^{circ}$。证明这个结果的一种方法是从 n-gon 并想象一下如果去掉一个三角形会发生什么。

去掉一个三角形就会变成 n-gon 变成 (n − 1)-gon，它还删除了 180 度的内角测量值。这是一个递归关系：一个内角和 n-gon 比 ( 的内角和大 180 度n − 1)-边形。要确定一般结果，请继续删除三角形，直到达到种子值，在这种情况下，当您删除了除三个之外的所有三角形时，就会发生这种情况 n-gon 的顶点。此时，初始多边形已简化为三角形，已知其内角和为 180 度。现在往回走，每一步加 180 度，你就会得到公式。

回到我们的聚会，握手问题本身向我们展示了当我们创造性地思考，然后将问题的多个不同观点联系在一起时，什么是可能的。如果我们使用递归模型来处理握手序列：

$乳胶a_1 = 0$

$乳胶a_n = a_{n-1} + n – 1$

一个很好的模式出现了：

$乳胶a_2 = a_1 + 1 = 0 + 1$

$乳胶a_3 = a_2 + 2 = 0 + 1 + 2$

$乳胶a_4 = a_3 + 3 = 0 + 1 + 2 + 3$

$乳胶cdots$

$乳胶a_n = a_{n-1} + (n-1) = 0 + 1 + 2 + 3 + cdots + (n-1)$

我们现在有了一种新的、通用的方式来思考这个问题：一个网络中的握手次数。 n-人一方等于第一人的总和 n − 1 个正整数。

回想一下我们最初的方法。在一个 n- 一人聚会，每个人都会与对方握手 n − 1 人。产品 $latex n (n-1)$ 将每次握手计数两次，因此握手总数为 $latex frac{n(n-1)}{2}$。但由于我们不同的方法计算相同的事物，因此它们必须产生相同的结果。特别是，这意味着：

$乳胶 1 + 2 + 3 + cdots + (n-1) = frac{n(n-1)}{2}$

通过连接握手问题的不同方法，我们得到第一个总和的封闭公式 n − 1 个正整数。但我们得到更多：表达式 $latex frac{n(n-1)}{2}$ 涉及一个分数，但因为它等于整数之和，所以它也必须是一个整数。这证明了数论的一个简单事实：对于每个整数 n, $latex frac{n(n-1)}{2}$ 是一个整数。

同样的论证继续为现代数学提供动力。举个例子，2000 年代初的研究人员 证明了一些令人惊讶的结果 关于被称为 Somos 序列的递归序列，通过表明它们也很重要。借助创造性联系的力量，数学家们通过了解自己曾经去过的地方，再次发现了自己可以去往的地方。

演习

1. 找到序列的封闭公式，递归定义为
$乳胶a_1 = 1$
$乳胶a_n = a_{n-1} + 2n – 1$

2. 在该列的末尾，表达式 $latex frac{n(n-1)}{2}$ 显示为整数，即使该表达式涉及分数，因为 $latex frac{n(n-1) )}{2}$ 是计算某项的结果。还有一个数论论证表明该表达式必须是整数。它是什么？

3. 求递归序列的前几项
$乳胶a_1 = 1$
$乳胶a_n = frac{1}{1+a_{n-1}}$

4. 求递归序列的前几项
$乳胶a_1 = 1$
$乳胶a_2 = 1$
$乳胶a_n = a_{n-1} – a_{n-2}$