介绍如题的内容

---

毕业生的工作问题：

工作总数固定是 ，假设在某个领域每年每个教授教出一个毕业生，除了第一年。假设教师们不会退休(永生)，什么时候 个职位会被填满？边界条件：一个教授在一开始被聘用。

记第 年有 个教授， 。没错，是个斐波那契数列。 。

线性递推

是指递推满足如下形式：

其中 是常数， 被称为阶数。 为 时称为齐次线性递推。

如何求解呢，我们猜测 ，其中 是常数。代入递推式(斐波那契)化简得到：，这就能解出 的两个根，那么就有 。实际上，利用线性， 的任意线性组合也是解。为了确定他们的线性组合，就需要边界条件。例如 ，如此解出两个系数。 那么回到开头的问题：

对于一般的齐次线性递推，带入幂次猜测就有：

这被称为特征方程。

如果没有重根，那么解的线性组合就是递推方程的解。具体可以通过边界条件确定系数。

如果存在重根呢，我们不加证明地给出结果：

假设 是特征方程的 重根，那么 都是递推方程的根，我们将他们作为等效的根进行线性组合也就得到了递推方程的解。这与微分方程一致。

Ex.考虑如下的递推：

那么特征方程就是

则是二重根，利用前面所说，根就由 构成，也就是 。

对于非齐次的情形，特征方程变成：

就回到了齐次的情形。与线性方程组/微分方程类似，我们

• 首先求解 的情形得到通解

• 然后带入 找到特解

• 最后的结果形式由通解加特解确定，并通过边界条件确定系数。

Ex.考虑

首先扔掉 ，那么可以一眼看出 ，那么 就是通解 。 然后试着找特解，根据形式，我们猜 ，代入得到 ，那么特解就是 。 最后把通解加上特解得到， ，最后的系数则通过边界条件解出。

关于猜特解，就通过 猜，多项式就猜多项式，指数就猜指数……如果，例如 猜测 失败，就猜测 还不行再猜 ，往往能解决问题，