递推序列$f(n)$模5的通项公式求解（$n \geq 4$）

嘿，你的思路方向完全没问题，猜测的结论也是对的——当$n \geq 4$时，$f(n) \equiv 1 \pmod{5}$，只是归纳步骤的切入点需要调整下，我来帮你理清楚：

首先明确问题和前几项的计算：

给定递推规则 $f(n+1)=2^{f(n)}$（$n \geq 1$），初始值 $f(0)=2$，我们需要求$n \geq 4$时$f(n) \pmod{5}$的结果。

先手动算出前几项的模5结果，和你做的一致：

• $f(0)=2$
• $f(1)=2^{f(0)}=22=4 \equiv -1 \pmod{5}$
• $f(2)=2^{f(1)}=24=16 \equiv 1 \pmod{5}$
• $f(3)=2^{f(2)}=2{16}$，因为$2^4 \equiv 1 \pmod{5}$，所以$2^{16}=(24)^4 \equiv 1^4=1 \pmod{5}$

接下来用数学归纳法严谨证明当$n \geq 3$时，$f(n) \equiv 1 \pmod{5}$（自然$n \geq 4$也满足）：

第一步：基例验证 #

当$n=3$时，我们已经算出$f(3)=2^{16} \equiv 1 \pmod{5}$，同时注意到$f(3)=2^{16}$是$22$的倍数，即$f(3) \equiv 0 \pmod{4}$——这个模4的结论是关键，因为后续要用到费马小定理。

第二步：归纳假设 #

假设对于某个整数$k \geq 3$，满足两个条件：

1. $f(k) \equiv 1 \pmod{5}$
2. $f(k) \equiv 0 \pmod{4}$

第三步：归纳推导 #

我们需要证明$f(k+1)=2^{f(k)} \equiv 1 \pmod{5}$，同时保持$f(k+1) \equiv 0 \pmod{4}$：

• 对于模5的计算：根据费马小定理，因为2和5互质，所以$2^4 \equiv 1 \pmod{5}$。由归纳假设，$f(k) \equiv 0 \pmod{4}$，即$f(k)=4t$（$t$为正整数），那么$2^{f(k)}=2{4t}=(2⁴⁾t=16^t$。而$16 \equiv 1 \pmod{5}$，所以$16^t \equiv 1^t=1 \pmod{5}$，即$f(k+1) \equiv 1 \pmod{5}$。
• 对于模4的计算：$f(k+1)=2^{f(k)}$，因为$f(k) \geq f(3)=65536 \geq 2$，所以$2^{f(k)}$是$22$的倍数，必然满足$f(k+1) \equiv 0 \pmod{4}$，为下一次归纳做好准备。

这样通过归纳法，我们就能确定：对于所有$n \geq 3$，$f(n) \equiv 1 \pmod{5}$，那么当$n \geq 4$时，自然也有$f(n) \equiv 1 \pmod{5}$。

备注：内容来源于stack exchange，提问作者IntegrateThis