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

2.1 Definitions 数列·定义

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

Investigate! 探究！

What comes next:

接下来是什么：

$\begin{equation*} 1, ~11, ~21, ~1211, ~111221, ~312211, ~\ldots \end{equation*}$

A sequence is simply an ordered list of numbers. For example, here is a sequence: 0, 1, 2, 3, 4, 5, \ldots. This is different from the set $\N$ because, while the sequence is a complete list of every element in the set of natural numbers, in the sequence we very much care what order the numbers come in. For this reason, when we use variables to represent terms in a sequence they will look like this:

数列（sequence）不过是一列有序的数。例如，下面就是一个数列：0, 1, 2, 3, 4, 5, \ldots。它与集合 $\N$ 不同，因为虽然数列列出了自然数集里的每一个元素，但在数列中我们非常在意这些数出现的先后次序。正因如此，当我们用变量表示数列中的项时，会写成如下形式：

$\begin{equation*} a_0, a_1, a_2, a_3, \ldots \end{equation*}$

To refer to the entire sequence at once, we will write $a_n)_{n\in\N}$ or $a_n)_{n\ge 0}\text{,}$ or sometimes if we are being sloppy, just $a_n)$ (in which case we assume we start the sequence with $a_0$).

为了一次性指代整个数列，我们会写作 $a_n)_{n\in\N}$，或 $a_n)_{n\ge 0}\text{，}$有时图省事就只写 $a_n)$（这时我们默认数列从 $a_0$ 开始）。

We might replace the $a$ with another letter, and sometimes we omit $a_0\text{,}$ starting with $a_1\text{,}$ in which case we would use $a_n)_{n \ge 1}$ to refer to the sequence as a whole. The numbers in the subscripts are called indices (the plural of index).

我们也可以把 $a$ 换成别的字母；有时我们略去 $a_0\text{，}$而从 $a_1$ 开始，这时就用 $a_n)_{n \ge 1}$ 来指代整个数列。下标中的数字称为下标（index 的复数形式是 indices）。

While we often just think of sequences as an ordered list of numbers, they really are a type of function. Specifically, the sequence $a_n)_{n\ge 0}$ is a function with domain $\N$ where $a_n$ is the image of the natural number $n\text{.}$ Later we will manipulate sequences in much the same way you have manipulated functions in algebra or calculus. We can shift a sequence up or down, add two sequences, or ask for the rate of change of a sequence. These are done exactly as you would for functions.

虽然我们通常只把数列看作一列有序的数，但它其实是一种函数。确切地说，数列 $a_n)_{n\ge 0}$ 是一个定义域为 $\N$ 的函数，其中 $a_n$ 是自然数 $n$ 的像。之后我们会像在代数或微积分中处理函数那样去操作数列：可以把数列整体上移或下移、把两个数列相加，或者求数列的变化率。这些做法都与处理函数完全相同。

That said, while keeping the rigorous mathematical definition in mind is helpful, we often describe sequences by writing out the first few terms.

话虽如此，牢记这个严格的数学定义固然有用，但我们通常还是通过写出数列的前几项来描述它。

Example 1

示例 1

Can you find the next term in the following sequences?

你能求出下列数列的下一项吗？
  1. $7,7,7,7,7, \ldots$
  2. $3, -3, 3, -3, 3, \ldots$
  3. $1, 5, 2, 10, 3, 15, \ldots$
  4. $1, 2, 4, 8, 16, 32, \ldots$
  5. $1, 4, 9, 16, 25, 36, \ldots$
  6. $1, 2, 3, 5, 8, 13, 21, \ldots$
  7. $1, 3, 6, 10, 15, 21, \ldots$
  8. $2, 3, 5, 7, 11, 13, \ldots$
  9. $3, 2, 1, 0, -1, \ldots$
  10. $1, 1, 2, 6, \ldots$
  1. $7,7,7,7,7, \ldots$
  2. $3, -3, 3, -3, 3, \ldots$
  3. $1, 5, 2, 10, 3, 15, \ldots$
  4. $1, 2, 4, 8, 16, 32, \ldots$
  5. $1, 4, 9, 16, 25, 36, \ldots$
  6. $1, 2, 3, 5, 8, 13, 21, \ldots$
  7. $1, 3, 6, 10, 15, 21, \ldots$
  8. $2, 3, 5, 7, 11, 13, \ldots$
  9. $3, 2, 1, 0, -1, \ldots$
  10. $1, 1, 2, 6, \ldots$

