隐式递推数列的估界证明

题型说明

• 常见形状：给一个把相邻两项绑在一起的方程，例如 $$a_{n+1}^{2}+a_{n+1}-1=a_{n}^{2},\qquad a_{1}=0,\ a_{n}\geqslant 0,$$ 然后连问三件事：$\{a_{n}\}$ 单调吗、前 $n$ 项和 $S_{n}$ 有没有下界、由各项做出来的连乘和有没有上界。
• 和「求通项」型递推的区别：那类题的递推能整理成等差、等比或可构造的新数列， 通项一写出来题就化成求和；这类题通项根本写不出来（就算解出 $a_{n+1}$ 关于 $a_{n}$ 的显式表达式， 迭代起来也没有闭式）。所以递推式本身就是全部的信息，三问都只能从它出发。

三步

1. 先把项本身夹住。 几乎所有这类题的第一件事都是定出一段区间 $[m,M]$，使 $a_{n}$ 永远落在里面。 办法是把递推方程看成关于 $a_{n+1}$ 的方程，用「左边这个函数是增的」把 $a_{n+1}$ 的位置卡出来， 再对 $n$ 做一次归纳。这条界是后面两问的地基，不要等到用上了才回头补。
2. 把方程改写成需要的形状。 要什么就凑什么：

   要证的东西	把递推式改写成	然后
   单调性	相邻两项的差（或差的符号）	直接判号，或做一次归纳
   和的界	$1-a_{k}$、$a_{k}-c$ 这类可对消的表达式	累加，中间项全消
   连乘的界	相邻两项的比	累乘，或换成一个等比的上界

3. 算出来的恒等式优先于放缩。 如果第 2 步凑出的是等式（例如 $S_{n}=n-1-a_{n}^{2}$）， 那就先把它写出来，再把第 1 步的界代进去——一步到位，且不会有「放松了多少」的顾虑。 只有凑不出等式时才退而求其次去放缩。

关口

• 和的界要分清方向。 每一项的上界只能推出和的上界；要证和的下界， 要么先把和算成恒等式，要么去叠缩 $1-a_{k}$ 这种「缺口」量。
• 一条界从第几项起成立，要写清楚。 首项常常是特例（$a_{1}=0$ 就不满足 $a_{n}>\frac{1}{2}$）， 求和时前几项得单独留着。
• 放缩要「刚好够用」。 题目给的界（$3$、$2$）往往正是某个自然的粗放缩恰好能到的值； 放得比它更松就够不着，放得过紧又常常算不动。