2.4 Solving Recurrence Relations 求解递推关系

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

Investigate! 探究！

Consider the recurrence relation

考虑如下递推关系

\begin{equation*} a_n = 5a_{n-1} - 6a_{n-2}. \end{equation*}

What sequence do you get if the initial conditions are $a_0 = 1\text{,}$ $a_1 = 2\text{?}$ Give a closed formula for this sequence.
What sequence do you get if the initial conditions are $a_0 = 1\text{,}$ $a_1 = 3\text{?}$ Give a closed formula.
What if $a_0 = 2$ and $a_1 = 5\text{?}$ Find a closed formula.

若初值条件为 $a_0 = 1\text{,}$ $a_1 = 2\text{?}$，你会得到怎样的数列？请给出该数列的闭式。
若初值条件为 $a_0 = 1\text{,}$ $a_1 = 3\text{?}$，你会得到怎样的数列？请给出闭式。
若 $a_0 = 2$ 且 $a_1 = 5\text{?}$，求闭式。

We have seen that it is often easier to find recursive definitions than closed formulas. Lucky for us, there are a few techniques for converting recursive definitions to closed formulas. Doing so is called solving a recurrence relation. Recall that the recurrence relation is a recursive definition without the initial conditions. For example, the recurrence relation for the Fibonacci sequence is $F_n = F_{n-1} + F_{n-2}\text{.}$ (This, together with the initial conditions $F_0 = 0$ and $F_1 = 1$ give the entire recursive definition for the sequence.)

我们此前已经看到，寻找递归定义往往比寻找闭式容易。所幸，有几种技巧可以把递归定义转换成闭式。这一过程称为求解递推关系。注意，递推关系是不带初值条件的递归定义。例如，斐波那契数列的递推关系是 $F_n = F_{n-1} + F_{n-2}\text{。}$ （它再结合初值条件 $F_0 = 0$ 与 $F_1 = 1$，就给出该数列完整的递归定义。）

Example 1

示例 1

Find a recurrence relation and initial conditions for $1, 5, 17, 53, 161, 485\ldots\text{.}$

求数列 $1, 5, 17, 53, 161, 485\ldots\text{。}$ 的递推关系与初值条件。

Solution

解答

Finding the recurrence relation would be easier if we had some context for the problem (like the Tower of Hanoi, for example). Alas, we have only the sequence. Remember, the recurrence relation tells you how to get from previous terms to future terms. What is going on here? We could look at the differences between terms: $4, 12, 36, 108, \ldots\text{.}$ Notice that these are growing by a factor of 3. Is the original sequence as well? $1\cdot 3 = 3\text{,}$ $5 \cdot 3 = 15\text{,}$ $17 \cdot 3 = 51$ and so on. It appears that we always end up with 2 less than the next term. Aha!

如果问题有些背景（例如汉诺塔），寻找递推关系会容易些。可惜我们只有这个数列本身。记住，递推关系告诉你如何由前面的项得到后面的项。这里到底发生了什么？我们可以观察相邻项之间的差：$4, 12, 36, 108, \ldots\text{。}$ 注意这些差以 3 倍的速度增长。原数列是否也是如此？$1\cdot 3 = 3\text{，}$ $5 \cdot 3 = 15\text{，}$ $17 \cdot 3 = 51$，依此类推。看来我们总是得到比下一项少 2 的结果。啊哈！

So $a_n = 3a_{n-1} + 2$ is our recurrence relation and the initial condition is $a_0 = 1\text{.}$

于是 $a_n = 3a_{n-1} + 2$ 就是我们的递推关系，初值条件为 $a_0 = 1\text{。}$

We are going to try to solve these recurrence relations. By this we mean something very similar to solving differential equations: we want to find a function of $n$ (a closed formula) which satisfies the recurrence relation, as well as the initial condition.²Recurrence relations are sometimes called difference equations since they can describe the difference between terms and this highlights the relation to differential equations further. Just like for differential equations, finding a solution might be tricky, but checking that the solution is correct is easy.

