← 学习库 Discrete Mathematics (Levin) · 中英对照 目录

2.3 Polynomial Fitting 多项式拟合

本页译自 LibreTexts · Discrete Mathematics (Levin) 第 2.3 章。公式经 MathJax 渲染，自定义宏已注入。

Investigate! 探究！

A standard $8 \times 8$ chessboard contains 64 squares. Actually, this is just the number of unit squares. How many squares of all sizes are there on a chessboard? Start with smaller boards: $1\times 1\text{,}$ $2 \times 2\text{,}$ $3\times 3\text{,}$ etc. Find a formula for the total number of squares in an $n\times n$ board.

一个标准的 $8 \times 8$ 棋盘共有 64 个方格。当然，这仅是单位方格的个数。一个棋盘上各种大小的正方形一共有多少个？先从较小的棋盘入手：$1\times 1\text{、}$ $2 \times 2\text{、}$ $3\times 3\text{、}$ 等等。试求 $n\times n$ 棋盘上正方形总数的公式。

So far we have seen methods for finding the closed formulas for arithmetic and geometric sequences. Since we know how to compute the sum of the first $n$ terms of arithmetic and geometric sequences, we can compute the closed formulas for sequences which have an arithmetic (or geometric) sequence of differences between terms. But what if we consider a sequence which is the sum of the first $n$ terms of a sequence which is itself the sum of an arithmetic sequence?

至此我们已学过求等差数列与等比数列闭式的方法。由于我们会计算等差与等比数列前 $n$ 项的和，也就能求出这样一类数列的闭式：其相邻项之差构成等差（或等比）数列。但如果我们考虑这样一个数列：它本身是另一个数列前 $n$ 项的和，而那个数列又是某个等差数列前 $n$ 项的和，又当如何？

Before we get too carried away, let's consider an example: How many squares (of all sizes) are there on a chessboard? A chessboard consists of $64$ squares, but we also want to consider squares of longer side length. Even though we are only considering an $8 \times 8$ board, there is already a lot to count. So instead, let us build a sequence: the first term will be the number of squares on a $1 \times 1$ board, the second term will be the number of squares on a $2 \times 2$ board, and so on. After a little thought, we arrive at the sequence

在走得太远之前，我们先看一个例子：一个棋盘上（各种大小的）正方形共有多少个？棋盘有 $64$ 个方格，但我们还想计入边长更长的正方形。即便只看 $8 \times 8$ 的棋盘，需要计数的也不少。因此，我们换个思路，构造一个数列：第一项是 $1 \times 1$ 棋盘上的正方形个数，第二项是 $2 \times 2$ 棋盘上的正方形个数，依此类推。稍加思考，便得到数列

$\begin{equation*} 1,5,14,30, 55,\ldots \end{equation*}$

This sequence is not arithmetic (or geometric for that matter), but perhaps its sequence of differences is. For differences we get

这个数列本身不是等差（严格说也不是等比）数列，但它的差分数列或许是的。我们来看相邻项的差：

$\begin{equation*} 4, 9, 16, 25, \ldots \end{equation*}$

Not a huge surprise: one way to count the number of squares in a $4 \times 4$ chessboard is to notice that there are $16$ squares with side length 1, 9 with side length 2, 4 with side length 3 and 1 with side length 4. So the original sequence is just the sum of squares. Now this sequence of differences is not arithmetic since its sequence of differences (the differences of the differences of the original sequence) is not constant. In fact, this sequence of second differences is

这并不意外：数 $4\times 4$ 棋盘上正方形个数的一种办法，是注意到边长为 1 的有 $16$ 个、边长为 2 的有 9 个、边长为 3 的有 4 个、边长为 4 的有 1 个。因此原数列其实就是平方数之和。而这个差分数列本身不是等差的，因为它的差分数列（即原数列的「差的差」）并非常数。事实上，这个二阶差分数列是

