介绍如题的内容

毕业生的工作问题：

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

记第 $n$年有$f(n)$ 个教授，$f(0)=0,f(1)=1,f(2)=1,f(3)=2,f(4)=3,f(5)=5$ 。没错，是个斐波那契数列。$f(n)=f(n-1)+f(n-2)$ 。

线性递推

是指递推满足如下形式：

$$ f(n)=\sum_{i=1}^da_if(n-i)+g(n) $$

其中 $a_i$ 是常数，$d$ 被称为阶数。$g(n)$为$0$ 时称为齐次线性递推。

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

$$ \begin{aligned} &\frac{1}{\sqrt{5}} \left( \frac{1+\sqrt{5}}{2} \right)^n + \delta(n) \geq M \\ \Rightarrow \quad &\left( \frac{1+\sqrt{5}}{2} \right)^n \geq \sqrt{5} (M - \delta(n)) \\ &n \geq \frac{\log(\sqrt{5}(M - \delta(n)))}{\log(\frac{1+\sqrt{5}}{2})} = \Theta(\log M) \end{aligned} $$

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

$$ \alpha^d-a_1\alpha^{d-1}-...-a_d=0 $$

这被称为特征方程。

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

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

假设 $\alpha$是特征方程的$r$重根，那么$\alpha^n, n\alpha^n,…,n^{r-1}\alpha^n$ 都是递推方程的根，我们将他们作为等效的根进行线性组合也就得到了递推方程的解。这与微分方程一致。

Ex.考虑如下的递推：

$$ f(n)=2f(n-1)-f(n-2) $$

那么特征方程就是

$$ \alpha^2-2\alpha+1=0 $$

$\alpha=1$则是二重根，利用前面所说，根就由$\alpha^2,n\alpha^2$构成，也就是$c_1+c_2n$ 。

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

$$ f(n)-a_1f(n-1)-...-a_df(n-d)=g(n) $$

$g(n)=0$ 就回到了齐次的情形。与线性方程组/微分方程类似，我们

• 首先求解 $g(n)=0$ 的情形得到通解

• 然后带入 $g(n)$ 找到特解

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

Ex.考虑

$$ f(n)=4f(n-1)+3^n $$

首先扔掉 $3^n$，那么可以一眼看出$\alpha=4$，那么$c_14^n$ 就是通解 。
然后试着找特解，根据形式，我们猜 $f(n)=c_23^n$，代入得到$c_2=-3$，那么特解就是$-3^{n+1}$ 。
最后把通解加上特解得到，$f(n)=c_14^n-3^{n+1}$ ，最后的系数则通过边界条件解出。

关于猜特解，就通过 $g(n)$猜，多项式就猜多项式，指数就猜指数……如果，例如$g(n)=2^n$猜测$a2^n$失败，就猜测$(an+b)2^n$还不行再猜$(an^2+bn+c)2^n$ ，往往能解决问题，