含交换性的函数方程证明：f(n)=n（定义域为非负整数）

我来一步步拆解这个函数方程的证明过程，先从已知条件和你的初步推导入手，再补全关键的后续步骤：

一、明确已知条件 #

我们有两个从非负整数集到自身的函数 (f, g: \mathbb{N}_0 \mapsto \mathbb{N}_0)，满足：

• 初始约束：(f(1) > 0)，(g(1) > 0)
• 交换性：对任意 (n \in \mathbb{N}_0)，(f(g(n)) = g(f(n)))
• 核心函数方程：
  1. 对任意 (m,n \in \mathbb{N}_0)，(f(m^2 + g(n)) = f(m)^2 + g(n))
  2. 对任意 (m,n \in \mathbb{N}_0)，(g(m^2 + f(n)) = g(m)^2 + f(n))

二、初步推导与关键结论：(f = g) #

按照你的思路，先令 (m = n = 0) 代入两个核心方程：

1. 代入方程1得：(f(g(0)) = f(0)^2 + g(0))
2. 代入方程2得：(g(f(0)) = g(0)^2 + f(0))

结合交换性 (f(g(0)) = g(f(0)))，联立两式可得：
$$f(0)^2 + g(0) = g(0)^2 + f(0)$$
整理后：
$$f(0)(f(0)-1) = g(0)(g(0)-1)$$

分析等式的可能解 #

非负整数中满足 (k(k-1) = l(l-1)) 的情况只有两种：

• 情况1：(f(0) = g(0))
• 情况2：({f(0), g(0)} = {0, 1})

排除情况2：假设 (f(0)=1, g(0)=0)，令 (n=1) 结合交换性可得 (g(f(1))=f(g(1)))，再代入 (m=0) 的方程1：(f(g(1))=f(0)^2 +g(1)=1+g(1))；代入 (m=0) 的方程2：(g(f(1))=g(0)^2 +f(1)=0+f(1))。联立得 (f(1)=1+g(1))，但令 (m=1,n=0) 代入方程2：(g(1+f(0))=g(2)=g(1)^2 +f(0)=g(1)^2+1)，同时由 (g(1)>0) 可知 (g(1)≥1)，则 (f(1)=1+g(1)≥2)，再代入交换性 (f(g(1))=g(f(1)))，左边 (f(g(1))≥f(1)≥2)，右边 (g(f(1))=g(1+g(1)))，若 (g(1)=1)，右边 (g(2)=1^2+1=2)，左边 (f(1)=2)，但再令 (m=1,n=1) 代入方程1：(f(1+g(1))=f(2)=f(1)^2 +g(1)=4+1=5)，而 (g(f(1))=g(2)=2)，与交换性 (f(g(1))=g(f(1)))（即 (f(1)=g(2))）矛盾。同理 (f(0)=0,g(0)=1) 也会导出矛盾，因此情况2不成立，只能是情况1：(f(0)=g(0))。

接下来，令 (m=0) 代入方程1：(f(g(n))=f(0)^2 +g(n))；代入方程2：(g(f(n))=g(0)^2 +f(n))。结合交换性 (f(g(n))=g(f(n))) 以及 (f(0)=g(0))，可得：
$$f(0)^2 +g(n) = f(0)^2 +f(n)$$
消去 (f(0)^2) 后，得到 对任意 (n \in \mathbb{N}_0)，(f(n)=g(n))。这是整个证明的关键转折点！

三、简化条件并证明 (f(n)=n) #

现在我们知道 (f=g)，条件简化为：

• (f(1)>0)
• 对任意 (m,n \in \mathbb{N}_0)，(f(m^2 + f(n))=f(m)^2 +f(n))
• 交换性自动满足（(f(f(n))=f(f(n)))）

步骤1：证明 (f(0)=0) #

设 (f(0)=c)，令 (m=0) 代入简化后的方程：(f(f(n))=c^2 +f(n))。
再令 (n=0)：(f(c)=c^2 +c)。
令 (m=c)，(n=0)：(f(c^2 +c)=f(c)^2 +c=(c^2 +c)^2 +c)。
但另一方面，(f(f(c))=c^2 +f(c)=c^2 +c^2 +c=2c^2 +c)，而 (f(f(c))=f(c^2 +c))，所以：
$$(c^2 +c)^2 +c = 2c^2 +c$$
化简得：
$$(c^2 +c)^2 = 2c^2$$
若 (c≠0)，两边除以 (c^2) 得 ((c+1)^2=2)，无整数解，因此 (c=0)，即 (f(0)=0)。

此时，(f(f(n))=0 +f(n)=f(n))，说明 (f) 是幂等函数（即 (f) 的值域中的元素都是不动点）。

步骤2：证明 (f(1)=1) #

令 (m=1, n=0) 代入简化后的方程：
$$f(1^2 +0)=f(1)^2 +0$$
即 (f(1)=f(1)^2)，结合 (f(1)>0)，可得 (f(1)=1)。

步骤3：数学归纳法证明所有 (n) 都是不动点 #

• 基例：(n=0) 时 (f(0)=0)，(n=1) 时 (f(1)=1)，成立。
• 归纳假设：假设对所有 (t \leq k)（(k \geq1)），都有 (f(t)=t)。
• 归纳步骤：证明 (f(k+1)=k+1)。
  • 若 (k+1) 是平方数，设 (k+1=m^2)，令 (m=m, n=0) 代入方程：(f(m^2)=f(m)2)。由归纳假设 (f(m)=m)（因为 (m \leq k)），所以 (f(m^2)=m2=k+1)，即 (f(k+1)=k+1)。
  • 若 (k+1) 不是平方数，则存在正整数 (m) 使得 (m^2 <k+1 <(m+1)^2)，即 (k+1=m^2 +r)，其中 (1 \leq r \leq 2m)。由于 (m^2 \geq1)，所以 (r=k+1 -m^2 \leq k)，由归纳假设 (f(r)=r)。代入方程：
    $$f(k+1)=f(m^2 +r)=f(m^2 +f(r))=f(m)^2 +f(r)$$
    再由归纳假设 (f(m)=m)，可得：
    $$f(k+1)=m^2 +r=k+1$$

综上，对所有非负整数 (n)，都有 (f(n)=n)。

内容的提问来源于stack exchange，提问作者QFTheorist