$\begin{equation*} 5, 7, 9, \ldots \end{equation*}$

which is an arithmetic sequence (with constant difference 2). Notice that our original sequence had third differences (that is, differences of differences of differences of the original) constant. We will call such a sequence $\Delta^3$-constant. The sequence $1, 4, 9, 16, \ldots$ has second differences constant, so it will be a $\Delta^2$-constant sequence. In general, we will say a sequence is a $\Delta^k$-constant sequence if the $k$th differences are constant.

这确实是一个等差数列（公差恒为 2）。注意，我们的原数列的三阶差分（即原数列的「差的差的差」）为常数。我们称这样的数列为 $\Delta^3$-常数列。数列 $1, 4, 9, 16, \ldots$ 的二阶差分为常数，因此它是一个 $\Delta^2$-常数列。一般地，若一数列的第 $k$ 阶差分为常数，我们就称它为 $\Delta^k$-常数列。

Example 1

示例 1

Which of the following sequences are $\Delta^k$-constant for some value of $k$?

下列数列中，哪些对某个 $k$ 是 $\Delta^k$-常数列？
  1. $2, 3, 7, 14, 24, 37,\ldots\text{.}$
  2. $1, 8, 27, 64, 125, 216, \ldots\text{.}$
  3. $1,2,4,8,16,64,128,\ldots.$
  1. $2, 3, 7, 14, 24, 37,\ldots\text{。}$
  2. $1, 8, 27, 64, 125, 216, \ldots\text{。}$
  3. $1,2,4,8,16,64,128,\ldots\text{。}$

Solution

解答
  1. This is the sequence from Example 2.2.6, in which we found a closed formula by recognizing the sequence as the sequence of partial sums of an arithmetic sequence. Indeed, the sequence of first differences is $1,4,7, 10, 13,\ldots\text{,}$ which itself has differences $3,3,3,3,\ldots\text{.}$ Thus $2, 3, 7, 14, 24, 37,\ldots$ is a $\Delta^2$-constant sequence.
  2. These are the perfect cubes. The sequence of first differences is $7, 19, 37, 61, 91, \ldots\text{;}$ the sequence of second differences is $12, 18, 24, 30,\ldots\text{;}$ the sequence of third differences is constant: $6,6,6,\ldots\text{.}$ Thus the perfect cubes are a $\Delta^3$-constant sequence.
  3. If we take first differences we get $1,2,4,8,16,\ldots\text{.}$ Wait, what? That's the sequence we started with. So taking second differences will give us the same sequence again. No matter how many times we repeat this we will always have the same sequence, which in particular means no finite number of differences will be constant. Thus this sequence is not $\Delta^k$-constant for any $k\text{.}$
  1. 这是示例 2.2.6 中的数列，当时我们通过把它看作某个等差数列的「部分和」数列而求出了它的闭式。确实，它的一阶差分数列为 $1,4,7, 10, 13,\ldots\text{，}$而这个差分数列本身的差分为 $3,3,3,3,\ldots\text{。}$ 因此 $2, 3, 7, 14, 24, 37,\ldots$ 是一个 $\Delta^2$-常数列。
  2. 这些是完全立方数。它的一阶差分数列为 $7, 19, 37, 61, 91, \ldots\text{；}$二阶差分数列为 $12, 18, 24, 30,\ldots\text{；}$三阶差分则为常数：$6,6,6,\ldots\text{。}$ 因此完全立方数构成 $\Delta^3$-常数列。
  3. 如果取一阶差分，得到 $1,2,4,8,16,\ldots\text{。}$等等，这不是我们最初的数列吗？于是取二阶差分又会得到同一数列。无论重复多少次，得到的始终是这个数列，这意味着不存在有限阶差分能成为常数。因此，对任意 $k\text{，}$该数列都不是 $\Delta^k$-常数列。