接下来我们要试着求解这些递推关系。这里的意思与求解微分方程非常相似：我们想找到一个关于 $n$ 的函数（即闭式），它既满足递推关系，又满足初值条件。² 递推关系有时也称为差分方程，因为它能描述相邻项之间的差，这进一步凸显了它与微分方程的关联。与微分方程一样，找到解可能不易，但验证解是否正确却很容易。

Example 2

示例 2

Check that $a_n = 2^n + 1$ is a solution to the recurrence relation $a_n = 2a_{n-1} - 1$ with $a_1 = 3\text{.}$

验证 $a_n = 2^n + 1$ 是递推关系 $a_n = 2a_{n-1} - 1$ 在初值条件 $a_1 = 3$ 下的一个解。

Solution

解答

First, it is easy to check the initial condition: $a_1$ should be $2^1 + 1$ according to our closed formula. Indeed, $2^1 + 1 = 3\text{,}$ which is what we want. To check that our proposed solution satisfies the recurrence relation, try plugging it in.

首先，验证初值条件很容易：按我们的闭式，$a_1$ 应为 $2^1 + 1$。确实，$2^1 + 1 = 3\text{，}$正是我们所期望的。要验证所提议的解满足递推关系，把它代进去试试看。

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

That's what our recurrence relation says! We have a solution.

这正是我们的递推关系所说的！我们找到了一个解。

Sometimes we can be clever and solve a recurrence relation by inspection. We generate the sequence using the recurrence relation and keep track of what we are doing so that we can see how to jump to finding just the $a_n$ term. Here are two examples of how you might do that.

有时我们可以用巧思、通过直接观察来求解递推关系。我们用递推关系生成数列，并留意自己每一步在做什么，从而看清如何直接跳到只求 $a_n$ 那一项。下面是两个这类思路的例子。

Telescoping refers to the phenomenon when many terms in a large sum cancel out - so the sum "telescopes." For example:

逐项相消（telescoping）指的是这样一种现象：一个大求和式中的许多项彼此抵消——于是这个和会"叠缩"成形。例如：

\begin{equation*} (2 - 1) + (3 - 2) + (4 - 3) + \cdots + (100 - 99) + (101 - 100) = -1 + 101 \end{equation*}

because every third term looks like: $2 + -2 = 0\text{,}$ and then $3 + -3 = 0$ and so on.

因为每一对项都形如：$2 + -2 = 0\text{，}$接着 $3 + -3 = 0$，如此等等。

We can use this behavior to solve recurrence relations. Here is an example.

我们可以利用这一性质来求解递推关系。下面是一个例子。

Example 3

示例 3

Solve the recurrence relation $a_n = a_{n-1} + n$ with initial term $a_0 = 4\text{.}$

求解递推关系 $a_n = a_{n-1} + n$，初值项 $a_0 = 4\text{。}$

Solution

解答

To get a feel for the recurrence relation, write out the first few terms of the sequence: $4, 5, 7, 10, 14, 19, \ldots\text{.}$ Look at the difference between terms. $a_1 - a_0 = 1$ and $a_2 - a_1 = 2$ and so on. The key thing here is that the difference between terms is $n\text{.}$ We can write this explicitly: $a_n - a_{n-1} = n\text{.}$ Of course, we could have arrived at this conclusion directly from the recurrence relation by subtracting $a_{n-1}$ from both sides.

为了感受这个递推关系，先把数列的前几项写出来：$4, 5, 7, 10, 14, 19, \ldots\text{。}$ 再看相邻项的差。$a_1 - a_0 = 1$，$a_2 - a_1 = 2$，依此类推。这里的关键是：项与项的差是 $n\text{。}$ 我们可以明确写出：$a_n - a_{n-1} = n\text{。}$ 当然，也可以直接由递推关系两边同减 $a_{n-1}$ 得到这一结论。

Now use this equation over and over again, changing $n$ each time:

现在反复使用这个等式，每次改变 $n$：

\begin{align*} a_1 - a_0 &= 1\\ a_2 - a_1 &= 2\\ a_3 - a_2 &= 3\\ \vdots \quad &= \quad \vdots\\ a_n - a_{n-1} &= n. \end{align*}