Solution

解答

No you cannot. You might guess that the next terms are:

不，你做不到。你也许会猜下一项分别是：
  1. $7$
  2. $-3$
  3. $4$
  4. 64
  5. 49
  6. 34
  7. 28
  8. 17
  9. $-2$
  10. $24$
  1. $7$
  2. $-3$
  3. $4$
  4. 64
  5. 49
  6. 34
  7. 28
  8. 17
  9. $-2$
  10. $24$

In fact, those are the next terms of the sequences I had in mind when I made up the example, but there is no way to be sure they are correct.

事实上，这些正是我编这道题时心里所想的数列的下一项；但没有任何办法能保证它们一定正确。

Still, we will often do this. Given the first few terms of a sequence, we can ask what the pattern in the sequence suggests the next terms are.

尽管如此，我们仍会经常这样做。给定数列的前几项，我们便可以问：数列中呈现的规律暗示下一项是什么。

Given that no number of initial terms in a sequence is enough to say for certain which sequence we are dealing with, we need to find another way to specify a sequence. We consider two ways to do this:

既然无论给出多少项初始项，都不足以确定我们面对的是哪一个数列，我们就需要另寻一种规定数列的方式。我们考虑两种做法：

Closed Formula 闭式

A closed formula for a sequence $a_n)_{n\in\N}$ is a formula for $a_n$ using a fixed finite number of operations on $n\text{.}$ This is what you normally think of as a formula in $n\text{,}$ just like if you were defining a function in terms of $n$ (because that is exactly what you are doing).

数列 $a_n)_{n\in\N}$ 的闭式（closed formula），是指只用对 $n$ 的有限次固定运算来表达 $a_n$ 的公式。这正是你通常所理解的关于 $n$ 的公式，就像你用一个关于 $n$ 的表达式来定义函数一样（因为那本来就是你在做的事）。

Recursive Definition 递推定义

A recursive definition (sometimes called an inductive definition) for a sequence $a_n)_{n\in\N}$ consists of a recurrence relation: an equation relating a term of the sequence to previous terms (terms with smaller index) and an initial condition: a list of a few terms of the sequence (one less than the number of terms in the recurrence relation).

数列 $a_n)_{n\in\N}$ 的递推定义（recursive definition，有时也称归纳定义 inductive definition）由两部分组成：一个递推关系（recurrence relation），即把数列的某一项与它前面的项（下标更小的项）联系起来的方程；以及一个初值（initial condition），即数列最前面若干项的列表（其项数比递推关系中所涉及的项数少一）。

It is easier to understand what is going on here with an example:

借助一个例子更容易理解这里在讲什么：

Example 2

示例 2

Here are a few closed formulas for sequences:

下面是几个数列的闭式：

Note in each case, if you are given $n\text{,}$ you can calculate $a_n$ directly: just plug in $n\text{.}$ For example, to find $a_3$ in the second sequence, just compute $a_3 = \frac{3(3+1)}{2} = 6\text{.}$

注意，在每种情况下，只要给定 $n$，就能直接算出 $a_n$：只需把 $n$ 代入即可。例如，要在第二个数列中求 $a_3$，只需计算 $a_3 = \frac{3(3+1)}{2} = 6\text{。}$

Here are a few recursive definitions for sequences:

下面是几个数列的递推定义：

In these cases, if you are given $n\text{,}$ you cannot calculate $a_n$ directly, you first need to find $a_{n-1}$ (or $a_{n-1}$ and $a_{n-2}$). In the second sequence, to find $a_3$ you would take $2a_2\text{,}$ but to find $a_2 = 2a_1$ we would need to know $a_1 = 2a_0\text{.}$ We do know this, so we could trace back through these equations to find $a_1 = 54\text{,}$ $a_2 = 108$ and finally $a_3 = 216\text{.}$

