递推关系与差分方程¶

数列的递推关系(Recurrence relation)，就是一个数列的第\(n\)项和前\(n-1\)项的等式。这个等式也叫差分方程(Difference equation)。

差分方程的概念¶

在差分方程中，一个很重要的任务就是从递推关系求解出数列的通项公式，这个过程称为解差分方程。

和数列的求和一样，求解递推关系（差分方程）也没有通用的方法。不过，下面我们会介绍一些常用的解法，能解决一部分常见的差分方程。

Tip

并不是所有的差分方程都可以给出初等解或者解析解。一个很显然的例子就是阶乘：定义数列\(a_0 = 1\)，\(a_{n+1} = na_n\)，那么这个数列就是阶乘数列\(a_n = n!\)，但阶乘并不是初等函数（阶乘在实数上的延拓是 Gamma 函数，但 Gamma 函数并非初等函数）。

如果将数列的求和类比成积分，那么差分方程就应该对应微积分的微分方程。很多微分方程和差分方程都无法用解析解表示。

通解与特解¶

一个差分方程往往不止一个解，差分方程的所有解的集合称为通解。而其中一个特定的解，称为差分方程的特解。

初值条件¶

差分方程的求解过程中，往往需要伴随某些已知的条件，例如已知某一项的具体值。这些条件称为初值条件(initial condition)。

这个条件的作用之一就是从通解得出满足给定条件的特解。

最常见的初值条件就是已知前几项 \(a_1, \dots, a_k\) 的值。

一些典型的差分方程¶

等差数列¶

等差数列的定义式是：

\[ a_n - a_{n-1} = d; \]

这是一个典型的差分方程，在第一节中我们已经用数学归纳法证明了等差数列的通项为 \(a_n = a_1 + d(n-1)\)。

这里我们用 \(a_1\) 表示了通项，实际上暗含了 \(a_1\) 已知的假设。也就是说，\(a_1\) 是这个方程的初值条件。

等比数列¶

\[ \frac{a_{n+1}}{a_n} = q; \]

阶乘¶

数列递推与编程递归

递推与递归（recursive)具有一定的相似性。

在数学上，递归指的是将一个问题分解为已经解决的问题，如用数学归纳法证明问题。类似地，编程上的递归也是将一个问题分解为它的子问题。

以下我们便可以用一个递推方法编写一个阶乘函数：

#include <stdio.h>

int factorial(int n){
    return n * factorial(n-1);
}

void main(){
    scanf("%d", &n);
    printf("%d", factorial(n));
}

def Factorial(n : int) -> int:
    return n * Factorial(n-1)

n = input()
print(Factorial(n))

差分方程与求和¶

数列的求和也是一类特殊的差分方程。求数列 \(\{a_n\}\) 的前 \(n\) 项和 \(S_n\)，也即相当于求出差分方程 \(S_n = S_{n - 1} + a_n\) 在初值条件 \(S_1 = a_1\) 下的特解。

这是一类最特殊的差分方程。如同我们学习微分方程前会先学习不定积分，学习差分方程之前也应先掌握多种数列求和技巧，然后将差分方程的求解化归到求和。

高中常见的差分方程解法¶

这些方法大多数在高中已经涉及，大家可以通过下面的内容进行温习。

如果没见过也没关系，我们会给出尽量详细的推导。

累加法¶

累加法就是将差分方程转化为一个数列的求和问题。

累加法主要适用于

\[ a_n = f(n) + a_{n-1} \]

型的方程。

累乘法¶

和累加法类似，累乘法解决的是

\[ {a_{n+1}} = f(n) a_n \]

型的方程，将数列通项转化为\(f(n)\)的前\(n\)项积的计算问题。

转化法¶

转化法是将一个数列通过平移、加项等方法，变换成熟悉的数列。

最经典的例子是\(a_n = k a_{n-1} + f(n)\)型的数列（可以称为一阶线性非齐次递推关系式），我们以这个数列举例：

Example

已知\(a_n = 2 a_{n-1} + 1, a_1 = 1\)，求\(a_n\)的通项。

Solution

这道题有多种方法：

Method 1

两边加上一个数，尝试将它配凑成等比数列的格式。经过尝试，加上1之后刚好成倍数：

\[ a_n + 1 = 2(a_{n+1} + 1). \]

于是令\(b_n = a_n + 1\)，则数列\(\{ b_n \}\)构成等比数列，于是有

\[ b_n = b_1 2^{n-1} = 2^n. \]

这样，就得到了\(a_n = 2^n - 1\)。

Method 2

方程两边除以\(2^n\)，得到：

\[ \frac{a_n}{2^n} = \frac{a_{n-1}}{2^{n-1}} + \left(\frac{1}{2}\right)^n; \]

这样，令\(c_n = a_n / 2^n\)，这样\(\{ c_n \}\)就可以用累加法进行计算。