Add all these equations together. On the right-hand side, we get the sum $1 + 2 + 3 + \cdots + n\text{.}$ We already know this can be simplified to $\frac{n(n+1)}{2}\text{.}$ What happens on the left-hand side? We get

把所有这些等式相加。右边得到和 $1 + 2 + 3 + \cdots + n\text{。}$ 我们已经知道它可以化简为 $\frac{n(n+1)}{2}\text{。}$ 左边发生了什么？我们得到

\begin{equation*} (a_1 - a_0) + (a_2 - a_1) + (a_3 - a_2) + \cdots (a_{n-1} - a_{n-2})+ (a_n - a_{n-1}). \end{equation*}

This sum telescopes. We are left with only the $-a_0$ from the first equation and the $a_n$ from the last equation. Putting this all together we have $-a_0 + a_n = \frac{n(n+1)}{2}$ or $a_n = \frac{n(n+1)}{2} + a_0\text{.}$ But we know that $a_0 = 4\text{.}$ So the solution to the recurrence relation, subject to the initial condition is

这个和会逐项相消。最后只剩第一项中的 $-a_0$ 与最后一项中的 $a_n$。合并起来得到 $-a_0 + a_n = \frac{n(n+1)}{2}$，也就是 $a_n = \frac{n(n+1)}{2} + a_0\text{。}$ 而我们知道 $a_0 = 4\text{。}$ 因此满足该初值条件的递推关系解为

\begin{equation*} a_n = \frac{n(n+1)}{2} + 4. \end{equation*}

(Now that we know that, we should notice that the sequence is the result of adding 4 to each of the triangular numbers.)

（既然已经知道，我们应当注意到：这个数列是在每个三角形数上加 4 得到的。）

The above example shows a way to solve recurrence relations of the form $a_n = a_{n-1} + f(n)$ where $\sum_{k = 1}^n f(k)$ has a known closed formula. If you rewrite the recurrence relation as $a_n - a_{n-1} = f(n)\text{,}$ and then add up all the different equations with $n$ ranging between 1 and $n\text{,}$ the left-hand side will always give you $a_n - a_0\text{.}$ The right-hand side will be $\sum_{k = 1}^n f(k)\text{,}$ which is why we need to know the closed formula for that sum.

上面的例子给出了一种求解形如 $a_n = a_{n-1} + f(n)$ 的递推关系的方法，其中 $\sum_{k = 1}^n f(k)$ 有已知的闭式。若把递推关系改写为 $a_n - a_{n-1} = f(n)\text{，}$再把 $n$ 取遍 1 到 $n$ 的各个等式相加，左边总会得到 $a_n - a_0\text{。}$ 右边则是 $\sum_{k = 1}^n f(k)\text{，}$这也正是我们需要知道该和之闭式的原因。

However, telescoping will not help us with a recursion such as $a_n = 3a_{n-1} + 2$ since the left-hand side will not telescope. You will have $-3a_{n-1}$'s but only one $a_{n-1}\text{.}$ However, we can still be clever if we use iteration.

然而，逐项相消对形如 $a_n = 3a_{n-1} + 2$ 的递归无能为力，因为左边不会相消。你会得到多个 $-3a_{n-1}$，却只有一个 $a_{n-1}\text{。}$ 不过，若采用迭代法，我们仍可以很巧妙地处理。

We have already seen an example of iteration when we found the closed formula for arithmetic and geometric sequences. The idea is, we iterate the process of finding the next term, starting with the known initial condition, up until we have $a_n\text{.}$ Then we simplify. In the arithmetic sequence example, we simplified by multiplying $d$ by the number of times we add it to $a$ when we get to $a_n\text{,}$ to get from $a_n = a + d + d + d + \cdots + d$ to $a_n = a + dn\text{.}$