在这些情况下，给定 $n$ 后无法直接计算 $a_n$，你必须先求出 $a_{n-1}$（或 $a_{n-1}$ 与 $a_{n-2}$）。以第二个数列为例，要求 $a_3$ 得先算 $2a_2\text{，}$而求 $a_2 = 2a_1$ 又得先知道 $a_1 = 2a_0\text{。}$这一点我们是知道的，因此可以顺着这些方程回溯，得到 $a_1 = 54\text{、}$ $a_2 = 108$，最终 $a_3 = 216\text{。}$

Investigate! 探究！

You have a large collection of $1\times 1$ squares and $1\times 2$ dominoes. You want to arrange these to make a $1 \times 15$ strip. How many ways can you do this?

你拥有大量 $1\times 1$ 的正方形和 $1\times 2$ 的多米诺骨牌。你想用它们拼出一条 $1 \times 15$ 的长条。共有多少种拼法？
  1. Start by collecting data. How many length $1\times 1$ strips can you make? How many $1\times 2$ strips? How many $1\times 3$ strips? And so on.
  2. How are the $1\times 3$ and $1 \times 4$ strips related to the $1\times 5$ strips?
  3. How many $1\times 15$ strips can you make?
  4. What if I asked you to find the number of $1\times 1000$ strips? Would the method you used to calculate the number fo $1 \times 15$ strips be helpful?
  1. 先收集数据。长度为 $1\times 1$ 的长条你能拼出几种？$1\times 2$ 的呢？$1\times 3$ 的呢？依此类推。
  2. $1\times 3$ 与 $1 \times 4$ 的长条，和 $1\times 5$ 的长条之间有什么关系？
  3. $1\times 15$ 的长条你能拼出几种？
  4. 如果我要你求 $1\times 1000$ 长条的拼法数呢？你用来计算 $1 \times 15$ 长条拼法数的方法，到时还有用吗？

You might wonder why we would bother with recursive definitions for sequences. After all, it is harder to find $a_n$ with a recursive definition than with a closed formula. This is true, but it is also harder to find a closed formula for a sequence than it is to find a recursive definition. So to find a useful closed formula, we might first find the recursive definition, then use that to find the closed formula.

你也许会问，何必费心用递推定义来描述数列。毕竟，用递推定义求 $a_n$ 比用闭式更麻烦。这话不假，但为数列寻找闭式，也比寻找递推定义更困难。所以，要得到一个好用的闭式，我们不妨先找递推定义，再借它由递推定义推出闭式。

This is not to say that recursive definitions aren't useful in finding $a_n\text{.}$ You can always calculate $a_n$ given a recursive definition, it might just take a while.

不过，这并不等于说递推定义在求 $a_n$ 时没有用处。只要给定递推定义，你总能算出 $a_n$，只是有时要花点时间罢了。

Example 3

示例 3

Find $a_6$ in the sequence defined by $a_n = 2a_{n-1} - a_{n-2}$ with $a_0 = 3$ and $a_1 = 4\text{.}$

在由 $a_n = 2a_{n-1} - a_{n-2}$、$a_0 = 3$、$a_1 = 4$ 定义的数列中，求 $a_6$。

Solution

解答

We know that $a_6 = 2a_5 - a_4\text{.}$ So to find $a_6$ we need to find $a_5$ and $a_4\text{.}$ Well

我们知道 $a_6 = 2a_5 - a_4\text{。}$ 所以要求 $a_6$，得先求 $a_5$ 和 $a_4$。那么

$\begin{equation*} a_5 = 2a_4 - a_3 \qquad \text{and} \qquad a_4 = 2a_3 - a_2, \end{equation*}$

so if we can only find $a_3$ and $a_2$ we would be set. Of course

也就是说，只要能求出 $a_3$ 和 $a_2$ 就万事大吉了。当然，

$\begin{equation*} a_3 = 2a_2 - a_1 \qquad \text{and} \qquad a_2 = 2a_1 - a_0, \end{equation*}$

so we only need to find $a_1$ and $a_0\text{.}$ But we are given these. Thus

所以我们只需要求 $a_1$ 和 $a_0$。而这两个已经给出了。于是

$$ \begin{align*} a_0 & = 3\\ a_1 & = 4\\ a_2 & = 2\cdot 4 - 3 = 5\\ a_3 & = 2\cdot 5 - 4 = 6\\ a_4 & = 2\cdot 6 - 5 = 7\\ a_5 & = 2\cdot 7 - 6 = 8\\ a_6 & = 2\cdot 8 - 7 = 9. \end{align*} $$

