Tongrui 5.5 数列
Published:
Ad-hoc 专场？？
Example 5.26 MPFG 2025 #17 (Ad-hoc)
\[y_n = \begin{cases} 0 & n = 0 \\ 451 & n = 1 \\ 1560 y_{n-1} - 901^2 y_{n-2} & n \ge 2 \\ \end{cases}\]找到最小正整数 $n$ 使得 $y_n < 0$ 且 $y_{n+1} > 0$。
提示：
- $\frac {1560} 2 = 780$，而 $780^2 + 451^2 = 901^2$。
- $\frac {451} {901} \approx \frac 1 2$。
换元 $z_n = \frac {y_n} {901^n}$
\[z_n = 2 \times \frac {780} {901} \times z_{n-1} - z_{n-2}\]联想到
\[\sin(nA) = 2 \cos A \sin((n-1)A) - \sin((n-2)A)\]设
\[A = \arccos \frac {780} {901}\]则我们发现恰好有
\[z_1 = \frac {451} {901} = \sin A\]于是换元 $z_n = \sin(nA)$（$A \in (0, \frac \pi 2)$）。因此我们就是要解
\[\begin{cases} z_n = \sin(nA) < 0 \\ z_{n+1} = \sin((n+1)A) > 0 \\ \end{cases}\]答案即为
\[n = \left\lfloor \frac {2 \pi} A \right\rfloor = \left\lfloor \frac {2 \pi} {\arcsin \frac {451} {901}} \right\rfloor = \boxed{11}\]这里的估算怎么做？
\[\frac {2 \pi} {\arcsin \frac {451} {901}} \lessapprox \frac {2 \pi} {\arcsin \frac 1 2} = 12\]那它是不是大于 $11$ 呢？
\[\arcsin \frac {451} {901} \overset{?}{<} \frac {2 \pi} {11}\]即
\[\sin \frac {2 \pi} {11} \overset{?}{>} \frac {451} {901}\]（我们希望结果很靠近 $12$，因此证明它大于 $11$ 的这个不等式是比较松的，放缩可以比较随便）
我们要找一个 $\sin \frac {2 \pi} {11}$ 的下界。注意到 $\sin$ 在 $(0, \pi)$ 是一个上凸的函数，作一条割线可以给出下界。
割线的一端毫无疑问地选取离得很近的 $\frac {2 \pi} {12}$，另一端不妨取 $\frac \pi 6$ 比较好算。
\[\begin{aligned} & \sin \frac {2 \pi} {11} \\ =& \sin\left( \frac {21} {22} \times \frac \pi 6 + \frac 1 {22} \times \frac \pi 2 \right) \\ >& \frac {21} {22} \sin \frac \pi 6 + \frac 1 {22} \sin \frac \pi 2 \\ =& \frac {23} {44} > \frac {451} {901} \end{aligned}\]证毕。
Example 5.27 AIME I 2006 #15 (Hard, Ad-hoc)
实数数列 $x$ 满足
- $x_0 = 0$
- $\lvert x_n \rvert = \lvert x_{n-1} + 3 \rvert$
求
\[\min \left\lvert \sum_{i=1}^{2006} x_i \right\rvert\]
$\lvert a \rvert = \lvert b \rvert$ 等价于 $a^2 = b^2$。
\[\sum_{i=1}^n x_i^2 = \sum_{i=0}^{n-1} (x_i + 3)^2 = \sum_{i=0}^{n-1} (x_i^2 + 6 x_i + 9)\] \[\sum_{i=0}^{n-1} x_i = \frac {x_n^2 - 9n} 6\] \[\sum_{i=1}^n x_i = \frac {x_{n+1}^2 - 9(n+1)} 6 = \frac {(x_n + 3)^2 - 9n - 9} 6\] \[\lvert \sum_{i=1}^{2006} x_i \rvert \ge \lvert \frac {(x_{2006} + 3)^2 - 9 \times 2007} 6 \rvert\]使这个值最小的 $x_{2006} = 3 \times 44$，此时原式取到 $27$。
构造方案：
- $x_1 = -3, x_2 = 0, x_3 = -3, x_4 = 0, \cdots$
- $x_{1962} = 0$ 从这之后一直都 $+3$，直到 $x_{2006} = 3 \times 44$。
因此 $\boxed{27}$ 是合法的答案。
Example 5.28 AIME I 2007 #14 (Hard)
数列 $a$ 满足：
- $a_0 = a_1 = 3$
- $a_{n+1} a_{n-1} = a_n^2 + 2007$
求
\[\left\lfloor \frac {a_{2006}^2 + a_{2007}^2} {a_{2006} a_{2007}} \right\rfloor\]
首先 $a_{n+1} a_{n-1} - a_n^2 = 2007$ 这个条件也太像 Cassini 恒等式了。
\[\det \begin{bmatrix} a_{n+1} & a_n \\ a_n & a_{n-1} \\ \end{bmatrix} = 2007\]不妨猜测 $a$ 和 Fibonacci 数列一样是一个二阶线性递推：
\[\begin{bmatrix} a_{n+1} & a_n \\ a_n & a_{n-1} \\ \end{bmatrix} = \begin{bmatrix} \alpha & \beta \\ 1 & 0 \\ \end{bmatrix} \begin{bmatrix} a_n & a_{n-1} \\ a_{n-1} & a_{n-2} \\ \end{bmatrix}\]等式两边同时取 $\det$：
\[\det \begin{bmatrix} \alpha & \beta \\ 1 & 0 \\ \end{bmatrix} = 1\]得 $\beta = -1$。与此同时，算出 $a_2 = 672$ 就能得到 $\alpha = 225$。
\[a_n = \begin{cases} 3 & n = 0 \lor n = 1 \\ 225 a_{n-1} - a_{n-2} & n \ge 2 \\ \end{cases}\]$a$ 已经求出来了，考虑答案怎么算。
「相邻两项比值」的差在通分后会出现 Cassini，利用这一点化简。
\[\begin{aligned} & \frac {a_n^2 + a_{n+1}^2} {a_n a_{n+1}} \\ =& \frac {a_n} {a_{n+1}} + \frac {a_{n+1}} {a_n} \\ =& \frac {a_n} {a_{n+1}} + \frac {225 a_n - a_{n-1}} {a_n} \\ =& 255 + \frac {a_n^2 - a_{n+1} a_{n-1}} {a_{n+1} a_n} \\ =& 255 - \frac {2007} {a_n a_{n+1}} \end{aligned}\]在 $n = 2006$ 时答案为 $\boxed{224}$。
Example 5.31 AIME II 2025 #13 (Hard, Ad-hoc)
有理数数列 $x$ 满足：
- $x_1 = \frac {25} {11}$
- $x_n = \frac 1 3 \left( x_{n-1} + \frac 1 {x_{n-1}} - 1 \right)$
令 $x_n = \frac {p_n} {q_n}$。求 $(p_{2025} + q_{2025}) \bmod 1000$。
首先凭借强大的注意力猜出
\[\begin{cases} p_k = \frac {p_{k-1}^2 + q_{k-1}^2 - p_{k-1} q_{k-1}} 3 \\ q_k = p_{k-1} q_{k-1} \\ \end{cases}\]证明是简单的。
然后注意到
\[(p_k + q_k) = \frac 1 3 (p_{k-1} + q_{k-1})^2\]迭代后可得
\[p_n + q_n = 3 \left( \frac {p_1 + q_1} 3 \right)^{2^{n-1}}\]因此答案在 $\bmod 1000$ 前即为
\[3 \times 12^{2^{2024}}\]CRT 后 Euler 定理降幂得答案为 $\boxed{248}$。