在求等差数列与等比数列的闭式时，我们已经见过迭代的例子。其思想是：从已知的初值条件出发，反复执行"求下一项"的过程，直到得到 $a_n\text{，}$然后再化简。在等差数列的例子中，我们把 $d$ 乘上从 $a$ 加到 $a_n$ 时所加的次数来化简，从而由 $a_n = a + d + d + d + \cdots + d$ 得到 $a_n = a + dn\text{。}$

To see how this works, let's go through the same example we used for telescoping, but this time use iteration.

为了看清它的运作方式，我们用与逐项相消相同的例子再走一遍，但这次使用迭代法。

Example 4

示例 4

Use iteration to solve the recurrence relation $a_n = a_{n-1} + n$ with $a_0 = 4\text{.}$

用迭代法求解递推关系 $a_n = a_{n-1} + n$，初值 $a_0 = 4\text{。}$

Answer

解答

Again, start by writing down the recurrence relation when $n = 1\text{.}$ This time, don't subtract the $a_{n-1}$ terms to the other side:

再次从写出 $n = 1$ 时的递推关系开始。这次不要把 $a_{n-1}$ 移到等式另一边：

\begin{equation*} a_1 = a_0 + 1. \end{equation*}

Now $a_2 = a_1 + 2\text{,}$ but we know what $a_1$ is. By substitution, we get

现在 $a_2 = a_1 + 2\text{，}$但我们知道 $a_1$ 是什么。代入可得

\begin{equation*} a_2 = (a_0 + 1) + 2. \end{equation*}

Now go to $a_3 = a_2 + 3\text{,}$ using our known value of $a_2\text{:}$

再看 $a_3 = a_2 + 3\text{，}$利用已知的 $a_2$ 值：

\begin{equation*} a_3 = ((a_0 + 1) + 2) + 3. \end{equation*}

We notice a pattern. Each time, we take the previous term and add the current index. So

我们注意到一个规律。每次都把前一项加上当前的下标。于是

\begin{equation*} a_n = ((((a_0 + 1) +2)+3)+\cdots + n-1) + n. \end{equation*}

Regrouping terms, we notice that $a_n$ is just $a_0$ plus the sum of the integers from $1$ to $n\text{.}$ So, since $a_0 = 4\text{,}$

重新组合各项，我们发现 $a_n$ 就是 $a_0$ 加上从 $1$ 到 $n$ 的整数之和。因此，由于 $a_0 = 4\text{，}$

\begin{equation*} a_n = 4 + \frac{n(n+1)}{2}. \end{equation*}

Of course in this case we still needed to know formula for the sum of $1,\ldots,n\text{.}$ Let's try iteration with a sequence for which telescoping doesn't work.

当然，这里仍然需要知道 $1,\ldots,n$ 的求和公式。下面我们用一个逐项相消法失效的数列来试试迭代。

Example 5

示例 5

Solve the recurrence relation $a_n = 3a_{n-1} + 2$ subject to $a_0 = 1\text{.}$

求解递推关系 $a_n = 3a_{n-1} + 2$，初值 $a_0 = 1\text{。}$

Answer

解答

Again, we iterate the recurrence relation, building up to the index $n\text{.}$

再次对递推关系迭代，逐步累积到下标 $n\text{。}$

\begin{align*} a_1 &= 3a_0 + 2\\ a_2 &= 3(a_1) + 2 = 3(3a_0 + 2) + 2\\ a_3 &= 3(a_2) + 2 = 3(3(3a_0 + 2) + 2) + 2\\ \vdots & \qquad \vdots \qquad \qquad \vdots\\ a_n &= 3(a_{n-1}) + 2 = 3(3(3(3\cdots(3a_0 + 2) + 2) + 2)\cdots + 2)+ 2. \end{align*}

It is difficult to see what is happening here because we have to distribute all those 3's. Let's try again, this time simplifying a bit as we go.

这里难以看清发生了什么，因为我们要把所有那些 3 分配进去。我们再试一次，这次边写边稍作化简。