Note that now we can guess a closed formula for the $n$th term of the sequence: $a_n = n+3\text{.}$ To be sure this will always work, we could plug in this formula into the recurrence relation:

注意，现在我们可以猜出该数列第 $n$ 项的闭式：$a_n = n+3\text{。}$ 要确认它始终成立，可以把这个公式代入递推关系：

$$ \begin{align*} 2a_{n-1} - a_{n-2} & = 2((n-1) + 3) - ((n-2) + 3)\\ & = 2n + 4 - n - 1 \\ & = n + 3\\ & = a_n. \end{align*} $$

That is not quite enough though, since there can be multiple closed formulas that satisfy the same recurrence relation; we must also check that our closed formula agrees on the initial terms of the sequence. Since $a_0 = 0 + 3 = 3$ and $a_1 = 1+3 = 4$ are the correct initial conditions, we can now conclude we have the correct closed formula.

不过，这还不够。因为满足同一个递推关系的闭式可能不止一个，所以我们还必须验证：我们的闭式在数列的初值上与它一致。由于 $a_0 = 0 + 3 = 3$、$a_1 = 1+3 = 4$ 正是正确的初值，现在我们可以断定，我们得到的就是正确的闭式。

Finding closed formulas, or even recursive definitions, for sequences is not trivial. There is no one method for doing this. Just like in evaluating integrals or solving differential equations, it is useful to have a bag of tricks you can apply, but sometimes there is no easy answer.

为数列寻找闭式，甚至寻找递推定义，都不是轻而易举的事。这没有一成不变的方法。就像求积分或解微分方程一样，手边备一套技巧很有用，但有时就是没有简便的答案。

One useful method is to relate a given sequence to another sequence for which we already know the closed formula.

一个有用的办法，是把给定的数列与我们已知其闭式的另一个数列联系起来。

Example 4

示例 4

Use the formulas $T_n = \frac{n(n+1)}{2}$ and $a_n = 2^n$ to find closed formulas for the following sequences.

利用公式 $T_n = \frac{n(n+1)}{2}$ 与 $a_n = 2^n$，为下列数列求出闭式。
  1. $b_n\text{:}$ $1, 2, 4, 7, 11, 16, 22, \ldots \text{.}$
  2. $c_n\text{:}$ $3, 5, 9, 17, 33,\ldots \text{.}$
  3. $d_n\text{:}$ $0, 2, 6, 12, 20, 30, 42,\ldots \text{.}$
  4. $e_n\text{:}$ $3, 6, 10, 15, 21, 28, \ldots\text{.}$
  5. $f_n\text{:}$ $0, 1, 3, 7, 15, 31, \ldots \text{.}$
  6. $g_n)$ $3, 6, 12, 24, 48, \ldots \text{.}$
  7. $h_n\text{:}$ $6, 10, 18, 34, 66, \ldots \text{.}$
  8. $j_n\text{:}$ $15, 33, 57, 87, 123, \ldots\text{.}$
  1. $b_n\text{：}$ $1, 2, 4, 7, 11, 16, 22, \ldots \text{。}$
  2. $c_n\text{：}$ $3, 5, 9, 17, 33,\ldots \text{。}$
  3. $d_n\text{：}$ $0, 2, 6, 12, 20, 30, 42,\ldots \text{。}$
  4. $e_n\text{：}$ $3, 6, 10, 15, 21, 28, \ldots\text{。}$
  5. $f_n\text{：}$ $0, 1, 3, 7, 15, 31, \ldots \text{。}$
  6. $g_n)$ $3, 6, 12, 24, 48, \ldots \text{。}$
  7. $h_n\text{：}$ $6, 10, 18, 34, 66, \ldots \text{。}$
  8. $j_n\text{：}$ $15, 33, 57, 87, 123, \ldots\text{。}$

Solution

