7.23 模拟赛 T6 证明
7.23 模拟赛 T6 证明
Sci_qud写在最前
不写这一部分感觉难受所以请输入文字。
学长让我写我拖了半个月说是，然而感觉这场比赛是两千年前打得了。
正文
题目大意：
定义 $f_i$ 表示斐波那契数列第 $i$ 项，求对于任意一个 $x$，是否存在 $i,;j;(i < j)$，使得 $f_x=f_i^2+f_j^2$。如果存在，请输出 $i$ 最小的一组。
引理
引理 1：
$f_i = f_{i-1} + f_{i-2}$（请输入文字）
引理 2：
$f_{m + n} = f_mf_{n+1}+f_{m-1}f_n$
引理 3：
$f_{2n} = f_{n}^2 + 2f_n f_{n-1}$。
证明
不妨分类讨论。
对于奇数
不妨将 $x$ 表示为 $2k + 1$，由引理 2 可知：
$$
\begin{align*}
f_{2k+1} &= f_{k}f_{k+2} + f_{k-1}f_{k+1} \
&= f_k(f_k+f_{k+1}) + f_{k-1}f_{k+1} \
&= f_k^2 + f_kf_{k+1} + f_{k-1}f_{k+1} \
&= f_k^2 + f_{k+1}(f_k+f_{k-1}) \
&= f_k^2 + f_{k+1}^2
\end{align*}
$$
所以，当 $x$ 是奇数时，$f_x = f_k^2 + f_{k+1}^2$ 是一个解，其中 $k = \lfloor\frac{x}{2}\rfloor$。存在性证毕。
接下来我们要证明这个东西的唯一性。
我们考虑将 $k$ 变大而 $k+1$ 变小，或者反过来。
我们有 $f_{k+2}^2 - f_{k+1}^2 > f_{k+1}^2$。
这个结论可以这样证明：
$$
\begin{align*}
f_{k+2}^2 - f_{k+1}^2 &= (f_{k+2}-f_{k+1})(f_{k+2}+f_{k+1}) \
&= f_k (f_{k+3})
\end{align*}
$$
因为 $f_k, f_{k+3}>0$，所以 $f_k(f_{k+3})>0$。并且 $f_{k+1}^2 < f_{k+2}^2 - f_{k+1}^2$。
所以 $f_{k+1}^2$ 的增大量大于 $f_{k}^{2}$，所以不会存在一个比 $k+1$ 更大的数满足条件。
故 $f_n=f_{\lfloor\frac{n}{2}\rfloor}^2+f_{\lfloor\frac{n}{2}\rfloor+1}^2$ 为唯一解。
对于偶数
不妨将 $x$ 表示为 $2k$。
由引理 3 可知：
$f_{2k} = f_{k}^2 + 2f_k f_{k-1}$。
我们现在已经构造出了一个 $f_{k}^2$，则需要考虑 $2f_{k}f_{k-1}$ 是否为某一个斐波那契数的平方。
根据斐波那契数列的性质，对于 $n>3$，我们有 $f_n < 2f_{n-1}$ 和 $f_{n+1} > 2f_{n-1}$。
因此 $2f_{k}f_{k-1}$ 不可能为某一个斐波那契数的平方。
接下来我们考虑 $f_{2k} = f_{k’}^2+f_j^2$ 是否可能存在。
根据引理 3，我们有 $f_{2k} = f_k^2 + 2f_k f_{k-1}$。
由于 $f_k, f_{k-1} > 0$，所以 $f_{2k} > f_k^2$。
并且，我们有 $f_{2k} < f_{k+1}^2$。
证明如下：
$$
\begin{align*}
f_{k+1}^2 - f_{2k} &= f_{k+1}^2 - (f_k^2 + 2f_k f_{k-1}) \
&= (f_k+f_{k-1})^2 - f_k^2 - 2f_k f_{k-1} \
&= f_k^2+2f_kf_{k-1}+f_{k-1}^2 - f_k^2 - 2f_k f_{k-1} \
&= f_{k-1}^2 > 0
\end{align*}
$$
所以 $f_k^2 < f_{2k} < f_{k+1}^2$。
这意味着 $f_{2k}$ 夹在两个相邻斐波那契数的平方之间。
对于任意一个正整数 $k’$，如果 $k’ \ge k+1$，那么 $f_{k’}^2 \ge f_{k+1}^2 > f_{2k}$。所以 $f_{k’}^2$ 加上任何正数都会大于 $f_{2k}$。
如果 $k’ < k$，我们记 $\Delta=f_{2k}-f_{k’}^2$。
因为 $f_{k’}^2 < f_k^2$，所以 $\Delta > f_{2k}-f_k^2 = 2f_k f_{k-1}$。
而 $f_k^2 < \Delta < f_{k+1}^2$。
所以 $\Delta$ 夹在两个相邻斐波那契数的平方之间，因此 $\Delta$ 无法被表示为一个斐波那契数的平方。
故，当 $x$ 为偶数时，不存在满足条件的解。
综上，有
当 $x$ 为偶数时，不存在两个数 $i$ 和 $j$ 使得它们满足 $i>j$ 且 $f_{x}=f_{i}^{2}+f_{j}^{2}$。
当 $x$ 为奇数时，当且仅当 $i=\lfloor\frac{x}{2}\rfloor+1$, $j=\lfloor\frac{x}{2}\rfloor$ 时满足 $i>j$ 且 $f_{x}=f_{i}^{2}+f_{j}^{2}$。