\begin{align*} a_1 &= 3a_0 + 2\\ a_2 &= 3(a_1) + 2 = 3(3a_0 + 2) + 2 = 3^2a_0 + 2\cdot 3 + 2\\ a_3 &= 3(a_2) + 2 = 3(3^2a_0 + 2\cdot 3 + 2) + 2 = 3^3 a_0 + 2 \cdot 3^2 + 2 \cdot 3 + 2\\ \vdots & \qquad\quad \vdots \hspace{2in} \vdots\\ a_n &= 3(a_{n-1}) + 2 = 3(3^{n-1}a_0 + 2 \cdot 3^{n-2} + \cdots +2)+ 2\\ & \qquad \qquad = 3^n a_0 + 2\cdot 3^{n-1} + 2 \cdot 3^{n-2} + \cdots + 2\cdot 3 + 2. \end{align*}

Now we simplify. $a_0 = 1\text{,}$ so we have $3^n + \langle\text{stuff}\rangle\text{.}$ Note that all the other terms have a 2 in them. In fact, we have a geometric sum with first term $2$ and common ratio $3\text{.}$ We have seen how to simplify $2 + 2\cdot 3 + 2 \cdot 3^2 + \cdots + 2\cdot 3^{n-1}\text{.}$ We get $\frac{2-2\cdot 3^n}{-2}$ which simplifies to $3^n - 1\text{.}$ Putting this together with the first $3^n$ term gives our closed formula:

现在化简。$a_0 = 1\text{，}$于是得到 $3^n + \langle\text{stuff}\rangle\text{。}$ 注意其余各项都含因子 2。事实上，我们有一个首项为 $2$、公比为 $3$ 的等比数列求和。我们已经见过如何化简 $2 + 2\cdot 3 + 2 \cdot 3^2 + \cdots + 2\cdot 3^{n-1}\text{：}$得到 $\frac{2-2\cdot 3^n}{-2}$，化简为 $3^n - 1\text{。}$ 把它与最前面的 $3^n$ 项合并，得到闭式：

\begin{equation*} a_n = 2\cdot 3^n - 1. \end{equation*}

Iteration can be messy, but when the recurrence relation only refers to one previous term (and maybe some function of $n$) it can work well. However, trying to iterate a recurrence relation such as $a_n = 2 a_{n-1} + 3 a_{n-2}$ will be way too complicated. We would need to keep track of two sets of previous terms, each of which were expressed by two previous terms, and so on. The length of the formula would grow exponentially (double each time, in fact). Luckily there happens to be a method for solving recurrence relations which works very well on relations like this.

迭代可能很繁琐，但当递推关系只涉及前一个项（或许再加上某个关于 $n$ 的函数）时，它能奏效。然而，试图对形如 $a_n = 2 a_{n-1} + 3 a_{n-2}$ 的递推关系迭代会过于复杂。我们需要同时跟踪两组前项，而每组又由两组更前的项表示，如此递推。公式的长度会呈指数增长（事实上是每次翻倍）。所幸，恰好存在一种求解递推关系的方法，对这类关系非常有效。

The Characteristic Root Technique 特征根法

Suppose we want to solve a recurrence relation expressed as a combination of the two previous terms, such as $a_n = a_{n-1} + 6a_{n-2}\text{.}$ In other words, we want to find a function of $n$ which satisfies $a_n - a_{n-1} - 6a_{n-2} = 0\text{.}$ Now iteration is too complicated, but think just for a second what would happen if we did iterate. In each step, we would, among other things, multiply a previous iteration by 6. So our closed formula would include $6$ multiplied some number of times. Thus it is reasonable to guess the solution will contain parts that look geometric. Perhaps the solution will take the form $r^n$ for some constant $r\text{.}$

假设我们要解一个由前两项组合而成的递推关系，例如 $a_n = a_{n-1} + 6a_{n-2}\text{。}$ 换句话说，我们想找到一个关于 $n$ 的函数，满足 $a_n - a_{n-1} - 6a_{n-2} = 0\text{。}$ 现在迭代过于复杂，但不妨试想：如果我们真的迭代，会发生什么。在每一步中，除了别的运算，我们还要把上一次迭代的结果乘以 6。于是闭式中会包含若干个 6 相乘。因此可以合理地猜想：解会含有类似等比数列的部分。也许解会取 $r^n$ 的形式，其中 $r$ 为某常数。