对于二阶线性常系数递推关系式，我们也可以尝试将其转化，降次为一阶的常系数递推（等比数列）：

Example

设数列\(\{ x_n \}\)满足:

\[ x_n = (\alpha + \beta) x_{n-1} - \alpha \beta x_{n-2} \]

（其中\(\alpha,\beta\)为常数），求数列的通项公式。

Solution

我们可以将方程变形为：

\[ x_n - \beta x_{n-1} = \alpha (x_{n-1} - \beta x_{n-2}), \]

令\(y_n = x_n - \beta x_{n-1}\)，则有：

\[ y_n = \alpha y_{n-1}, \]

这说明\(\{ y_n \}\)是等比数列，得到：

\[ y_n = C \alpha^n \]

（其中\(C\)为任意常数）。这说明：

\[ x_n - \beta x_{n-1} = C \alpha^n, \]

这是上面提到的一阶线性非齐次递推关系，我们通过两边除以\(\beta^n\)得到：

\[ \frac{x_n}{\beta^n} - \frac{x_{n-1}}{\beta^{n-1}} = C \left( \frac{\alpha}{\beta} \right)^n, \]

于是，\(\{ x_n/\beta^n \}\)构成一个等比数列，可以得到：

\[ \frac{x_n}{\beta^n} = C' \frac{1 - C \left( \frac{\alpha}{\beta} \right)^n}{1 - C \left( \frac{\alpha}{\beta} \right)} \]

整理得到：

\[ x_n = A \alpha^n + B \beta^n. \]

其中\(A, B\)为常数，由初值条件确定。

取倒数法¶

这是一种特殊的转化法，通过取倒数转化为已知递推数列。

取对数法¶

这也是一种特殊的转化法，通过取对数来转化。

不动点法¶

不动点法最常见的应用是针对分式型递推数列，也即形如：

\[ x_{n+1} = \frac{A x_n + B}{C x_n + D} \]

型的数列。

不动点¶

一个函数 \(f(x)\) 的不动点指的是满足 \(f(x) = x\) 的数 \(x\)。对于一阶递推关系 \(x_n = f(x_{n - 1})\)，可以定义其不动点为 \(f(x)\) 的不动点。

直观上看，“不动点”就是经过函数 \(f\) 作用之后不改变位置的点，对于数列也就是递推中不变的点。

不动点与数列极限

如果 \(f\) 为连续函数，递推关系 \(x_n = f(x_{n - 1})\) 所确定的数列 \(\{ x_n \}\) 收敛，则其极限必定为不动点。

这一性质是显然的，设 \(x\) 为极限值，对 \(x_n = f(x_{n - 1})\) 两边取极限就得到 \(x = f(x)\)，因此 \(x\) 是不动点。

利用这一性质，我们可以先用单调有界法、压缩法、Cauchy 收敛原理等方法证明数列收敛，然后再利用不动点求出数列的极限。

不动点法解差分方程¶

（待补充）

线性常系数递推·特征方程法¶

线性常系数递推的概念¶

一般地，设\(k\)是一个固定的正整数，那么线性常系数齐次差分方程(Linear homogeneous difference equation with constant coefficients)或线性常系数齐次递推关系(Linear homogeneous recurrence with constant coefficients)，指的是满足以下条件的方程：

\[ a_n = c_1 a_{n-1} + a_2 a_{n-2} + \cdots + c_k a_{n-k}. \tag{1} \]

（其中\(c_1, \dots, c_k\)为常数）

这个递推关系中的每一项只与其前\(k\)项有关，我们将\(k\)称为这个递推关系式的阶(degree)。

而如果方程的右边还有一个固定的非零项\(g(n)\)，也即：

\[ a_n = c_1 a_{n-1} + a_2 a_{n-2} + \cdots + c_k a_{n-k} + g(n); \]

则称该方程为线性常系数非齐次差分方程(Linear nonhomogeneous diffence equation with constant coefficients)

Notation

这类差分方程的名字中，“线性”指的是两个该形式的递推关系相加，或者与一个数（实数或复数）相乘后，仍然满足该形式；“常系数”指的是\(a_{n-1},\dots,a_{n-k}\)的系数均为常数，而不是某个关于\(n\)的函数；“齐次”指的是方程的右边只包含\(a_{n-1},\dots,a_{n-k}\)这些项的组合，不再包含一个非零项\(g(n)\)。

因此，简单说，可以把\(a_n\)表示为\(a_{n-1}, \dots, a_{n-k}\)的线性组合的递推关系，称为线性常系数齐次递推关系。

方程解法的推导¶

我们可以发现，等比数列\(x_n = r^n\)在任取倍数作差之后，仍然为等比数列：

\[ x_n - k x_{n-1} = r\cdot r^{n-1} - k r^{n-1} = (r-k) r^{n-1}; \]

所以我们可以猜出，等比数列很可能满足这类方程。我们将等比数列\(a_n = r^n\)代入定义式\((1)\)得到：