高中数列与函数迭代
PragmaGCC
·
·
个人记录
数列通项
特征根法
基本流程
设有常系数齐次线性递推数列 \sum_{i=0}^{m} c_ia_{n+i}=0，并给定 a_0,a_1,\dots,a_{m-1}。
记其特征方程为 \sum_{i=0}^m c_i x^i=0，则由代数基本定理，该方程最多有 m 个复数根。称这些根为该序列的特征根。
假设最终解出 k 个不等根，记为 x_1,\dots,x_k，并记每个根的代数重数为 m_i（即每个根出现了多少次），且 \sum_{i=1}^km_i=m。
则该数列的通项可表示为
a_n=\sum_{i=1}^k \sum_{j=1}^{m_i} \lambda_{i,j} n^{j-1} x_i^n
其中 \lambda_{i,j} 为常数，根据 a_0,\dots,a_{m-1} 的值而定。
例1：求斐波那契数列的通项公式。
斐波那契数列：F_0=0,F_1=1,F_2=1,F_n=F_{n-1}+F_{n-2}。
数列的特征方程为 x^2-x-1=0，两根为 x_1=\frac{1-\sqrt5}{2},x_2=\frac{1+\sqrt5}{2}。
构造通项公式 F_n=\lambda x_1^n+\mu x_2^n，由 F_1=1,F_2=1 得
\begin{cases}
\dfrac{1-\sqrt5}{2}\lambda+\dfrac{1+\sqrt5}{2}\mu=1 \\
(\dfrac{1-\sqrt5}{2})^2\lambda+(\dfrac{1+\sqrt5}{2})^2\mu=1
\end{cases}
解得 \lambda=-\frac{1}{\sqrt5}，\mu=\frac{1}{\sqrt5}。
所以 F_n = \frac{1}{\sqrt 5}\left((\frac{1+\sqrt 5}{2})^n-(\frac{1-\sqrt 5}{2})^n\right)。
例2：求数列 a_{n+2}=6a_{n+1}-9a_n 的通项公式，其中 a_1=3,a_2=27。
列出特征方程 x^2=6x-9，解得特征根 x_1=x_2=3。于是通项形式为 (An+B)3^n，代入 a_1,a_2 解得 A=2,B=-1。
证明
生成函数
考虑该数列的生成函数 F(x)=\sum_{n\ge 0}a_nx^n。则由递推式可以写出关于 F(x) 的方程：\sum_{i=0}^m x^{m-i}c_iF(x)=C，其中 C 为某一个与 a_0,\dots,a_{m-1} 有关的 m-1 次多项式。（参考生成函数法求序列通项公式）
所以可以解出封闭形式 F(x)=\dfrac{C}{\sum_{i=0}^m c_ix^{m-i}}。
我们尝试对右式进行拆分，考虑对分母进行因式分解。
在分母的多项式中对 x 取倒数，由因式定理可以知道分母可以分解成 \sum_{i=0}^m c_ix^i=\prod_{i=1}^k(x-x_i)^{m_i}，其中 x_i 与 m_i 的定义与上文相同。
所以有 \sum_{i=0}^m c_ix^{m-i}=\prod_{i=1}^k(1-x_ix)^{m_i}，即 F(x) 可以改写成
F(x)=\dfrac{C}{\sum_{i=0}^m c_ix^{m-i}} =\sum_{i=1}^k \dfrac{\lambda_i}{(1-x_ix)^{m_i}}
其中 \lambda 是常数。
考虑求出 \frac{1}{(1-x_ix)^{m_i}} 的开放形式：
首先有 \frac{1}{1-px} = \sum_{n\ge0}p^ix^i。两边求 q 阶导变为
\begin{aligned}
\frac{1}{(1-px)^{q+1}}&=\sum_{n\ge0}n(n-1)\dots(n-q+1)p^n x^{n-q} \\
&=\sum_{n\ge0}p^q (n+1)(n+2)\dots(n+q) p^n x^n \\
\end{aligned}
所以每一个 x_i^n 前的系数都是一个关于 n 的 m_i-1 次多项式，证毕。
线性代数
还没写
考虑将递推写成矩阵形式。
不动点法
先来点简单的。
一阶齐次递推
对于数列 a_{n+1}=pa_n+q，请求出数 \lambda 使得 a_{n+1}-\lambda=p(a_n-\lambda)，并求出其通项公式。
可以待定系数，但是最后发现 \lambda 实质上是方程 x=px+q 的根，怎么会事呢？
我们在做的实际上是对原式进行代数变形，而且这个操作类似于因式分解。
所以我们如果解出来 x=\lambda，那么原式一定可以写成 A(x-\lambda)=x-\lambda 的形式，然后再换回 a 即可。
一阶分式递推
对于数列 f_{n+1}=\dfrac{af_n+b}{cf_n+d}，求其通项公式。
同样的，我们解它的不动点，应该可以求出它的因式。
由于得到的方程是 x=\dfrac{ax+b}{cx+d}，因此对根的数量进行分类讨论。
- 当只有一个根 x_0 时，代数变形后两边取倒数，发现 \frac{1}{a_n-x_0} 为等差数列。
- 当有两根 x_1,x_2 时，分别写出关于 a_n-x_1 和 a_n-x_2 的式子，两式相除即可发现 \frac{a_n-x_1}{a_n-x_2} 为等比数列。
数列求和
错位相减
没啥好说的。
裂项叠缩与阿贝尔变换
裂项的大体思想是对于已知要求的 \sum f，构造函数 g 使得 f(n)=g(n+1)-g(n)，于是有 \sum_{k=a}^bf(k)=\sum_{k=a}^bg(k+1)-g(k)=g(b+1)-g(a)。
这种方式也被称为叠缩（Telescoping），叫这个名字大抵是因为折叠望远镜的镜筒厚度止于最外层和最内层半径有关。
例3：求数列 a_n=(2n-1)3^n 的前缀和 S_n 的表达式。
考虑构造 a_n=b_{n+1}-b_n，假设 b_n=(pn+q)3^n，可得：
\begin{cases}
a_1=3=9(2p+q)-3(p+q) \\
a_2=27=27(3p+q)-9(2p+q)
\end{cases}
解得 p=1,q=-2，于是 S_n=b_{n+1}-b_1=(n-1)3^{n+1}+3。
阿贝尔求和公式
我们尝试对错位相减与裂项两种方法进行对比：
- 重新回顾错位相减，发现我们实际上是对原数列的等差部分做了差分。
- 考虑构造裂项的时候，我们假设列出来的仍是一个 Aq^n 的形式，看起来像是对等比部分做了前缀和。
这启发我们，对于形如 a_nb_n 的序列，a 的差分和 b 的前缀和应当有某种联系。
阿贝尔求和公式就是通过变换求和顺序，来构造出容易计算的差分数列。
阿贝尔求和公式：定义 B_k=\sum_{k=1}^nb_k，则有以下恒等式
\sum_{k=1}^n a_kb_k = B_na_n-\sum_{k=1}^{n-1}B_k(a_{k+1}-a_k)
更一般的，有阿贝尔变换（分部求和法）
\sum_{k=m}^na_{k}(b_{k+1}-b_k)=a_{n+1}b_{n+1}-a_mb_m-\sum_{k=m}^nb_{k+1}(a_{k+1}-a_k)
证明：
\begin{aligned}
\sum_{k=1}^na_kb_k&=\sum_{k=1}^na_k(B_k-B_{k-1})\\&=\sum_{k=1}^na_kB_k-\sum_{k=1}^na_kB_{k-1}\\
&=\sum_{k=1}^na_kB_k-\sum_{k=0}^{n-1}a_{k+1}B_{k}\\
&=a_nB_n-\sum_{k=1}^{n-1} B_k(a_{k+1}-a_k)
\end{aligned}
于是我们直接进行替换：\sum_{k=1}^n(2n-1)3^n=\frac{3}{2}(2n-1)(3^{n}-1)-\frac{3}{2}\sum_{k=1}^n2(3^k-1)，整理即可。
求导
注意到出现了形如 \sum kx^k 的式子，考虑求导。
首先对于等比数列有 \sum_{k=1}^nx^{k-1}=\dfrac{x^n-1}{x-1}，两边求导得到 \sum_{k=1}^n(k-1)x^{k-2}=\dfrac{nx^{n-1}(x-1)-x^n+1}{(x-1)^2}。
之后同时乘以 x，再换一下下标得到 \sum_{k=1}^nkx^k=\dfrac{(n+1)x^{n+1}}{x-1}-\dfrac{x^{n+1}-1}{(x-1)^2}x。
于是 \sum_{k=1}^n(Ak+B)x^k=\dfrac{A(n+1)x^{n+1}}{x-1}-Ax\dfrac{x^{n+1}-1}{(x-1)^2}+Bx\dfrac{x^n-1}{x-1}，整理得到
\sum_{k=1}^n(Ak+B)x^k=\frac{a_{n+1}}{x-1}-\frac{x}{x-1}(\frac{A(x^{n+1}-1)}{x-1}+B)
有限微积分
可参考有限微积分与数列求和。
不难注意到分部求和法则 \sum u\Delta v=uv-\sum \text{E} v\Delta u 其实就是阿贝尔变换，同时我们做的事情和求导也很像，这揭示了无限微积分与有限和式之间的一些联系。
以及由于 \sum x^{\underline{k}}q^x\delta x=\dfrac{x^{\underline{k}}q^x}{q-1}-\sum \dfrac{q^{x+1}}{q-1}kx^{\underline{k-1}}\delta x，所以对于形如 a_nf(n)q^n 的求和，其中 f(n) 为关于 n 的 k 次多项式，其前缀和必定可以写成 S_n=g(n)q^n+C 的形式，从而可以强行待定系数法（这也说明了上文例3中直接将答案设成这种形式的原因）。
函数迭代
定义与性质
定义1：定义 f^{(n)}(x)=\underbrace{f(f(\cdots f(x)\cdots))}_{n个f} 表示函数 f(x) 的 n 次迭代。
特别地，约定 f^{(0)}(x)=x。
显然有一些性质，比如 f^{(m)}(f^{(n)}(x))=f^{(m+n)}(x)。
于是我们可以定义 f^{(-n)}(x) 为满足 f^{(n)}(f^{(-n)}(x))=x 的函数。注意它不一定存在。
对于 n=1，我们也把 f^{(-1)}(x) 叫做 f(x) 的反函数，简记为 f^{-1}(x)。
定义2（轨道）：对于 x 与函数 f(x)，定义 x 的一个 f 轨道为无穷序列 x,f(x),f^{(2)}(x),\dots,f^{(n)}(x),\dots。
也可简称为 x 的轨道。
其实就是数列和他的递推公式。
定义3（不动点）：称满足 f(x_0)=x_0 的数 x_0 为函数 f 的一个不动点。
后面会有用。
定义4（相似函数）：如果两个函数 f,g 的定义域相同，且存在可逆函数 \varphi，使得 f(x)=\varphi^{-1}(g(\varphi(x)))，则称函数 f 与 g 关于 \varphi 相似，记作 f\stackrel{\varphi}{\sim}g，简称为 f\sim g。
这里的函数 \varphi(x) 称为桥函数。
相似函数满足一些性质：
-
反身性：f \sim f。
-
传递性：若 f\sim g，g\sim h，则 f \sim h。
-
对称性：若 f\stackrel{\varphi}{\sim}g，则 g\stackrel{\varphi^{-1}}{\sim}f。
-
若 f\sim g，则 f^{(n)} \sim g^{(n)}。
写出来发现里面的 \varphi 全部消掉了。
桥函数法
别急。
不动点法
别急。