The nice thing is, we know how to check whether a formula is actually a solution to a recurrence relation: plug it in. What happens if we plug in $r^n$ into the recursion above? We get

妙处在于：我们知道如何验证一个公式是否真的是递推关系的解——代进去即可。如果把 $r^n$ 代入上面的递归，会得到什么？

\begin{equation*} r^n - r^{n-1} - 6r^{n-2} = 0. \end{equation*}

Now solve for $r\text{:}$

现在解 $r\text{：}$

\begin{equation*} r^{n-2}(r^2 - r - 6) = 0, \end{equation*}

so by factoring, $r = -2$ or $r = 3$ (or $r = 0\text{,}$ although this does not help us). This tells us that $a_n = (-2)^n$ is a solution to the recurrence relation, as is $a_n = 3^n\text{.}$ Which one is correct? They both are, unless we specify initial conditions. Notice we could also have $a_n = (-2)^n + 3^n\text{.}$ Or $a_n = 7(-2)^n + 4\cdot 3^n\text{.}$ In fact, for any $a$ and $b\text{,}$ $a_n = a(-2)^n + b 3^n$ is a solution (try plugging this into the recurrence relation). To find the values of $a$ and $b\text{,}$ use the initial conditions.

于是因式分解得 $r = -2$ 或 $r = 3$（或者 $r = 0\text{，}$尽管这对我们没用）。这说明 $a_n = (-2)^n$ 是递推关系的一个解，$a_n = 3^n$ 也是。哪个才对？若不明确初值条件，二者都对。注意我们也可以有 $a_n = (-2)^n + 3^n\text{。}$ 或 $a_n = 7(-2)^n + 4\cdot 3^n\text{。}$ 事实上，对任意 $a$ 与 $b\text{，}$ $a_n = a(-2)^n + b 3^n$ 都是解（把它代入递推关系试试）。要确定 $a$ 与 $b$ 的值，需使用初值条件。

This points us in the direction of a more general technique for solving recurrence relations. Notice we will always be able to factor out the $r^{n-2}$ as we did above. So we really only care about the other part. We call this other part the characteristic equation for the recurrence relation. We are interested in finding the roots of the characteristic equation, which are called (surprise) the characteristic roots.

这指引我们走向一种更通用的求解递推关系的技术。注意我们总可以像上面那样提取出 $r^{n-2}$。因此我们真正关心的只是另一部分。我们把这另一部分称为该递推关系的特征方程。我们感兴趣的是求特征方程的根，它们（不出所料）被称为特征根。

Characteristic Roots 特征根

Given a recurrence relation $a_n + \alpha a_{n-1} + \beta a_{n-2} = 0\text{,}$ the characteristic polynomial is

给定递推关系 $a_n + \alpha a_{n-1} + \beta a_{n-2} = 0\text{，}$其特征多项式为

\begin{equation*} x^2 + \alpha x + \beta \end{equation*}

giving the characteristic equation:

由此得到特征方程：

\begin{equation*} x^2 + \alpha x + \beta = 0. \end{equation*}

If $r_1$ and $r_2$ are two distinct roots of the characteristic polynomial (i.e, solutions to the characteristic equation), then the solution to the recurrence relation is

若 $r_1$ 与 $r_2$ 是特征多项式的两个互异根（即特征方程的解），则该递推关系的解为

\begin{equation*} a_n = ar_1^n + br_2^n, \end{equation*}

where $a$ and $b$ are constants determined by the initial conditions.

其中 $a$ 与 $b$ 是由初值条件确定的常数。

Example 6

示例 6

Solve the recurrence relation $a_n = 7a_{n-1} - 10 a_{n-2}$ with $a_0 = 2$ and $a_1 = 3\text{.}$

求解递推关系 $a_n = 7a_{n-1} - 10 a_{n-2}$，初值 $a_0 = 2$、$a_1 = 3\text{。}$