The $\Delta^0$-constant sequences are themselves constant, so a closed formula for them is easy to compute (it's just the constant). The $\Delta^1$-constant sequences are arithmetic and we have a method for finding closed formulas for them as well. Every $\Delta^2$-constant sequence is the sum of an arithmetic sequence so we can find formulas for these as well. But notice that the format of the closed formula for a $\Delta^2$-constant sequence is always quadratic. For example, the square numbers are $\Delta^2$-constant with closed formula $a_n= n^2\text{.}$ The triangular numbers (also $\Delta^2$-constant) have closed formula $a_n = \frac{n(n+1)}{2}\text{,}$ which when multiplied out gives you an $n^2$ term as well. It appears that every time we increase the complexity of the sequence, that is, increase the number of differences before we get constants, we also increase the degree of the polynomial used for the closed formula. We go from constant to linear to quadratic. The sequence of differences between terms tells us something about the rate of growth of the sequence. If a sequence is growing at a constant rate, then the formula for the sequence will be linear. If the sequence is growing at a rate which itself is growing at a constant rate, then the formula is quadratic. You have seen this elsewhere: if a function has a constant second derivative (rate of change) then the function must be quadratic.

$\Delta^0$-常数列本身就是常数数列，因此它们的闭式很容易算（就是那个常数）。$\Delta^1$-常数列是等差数列，我们也已有求其闭式的方法。每个 $\Delta^2$-常数列都是某个等差数列的部分和，因此同样可以求出公式。但要注意，$\Delta^2$-常数列的闭式总是二次的。例如，平方数数列是 $\Delta^2$-常数数列，其闭式为 $a_n= n^2\text{。}$三角形数（也是 $\Delta^2$-常数数列）的闭式为 $a_n = \frac{n(n+1)}{2}\text{，}$展开后也含 $n^2$ 项。由此可见，每当数列的复杂度提高——即需要更多阶差分才得到常数——闭式所用多项式的次数也随之提高：从常数到一次，再到二次。相邻项之差的数列反映了原数列的增长速率。若数列以恒定速率增长，其公式就是一次的；若数列以「本身也在恒定速率增长」的速率增长，公式就是二次的。你在别处也见过这一点：若一个函数的二阶导（变化率）为常数，该函数必为二次函数。

This works in general:

这在一般情形下也成立：

Finite Differences 有限差分

The closed formula for a sequence will be a degree $k$ polynomial if and only if the sequence is $\Delta^k$-constant (i.e., the $k$th sequence of differences is constant).

一个数列的闭式是 $k$ 次多项式，当且仅当该数列是 $\Delta^k$-常数列（即其第 $k$ 阶差分数列为常数）。

This tells us that the sequence of numbers of squares on a chessboard, $1, 5, 14, 30, 55, \ldots\text{,}$ which we saw to be $\Delta^3$-constant, will have a cubic (degree 3 polynomial) for its closed formula.

这说明，我们之前看到的棋盘正方形个数数列 $1, 5, 14, 30, 55, \ldots\text{，}$是一个 $\Delta^3$-常数列，因此它的闭式将是一个三次（3 次）多项式。

Now once we know what format the closed formula for a sequence will take, it is much easier to actually find the closed formula. In the case that the closed formula is a degree $k$ polynomial, we just need $k+1$ data points to “fit” the polynomial to the data.

一旦知道了数列闭式的形式，实际求出闭式就容易多了。当闭式是一个 $k$ 次多项式时，我们只需要 $k+1$ 个数据点，就能把多项式「拟合」到这些数据上。

Example 2

示例 2

Find a formula for the sequence $3, 7, 14, 24,\ldots\text{.}$ Assume $a_1 = 3\text{.}$

求数列 $3, 7, 14, 24,\ldots\text{。}$ 的公式。设 $a_1 = 3\text{。}$

Solution

解答

First, check to see if the formula has constant differences at some level. The sequence of first differences is $4, 7, 10, \ldots$ which is arithmetic, so the sequence of second differences is constant. The sequence is $\Delta^2$-constant, so the formula for $a_n$ will be a degree 2 polynomial. That is, we know that for some constants $a\text{,}$ $b\text{,}$ and $c\text{,}$

首先，检查该公式在某个阶数上是否具有常数差分。它的一阶差分数列为 $4, 7, 10, \ldots\text{，}$这是一个等差数列，因此二阶差分为常数。该数列是 $\Delta^2$-常数列，所以 $a_n$ 的公式将是一个 2 次多项式。也就是说，存在某些常数 $a\text{、}$ $b\text{、}$ $c\text{，}$使得

$\begin{equation*} a_n = an^2 + bn + c. \end{equation*}$

Now to find $a\text{,}$ $b\text{,}$ and $c\text{.}$ First, it would be nice to know what $a_0$ is, since plugging in $n = 0$ simplifies the above formula greatly. In this case, $a_0 = 2$ (work backwards from the sequence of constant differences). Thus

现在来求 $a\text{、}$ $b\text{、}$ $c\text{。}$ 最好先知道 $a_0$ 的值，因为代入 $n = 0$ 能极大简化上式。此处 $a_0 = 2$（由常数差分数列倒推得到）。于是

$\begin{equation*} a_0 = 2 = a\cdot 0^2 + b \cdot 0 + c, \end{equation*}$

so $c = 2\text{.}$ Now plug in $n =1$ and $n = 2\text{.}$ We get

故 $c = 2\text{。}$ 再代入 $n =1$ 与 $n = 2\text{。}$ 得到

$\begin{equation*} a_1 = 3 = a + b + 2 \end{equation*} \begin{equation*} a_2 = 7 = a4 + b 2 + 2. \end{equation*}$

At this point we have two (linear) equations and two unknowns, so we can solve the system for $a$ and $b$ (using substitution or elimination or even matrices). We find $a = \frac{3}{2}$ and $b = \frac{-1}{2}\text{,}$ so $a_n = \frac{3}{2} n^2 - \frac{1}{2}n + 2\text{.}$

至此我们有了两个（线性）方程与两个未知数，因此可以解出 $a$ 与 $b$（可用代入法、消元法，甚至矩阵法）。解得 $a = \frac{3}{2}$、 $b = \frac{-1}{2}\text{，}$故 $a_n = \frac{3}{2} n^2 - \frac{1}{2}n + 2\text{。}$

Example 3

示例 3

Find a closed formula for the number of squares on an $n \times n$ chessboard.

求 $n \times n$ 棋盘上正方形个数的闭式。

Solution

解答

We have seen that the sequence $1, 5, 14, 30, 55, \ldots$ is $\Delta^3$-constant, so we are looking for a degree 3 polynomial. That is,

我们已经看到数列 $1, 5, 14, 30, 55, \ldots$ 是 $\Delta^3$-常数列，因此我们要找的是一个 3 次多项式。即

$\begin{equation*} a_n = an^3 + bn^2 + cn + d. \end{equation*}$

We can find $d$ if we know what $a_0$ is. Working backwards from the third differences, we find $a_0 = 0$ (unsurprisingly, since there are no squares on a $0\times 0$ chessboard). Thus $d = 0\text{.}$ Now plug in $n = 1\text{,}$ $n =2\text{,}$ and $n =3\text{:}$

若知道 $a_0$ 的值，就能求出 $d$。由三阶差分倒推，得到 $a_0 = 0$（这毫不意外，因为 $0\times 0$ 的棋盘上没有正方形）。于是 $d = 0\text{。}$ 现在代入 $n = 1\text{、}$ $n =2\text{、}$ $n =3\text{：}$

$$\begin{align*} 1 = & a + b + c\\ 5 = & 8a + 4b + 2c\\ 14 = & 27a + 9b + 3c. \end{align*}$$

If we solve this system of equations we get $a = \frac{1}{3}\text{,}$ $b = \frac{1}{2}$ and $c = \frac{1}{6}\text{.}$ Therefore the number of squares on an $n \times n$ chessboard is $a_n = \frac{1}{3}n^3 + \frac{1}{2}n^2 + \frac{1}{6}n\text{.}$

解这个方程组，得到 $a = \frac{1}{3}\text{、}$ $b = \frac{1}{2}$、 $c = \frac{1}{6}\text{。}$ 因此 $n \times n$ 棋盘上正方形的个数为 $a_n = \frac{1}{3}n^3 + \frac{1}{2}n^2 + \frac{1}{6}n\text{。}$

Note: Since the squares-on-a-chessboard problem is really asking for the sum of squares, we now have a nice formula for $\d\sum_{k=1}^n k^2\text{.}$

注：棋盘正方形问题本质上是在求平方和，因此我们现在有了一个漂亮的公式来表示 $\d\sum_{k=1}^n k^2\text{。}$

Not all sequences will have polynomials as their closed formula. We can use the theory of finite differences to identify these.

并非所有数列的闭式都是多项式。我们可以借助有限差分的理論来识别这一点。

Example 4

示例 4

Determine whether the following sequences can be described by a polynomial, and if so, of what degree.

判断下列数列能否用多项式描述；若可以，是几次多项式。
  1. $1, 2, 4, 8, 16, \ldots$
  2. $0, 7, 50, 183, 484, 1055, \ldots$
  3. $1,1,2,3,5,8,13,\ldots$
  1. $1, 2, 4, 8, 16, \ldots$
  2. $0, 7, 50, 183, 484, 1055, \ldots$
  3. $1,1,2,3,5,8,13,\ldots$

Solution

解答
  1. As we saw in Example 2.3.1, this sequence is not $\Delta^k$-constant for any $k\text{.}$ Therefore the closed formula for the sequence is not a polynomial. In fact, we know the closed formula is $a_n = 2^n\text{,}$ which grows faster than any polynomial (so is not a polynomial).
  2. The sequence of first differences is $7, 43, 133, 301, 571,\ldots\text{.}$ The second differences are: $36, 90, 168, 270,\ldots\text{.}$ Third difference: $54, 78, 102,\ldots\text{.}$ Fourth differences: $24, 24, \ldots\text{.}$ As far as we can tell, this sequence of differences is constant so the sequence is $\Delta^4$-constant and as such the closed formula is a degree 4 polynomial.
  3. This is the Fibonacci sequence. The sequence of first differences is $0, 1, 1, 2, 3, 5, 8, \ldots\text{,}$ the second differences are $1, 0, 1, 1, 2, 3, 5\ldots\text{.}$ We notice that after the first few terms, we get the original sequence back. So there will never be constant differences, so the closed formula for the Fibonacci sequence is not a polynomial.
  1. 如示例 2.3.1 所见，该数列对任意 $k$ 都不是 $\Delta^k$-常数列。因此它的闭式不是多项式。事实上，我们已知其闭式为 $a_n = 2^n\text{，}$它比任何多项式增长都快（故不是多项式）。
  2. 它的一阶差分数列为 $7, 43, 133, 301, 571,\ldots\text{；}$二阶差分为：$36, 90, 168, 270,\ldots\text{；}$三阶差分为：$54, 78, 102,\ldots\text{；}$四阶差分为：$24, 24, \ldots\text{。}$ 就目前所见，这个差分数列为常数，因此该数列是 $\Delta^4$-常数列，其闭式是一个 4 次多项式。
  3. 这是斐波那契数列。它的一阶差分数列为 $0, 1, 1, 2, 3, 5, 8, \ldots\text{，}$二阶差分为 $1, 0, 1, 1, 2, 3, 5\ldots\text{。}$ 我们注意到，头几项之后，它又回到了原数列。因此永远不会出现常数差分，斐波那契数列的闭式不是多项式。