解答
  1. Before you say this is impossible, what we are asking for is simply to find a closed formula which agrees with all of the initial terms of the sequences. Of course there is no way to read into the mind of the person who wrote the numbers down, but we can at least do this.
  2. The first few terms of $(T_n)_{n\ge 0}$ are $0, 1, 3, 6, 10, 15, 21, \ldots$ (these are called the triangular numbers). The first few terms of $(a_n)_{n\ge 0}$ are $1, 2, 4, 8, 16, \ldots\text{.}$ Let's try to find formulas for the given sequences:
  3. $1, 2, 4, 7, 11, 16, 22, \ldots)\text{.}$ Note that if subtract 1 from each term, we get the sequence $(T_n)\text{.}$ So we have $b_n = T_n + 1\text{.}$ Therefore a closed formula is $b_n = \frac{n(n+1)}{2} + 1\text{.}$ A quick check of the first few $n$ confirms we have it right.
  4. $3, 5, 9, 17, 33, \ldots )\text{.}$ Each term in this sequence is one more than a power of 2, so we might guess the closed formula is $c_n = a_n+1 = 2^n + 1\text{.}$ If we try this though, we get $c_0 2^0 + 1 = 2$ and $c_1 = 2^1 + 1 = 3\text{.}$ We are off because the indices are shifted. What we really want is $c_n = a_{n+1}+1$ giving $c_n = 2^{n+1} + 1\text{.}$
  5. $(0, 2, 6, 12, 20, 30, 42,\ldots$. Notice that all these terms are even. What happens if we factor out a 2? We get $(T_n)\text{!}$ More precisely, we find that $d_n/2 = T_n\text{,}$ so this sequence has closed formula $d_n = n(n+1)\text{.}$
  6. $(3, 6, 10, 15, 21, 28, \ldots)\text{.}$ These are all triangular numbers. However, we are starting with 3 as our initial term instead of as our third term. So if we could plug in 2 instead of 0 into the formula for $T_n\text{,}$ we would be set. Therefore the closed formula is $e_n = \frac{(n+2)(n+3)}{2}$ (where $n+3$ came from $(n+2)+1$. Thinking about sequences as functions, we are doing a horizontal shift by 2: $e_n = T_{n+2}$ which would cause the graph to shift 2 units to the left.
  7. $(0, 1, 3, 7, 15, 31, \ldots )\text{.}$ Try adding 1 to each term and we get powers of 2. You might guess this because each term is a little more than twice the previous term (the powers of 2 are exactly twice the previous term). Closed formula: $f_n = 2^{n} - 1\text{.}$
  8. $(3, 6, 12, 24, 48, \ldots )\text{.}$ These numbers are also doubling each time, but are also all multiples of 3. Dividing each by 3 gives 1, 2, 4, 8, …. Aha. We get the closed formula $g_n = 3\cdot 2^{n}\text{.}$
  9. $(6, 10, 18, 34, 66, \ldots )\text{.}$ To get from one term to the next, we almost double each term. So maybe we can relate this back to $2^n\text{.}$ Yes, each term is 2 more than a power of 2. So we get $h_n = 2^{n+2} + 2$ (the $n+2$ is because the first term is 2 more than $2^2\text{,}$ not $2^0$. Alternatively, we could have related this sequence to the second sequence in this example: starting with 3, 5, 9, 17, … we see that this sequence is twice the terms from that sequence. That sequence had closed formula $c_n = 2^{n+1} + 1\text{.}$ Our sequence here would be twice this, so $h_n = 2(2^n + 1)\text{,}$ which is the same as we got before.
  10. $(15, 33, 57, 87, 123, \ldots)\text{.}$ Try dividing each term by 3. That gives the sequence $5, 11, 19, 29, 41,\ldots\text{.}$ Now add 1: $6, 12, 20, 30, 42, \ldots\text{,}$ which is $(d_n)$ in this example, except starting with 6 instead of 0. So let's start with the formula $d_n= n(n+1)\text{.}$ To start with the 6, we shift: $(n+2)(n+3)\text{.}$ But this is one too many, so subtract 1: $(n+2)(n+3) - 1\text{.}$ That gives us our sequence, but divided by 3. So we want $j_n = 3((n+2)(n+3) - 1)\text{.}$
  1. 先别急着说这不可能——我们要求的，无非是找一个与这些数列所有已知首项都吻合的闭式。当然，我们没法窥探写出这些数的人心里在想什么，但至少可以做到这一点。
  2. $(T_n)_{n\ge 0}$ 的前几项是 $0, 1, 3, 6, 10, 15, 21, \ldots$（它们被称为三角形数 triangular numbers）。$(a_n)_{n\ge 0}$ 的前几项是 $1, 2, 4, 8, 16, \ldots\text{。}$ 下面试着为给出的数列求出公式：
  3. $1, 2, 4, 7, 11, 16, 22, \ldots)\text{。}$ 注意，若把每一项都减 1，就得到数列 $(T_n)\text{。}$ 于是有 $b_n = T_n + 1\text{。}$ 因此一个闭式是 $b_n = \frac{n(n+1)}{2} + 1\text{。}$ 取前几个 $n$ 快速验算一下，可知答对了。
  4. $3, 5, 9, 17, 33, \ldots )\text{。}$ 这个数列每一项都比 2 的某个幂多 1，所以我们或许会猜闭式为 $c_n = a_n+1 = 2^n + 1\text{。}$ 但试一下会发现：$c_0 = 2^0 + 1 = 2$，$c_1 = 2^1 + 1 = 3\text{。}$ 对不上，因为下标发生了错位。我们真正想要的是 $c_n = a_{n+1}+1$，即 $c_n = 2^{n+1} + 1\text{。}$
  5. $(0, 2, 6, 12, 20, 30, 42,\ldots$。 注意这些项全是偶数。若提出因子 2 会怎样？会得到 $(T_n)\text{！}$ 更准确地说，我们发现 $d_n/2 = T_n\text{，}$ 所以这个数列的闭式是 $d_n = n(n+1)\text{。}$
  6. $(3, 6, 10, 15, 21, 28, \ldots)\text{。}$ 这些都是三角形数。不过，这里我们是把 3 作为首项，而不是第三项。所以，若能往 $T_n$ 的公式里代入 2 而非 0，就对了。因此闭式为 $e_n = \frac{(n+2)(n+3)}{2}$（其中 $n+3$ 来自 $(n+2)+1$）。把数列看作函数来看，这相当于一次水平平移 2 个单位：$e_n = T_{n+2}$，会使图像向左平移 2 个单位。
  7. $(0, 1, 3, 7, 15, 31, \ldots )\text{。}$ 试着给每一项加 1，就得到 2 的幂。你大概会这样猜，因为每一项都略微大于前一项的两倍（2 的幂恰好是前一倍的两倍）。闭式：$f_n = 2^{n} - 1\text{。}$
  8. $(3, 6, 12, 24, 48, \ldots )\text{。}$ 这些数同样每次翻倍，而且全是 3 的倍数。每项除以 3 得到 1, 2, 4, 8, …。啊哈。于是闭式为 $g_n = 3\cdot 2^{n}\text{。}$
  9. $(6, 10, 18, 34, 66, \ldots )\text{。}$ 从一项到下一代一项，几乎是每项翻倍。所以或许可以把它和 $2^n$ 联系起来。没错，每一项都比 2 的某个幂多 2。于是得到 $h_n = 2^{n+2} + 2$（这里的 $n+2$ 是因为首项比 $2^2$ 多 2，而不是比 $2^0$ 多 2）。换一种思路，也可以把这个数列和本例的第二个数列联系起来：从 3, 5, 9, 17, … 出发，可见本数列正是那个数列各项的两倍。那个数列的闭式是 $c_n = 2^{n+1} + 1\text{。}$ 本数列就是它的两倍，即 $h_n = 2(2^n + 1)\text{，}$ 与前面得到的相同。
  10. $(15, 33, 57, 87, 123, \ldots)\text{。}$ 试着把每项都除以 3，得到数列 $5, 11, 19, 29, 41,\ldots\text{。}$ 再加 1：$6, 12, 20, 30, 42, \ldots\text{，}$ 这正是本例中的 $(d_n)$，只不过是从 6 而不是从 0 开始。所以先取公式 $d_n= n(n+1)\text{。}$ 要让它从 6 开始，就平移：$(n+2)(n+3)\text{。}$ 但这多了一个，于是减 1：$(n+2)(n+3) - 1\text{。}$ 这样得到的是我们的数列再除以 3 的结果。所以我们想要的是 $j_n = 3((n+2)(n+3) - 1)\text{。}$