Solution

解答

Rewrite the recurrence relation $a_n - 7a_{n-1} + 10a_{n-2} = 0\text{.}$ Now form the characteristic equation:

改写递推关系为 $a_n - 7a_{n-1} + 10a_{n-2} = 0\text{。}$ 现在写出特征方程：

\begin{equation*} x^2 - 7x + 10 = 0 \end{equation*}

and solve for $x\text{:}$

解 $x\text{：}$

\begin{equation*} (x - 2) (x - 5) = 0 \end{equation*}

so $x = 2$ and $x = 5$ are the characteristic roots. We therefore know that the solution to the recurrence relation will have the form

于是 $x = 2$ 与 $x = 5$ 是特征根。因此我们可知递推关系的解将具有如下形式

\begin{equation*} a_n = a 2^n + b 5^n. \end{equation*}

To find $a$ and $b\text{,}$ plug in $n =0$ and $n = 1$ to get a system of two equations with two unknowns:

为求 $a$ 与 $b\text{，}$代入 $n =0$ 与 $n = 1$，得到含两个未知数的二元方程组：

\begin{align*} 2 &= a 2^0 + b 5^0 = a + b\\ 3 &= a 2^1 + b 5^1 = 2a + 5b \end{align*}

Solving this system gives $a = \frac{7}{3}$ and $b = -\frac{1}{3}$ so the solution to the recurrence relation is

解此方程组得 $a = \frac{7}{3}$、$b = -\frac{1}{3}$，故该递推关系的解为

\begin{equation*} a_n = \frac{7}{3}2^n - \frac{1}{3} 5^n. \end{equation*}

Perhaps the most famous recurrence relation is $F_n = F_{n-1} + F_{n-2}\text{,}$ which together with the initial conditions $F_0 = 0$ and $F_1= 1$ defines the Fibonacci sequence. But notice that this is precisely the type of recurrence relation on which we can use the characteristic root technique. When you do, the only thing that changes is that the characteristic equation does not factor, so you need to use the quadratic formula to find the characteristic roots. In fact, doing so gives the third most famous irrational number, $\varphi\text{,}$ the golden ratio.

或许最有名的递推关系是 $F_n = F_{n-1} + F_{n-2}\text{，}$它再结合初值条件 $F_0 = 0$ 与 $F_1 = 1$，就定义了斐波那契数列。但请注意，这正是可以使用特征根法的一类递推关系。使用时唯一的不同在于：特征方程无法在有理数范围内因式分解，因此需要用二次公式来求特征根。事实上，这样做会给出第三著名的无理数——黄金比例 $\varphi\text{。}$

Before leaving the characteristic root technique, we should think about what might happen when you solve the characteristic equation. We have an example above in which the characteristic polynomial has two distinct roots. These roots can be integers, or perhaps irrational numbers (requiring the quadratic formula to find them). In these cases, we know what the solution to the recurrence relation looks like.

在结束特征根法之前，我们应当想想：求解特征方程时还可能发生什么。上面有一个例子，其特征多项式有两个互异根。这些根可以是整数，也可以是（需要二次公式才能求出的）无理数。在这些情况下，我们知道递推关系的解长什么样。

However, it is possible for the characteristic polynomial to only have one root. This can happen if the characteristic polynomial factors as $(x - r)^2\text{.}$ It is still the case that $r^n$ would be a solution to the recurrence relation, but we won't be able to find solutions for all initial conditions using the general form $a_n = ar_1^n + br_2^n\text{,}$ since we can't distinguish between $r_1^n$ and $r_2^n\text{.}$ We are in luck though:

然而，特征多项式也可能只有一个根。当特征多项式分解为 $(x - r)^2$ 时就可能出现这种情况。此时 $r^n$ 仍是递推关系的一个解，但我们没办法用一般形式 $a_n = ar_1^n + br_2^n$ 来满足所有初值条件，因为我们无从区分 $r_1^n$ 与 $r_2^n\text{。}$ 不过我们走运了：

Characteristic Root Technique for Repeated Roots 重根情形下的特征根法

Suppose the recurrence relation $a_n = \alpha a_{n-1} + \beta a_{n-2}$ has a characteristic polynomial with only one root $r\text{.}$ Then the solution to the recurrence relation is

假设递推关系 $a_n = \alpha a_{n-1} + \beta a_{n-2}$ 的特征多项式只有一个根 $r\text{。}$ 那么该递推关系的解为

\begin{equation*} a_n = ar^n + bnr^n \end{equation*}

where $a$ and $b$ are constants determined by the initial conditions.

其中 $a$ 与 $b$ 是由初值条件确定的常数。

Notice the extra $n$ in $bnr^n\text{.}$ This allows us to solve for the constants $a$ and $b$ from the initial conditions.

注意 $bnr^n$ 中多出的那个 $n$。它使我们能由初值条件解出常数 $a$ 与 $b$。

Example 7

示例 7

Solve the recurrence relation $a_n = 6a_{n-1} - 9a_{n-2}$ with initial conditions $a_0 = 1$ and $a_1 = 4\text{.}$

求解递推关系 $a_n = 6a_{n-1} - 9a_{n-2}$，初值 $a_0 = 1$、$a_1 = 4\text{。}$

Answer

解答

The characteristic polynomial is $x^2 - 6x + 9\text{.}$ We solve the characteristic equation

特征多项式为 $x^2 - 6x + 9\text{。}$ 解特征方程

\begin{equation*} x^2 - 6x + 9 = 0 \end{equation*}

by factoring:

因式分解：

\begin{equation*} (x - 3)^2 = 0 \end{equation*}

so $x =3$ is the only characteristic root. Therefore we know that the solution to the recurrence relation has the form

于是 $x = 3$ 是仅有的特征根。因此我们可知该递推关系的解具有形式

\begin{equation*} a_n = a 3^n + bn3^n \end{equation*}

for some constants $a$ and $b\text{.}$ Now use the initial conditions:

其中 $a$ 与 $b$ 为某两个常数。现在代入初值条件：

\begin{align*} a_0 = 1 &= a 3^0 + b\cdot 0 \cdot 3^0 = a\\ a_1 = 4 &= a\cdot 3 + b\cdot 1 \cdot3 = 3a + 3b. \end{align*}

Since $a = 1\text{,}$ we find that $b = \frac{1}{3}\text{.}$ Therefore the solution to the recurrence relation is

由于 $a = 1\text{，}$得 $b = \frac{1}{3}\text{。}$ 因此该递推关系的解为

\begin{equation*} a_n = 3^n + \frac{1}{3}n3^n. \end{equation*}

Although we will not consider examples more complicated than these, this characteristic root technique can be applied to much more complicated recurrence relations. For example, $a_n = 2a_{n-1} + a_{n-2} - 3a_{n-3}$ has characteristic polynomial $x^3 - 2 x^2 - x + 3\text{.}$ Assuming you see how to factor such a degree 3 (or more) polynomial you can easily find the characteristic roots and as such solve the recurrence relation (the solution would look like $a_n = ar_1^n + br_2^n + cr_3^n$ if there were 3 distinct roots). It is also possible to solve recurrence relations of the form $a_n = \alpha a_{n-1} + \beta a_{n-2} + C$ for some constant $C\text{.}$ It is also possible (and acceptable) for the characteristic roots to be complex numbers.

尽管我们不再考虑比这些更复杂的例子，但特征根法可以应用于远为复杂的递推关系。例如，$a_n = 2a_{n-1} + a_{n-2} - 3a_{n-3}$ 的特征多项式为 $x^3 - 2 x^2 - x + 3\text{。}$ 假定你会分解这种三次（或更高次）多项式，就能轻松求出特征根，从而解出递推关系（若有 3 个互异根，解形如 $a_n = ar_1^n + br_2^n + cr_3^n$）。对于形如 $a_n = \alpha a_{n-1} + \beta a_{n-2} + C$（$C$ 为某常数）的递推关系，也可以求解。特征根为复数同样是可能（且可以接受）的。