MathLabs

竞赛数学与解题

函数方程

柯西的四个基本函数方程——加性 f(x+y)=f(x)+f(y)f(x+y)=f(x)+f(y)、指数性 f(x+y)=f(x)f(y)f(x+y)=f(x)f(y)、对数性 f(xy)=f(x)+f(y)f(xy)=f(x)+f(y)、乘性 f(xy)=f(x)f(y)f(xy)=f(x)f(y)——以及求解竞赛函数方程的代换与单射/满射利用技巧。我们证明每个加性的 f:Q→Qf:\mathbb{Q}\to\mathbb{Q} 都具有 f(q)=cqf(q) = cq 的形式,在温和的正则性条件下将其推广到 R\mathbb{R},并说明詹森方程 f(x+y2)=f(x)+f(y)2f\left(\frac{x+y}{2}\right) = \frac{f(x)+f(y)}{2} 可归约为加性情形。应用包括香农熵的公理化推导与指数分布的无记忆性。

直观仅由规则定义的函数

你遇到的大多数函数都由显式公式给出:f(x)=x2f(x)=x^2,f(x)=sin⁡xf(x) = \sin x。函数方程则只通过对所有输入都必须满足的某种关系来描述一个函数——例如"ff 将和变为输出的积"(f(x+y)=f(x)f(y)f(x+y)=f(x)f(y))——你的任务是推导出符合这条单一规则的所有可能的 ff。这是一种奇特的侦探工作:不是去计算答案,而是代入巧妙的特定值(如 x=y=0x=y=0、y=−xy=-x 或 y=1/xy=1/x)来挤出约束,直到函数的整个形状被完全确定。

过原点的线性函数图,展示加性柯西方程的解
柯西加性方程 f(x+y)=f(x)+f(y)f(x+y)=f(x)+f(y) 的解 f(x)=cxf(x)=cx(此处 c=2c=2):拖动查看改变斜率后,过原点的任意线性函数仍保持 f(x+y)=f(x)+f(y)f(x+y)=f(x)+f(y) 成立。

中学柯西的四个方程

定义: 加性、指数性、对数性、乘性

柯西研究了 f:R→Rf:\mathbb{R}\to\mathbb{R}(或适当子定义域)的四个方程:加性 f(x+y)=f(x)+f(y)f(x+y)=f(x)+f(y)、指数性 f(x+y)=f(x)f(y)f(x+y)=f(x)f(y)(将和变为积)、对数性 f(xy)=f(x)+f(y)f(xy)=f(x)+f(y)(将积变为和,定义域限于正实数)、乘性 f(xy)=f(x)f(y)f(xy)=f(x)f(y)。每一对通过 exp⁡\exp/log⁡\log 相连:若 gg 解加性方程,则 f=exp⁡∘gf = \exp \circ g 解指数方程;若 ff 解乘性方程,则 g=log⁡∘fg = \log \circ f(在正实数上)解加性方程。

f(x+y)=f(x)+f(y)⟺ f=exp⁡∘g f(x+y)=f(x)f(y)f(x+y)=f(x)+f(y) \quad \Longleftrightarrow_{\ f=\exp\circ g\ } \quad f(x+y)=f(x)f(y)

加性方程是主导情形:另外三个方程的每个解都通过 exp⁡\exp/log⁡\log 代换(在满足所需的正/非零条件下)归约到它,这就是为什么下面直接针对加性方程证明的定理1,实际上悄悄解出了全部四个方程。

f(x+y2)=f(x)+f(y)2f\left(\frac{x+y}{2}\right) = \frac{f(x)+f(y)}{2}
柯西的四个方程
方程定义域一般解(正则情形)
加性R→R\mathbb{R}\to\mathbb{R}f(x)=cxf(x)=cx
指数性R→R>0\mathbb{R}\to\mathbb{R}_{>0}f(x)=axf(x)=a^x
对数性R>0→R\mathbb{R}_{>0}\to\mathbb{R}f(x)=clog⁡xf(x)=c\log x
乘性R>0→R\mathbb{R}_{>0}\to\mathbb{R}f(x)=xcf(x)=x^c

大学求解柯西方程与詹森方程

若 f:Q→Qf:\mathbb{Q}\to\mathbb{Q} 对所有 x,y∈Qx,y\in\mathbb{Q} 满足 f(x+y)=f(x)+f(y)f(x+y)=f(x)+f(y),则对所有 q∈Qq\in\mathbb{Q} 有 f(q)=cqf(q) = cq,其中 c=f(1)c=f(1)。若进一步 f:R→Rf:\mathbb{R}\to\mathbb{R} 连续(或单调,或在某区间上有界),则同样的结论 f(x)=cxf(x)=cx 对所有 x∈Rx\in\mathbb{R} 成立。

为什么成立?

这个定理是整个函数方程工具箱的基础:它表明一个纯代数关系,在 Q\mathbb{Q} 上无需任何连续性假设,就已经完全确定了 ff——而在 R\mathbb{R} 上,若没有任何正则性假设,则存在极其病态的非线性解(通过选择公理构造的哈默尔基建立),因此正则性假设并非技术细节,而是不可或缺的。

证明

**第1步:确定 f(0)f(0)。** 在 f(x+y)=f(x)+f(y)f(x+y)=f(x)+f(y) 中令 x=y=0x=y=0:f(0)=f(0)+f(0)f(0)=f(0)+f(0),故 f(0)=0f(0)=0。

第2步:推广到正整数。 对正整数 nn,令 x=(n−1)x=(n-1)(或归纳):f(n⋅1)=f((n−1)⋅1+1)=f((n−1)⋅1)+f(1)f(n\cdot 1) = f((n-1)\cdot 1 + 1) = f((n-1)\cdot 1) + f(1)。对 nn 归纳,得对每个正整数 nn,f(n)=nf(1)f(n) = n f(1)(基础情形 n=1n=1 平凡,归纳步骤如上应用)。

第3步:推广到负整数。 在 f(x+y)=f(x)+f(y)f(x+y)=f(x)+f(y) 中令 y=−xy=-x:f(0)=f(x)+f(−x)f(0) = f(x) + f(-x),又 f(0)=0f(0)=0,故 f(−x)=−f(x)f(-x) = -f(x)。结合第2步,对每个整数 nn(正、负或零)有 f(n)=nf(1)f(n) = n f(1),记 c=f(1)c = f(1)。

第4步:推广到有理数。 设 q=p/rq = p/r,p∈Zp\in\mathbb{Z},r∈Z>0r\in\mathbb{Z}_{>0}。由于 r⋅q=pr \cdot q = p(在重复加法下作为整数,即 q+q+⋯+qq + q + \dots + q(rr 次)=p= p),对被求值 rr 次的函数应用第2/3步的整数情形,得 f(rq)=rf(q)f(rq) = r f(q)(用第2步同样的归纳论证,现取 x=qx=q)。但 rq=prq = p,故 f(p)=rf(q)f(p) = r f(q),即 cp=rf(q)cp = r f(q),即 f(q)=c⋅pr=cqf(q) = c \cdot \frac{p}{r} = cq。

第5步:总结有理数情形。 这表明对每个 q∈Qq \in \mathbb{Q} 都有 f(q)=cqf(q) = cq,其中 c=f(1)c = f(1)——Q\mathbb{Q} 上的整个函数由其在单一点的取值确定。

**第6步:在连续性下推广到 R\mathbb{R}。** 现设 f:R→Rf:\mathbb{R}\to\mathbb{R} 是加性的,且哪怕只在一点连续(处处连续随即由加性得出:若在 00 处连续,则当 h→0h\to 0 时 f(x+h)−f(x)=f(h)→0f(x+h)-f(x) = f(h) \to 0)。对任意实数 xx,取有理数列 qn→xq_n \to x。由第1–5步,f(qn)=cqnf(q_n) = c q_n。连续性给出 f(x)=lim⁡nf(qn)=lim⁡ncqn=cxf(x) = \lim_n f(q_n) = \lim_n c q_n = cx。

**第7步:在单调性或局部有界性下推广到 R\mathbb{R}(概述)。** 若 ff 单调,则对任意实数 xx,取有理数 q1<x<q2q_1 < x < q_2 夹逼,单调性迫使 cq1≤f(x)≤cq2cq_1 \le f(x) \le cq_2(若 c>0c>0;若 c<0c<0 则反向),令 q1,q2→xq_1,q_2\to x,同样的夹逼确定 f(x)=cxf(x)=cx。若改为 ff 在某区间 II 上有界,则可证明 ff 在 00 附近有界(利用加性平移区间),然后对固定的 xx,当 n→∞n\to\infty 时 f(x/n)→0f(x/n)\to 0 迫使在 00 处连续,从而归约到第6步。在这三种正则性情形(连续、单调、区间上有界)中,结论相同:对所有 x∈Rx\in\mathbb{R},f(x)=cxf(x)=cx。

若 f:R→Rf:\mathbb{R}\to\mathbb{R} 对所有 x,y∈Rx,y\in\mathbb{R} 满足詹森方程 f(x+y2)=f(x)+f(y)2f\left(\frac{x+y}{2}\right) = \frac{f(x)+f(y)}{2},则 g(x):=f(x)−f(0)g(x) := f(x)-f(0) 是加性的(满足 f(x+y)=f(x)+f(y)f(x+y)=f(x)+f(y)),故在连续性(或单调性,或区间上有界性)下,存在常数 cc 使 f(x)=cx+f(0)f(x) = cx + f(0)。

为什么成立?

这表明看似纯粹关于中点与平均值的詹森方程,实际上是伪装过的柯西加性方程,因此定理1的全部机制(包括病态的非正则解及排除它们的正则性条件)都会自动迁移过来。

证明

**第1步:定义 gg 并验证 g(0)=0g(0)=0。** 设 g(x)=f(x)−f(0)g(x) = f(x) - f(0)。则 g(0)=f(0)−f(0)=0g(0) = f(0)-f(0) = 0。

**第2步:用 gg 重写詹森方程。** 将 f=g+f(0)f = g + f(0) 代入 f(x+y2)=f(x)+f(y)2f\left(\frac{x+y}{2}\right) = \frac{f(x)+f(y)}{2},得 g(x+y2)+f(0)=g(x)+f(0)+g(y)+f(0)2=g(x)+g(y)2+f(0)g\left(\frac{x+y}{2}\right) + f(0) = \frac{g(x)+f(0)+g(y)+f(0)}{2} = \frac{g(x)+g(y)}{2} + f(0)。f(0)f(0) 项相消,留下 g(x+y2)=g(x)+g(y)2g\left(\frac{x+y}{2}\right) = \frac{g(x)+g(y)}{2}——gg 满足完全相同的詹森方程。

第3步:推导减半恒等式。 在 gg 的方程中令 y=0y=0:g(x2)=g(x)+g(0)2=g(x)2g\left(\frac{x}{2}\right) = \frac{g(x)+g(0)}{2} = \frac{g(x)}{2}(利用第1步的 g(0)=0g(0)=0)。故对每个 xx 有 g(x/2)=g(x)/2g(x/2) = g(x)/2,等价地对每个 uu 有 g(2u)=2g(u)g(2u) = 2g(u)(代入 u=x/2u=x/2)。

**第4步:将 gg 的詹森方程转化为加性。** 对任意 x,y∈Rx,y\in\mathbb{R},对 (x,y)(x,y) 应用 gg 的詹森方程:g(x+y2)=g(x)+g(y)2g\left(\frac{x+y}{2}\right) = \frac{g(x)+g(y)}{2}。由第3步取 u=x+yu = x+y,左边等于 g(x+y)/2g(x+y)/2(因为 x+y2\frac{x+y}{2} 是 x+yx+y 的减半)。故 g(x+y)2=g(x)+g(y)2\frac{g(x+y)}{2} = \frac{g(x)+g(y)}{2},两边乘以 22:g(x+y)=g(x)+g(y)g(x+y) = g(x)+g(y)。

第5步:结论。 这正是应用于 gg 的加性柯西方程 f(x+y)=f(x)+f(y)f(x+y)=f(x)+f(y)。由定理1,若 gg(等价地 ff,因两者仅相差常数 f(0)f(0))连续、单调或在某区间上有界,则存在常数 c=g(1)=f(1)−f(0)c=g(1)=f(1)-f(0) 使 g(x)=cxg(x) = cx。代回得 f(x)=g(x)+f(0)=cx+f(0)f(x) = g(x) + f(0) = cx + f(0),即詹森方程的一般正则解——一个仿射(不必是线性)函数。

进阶实际应用与典型例题

函数方程不仅仅是谜题:香农关于熵的公理化推导假设两个概率为 pp 和 qq 的独立事件的不确定性满足 H(pq)=H(p)+H(q)H(pq)=H(p)+H(q),这正是柯西的对数方程,迫使 H(p)=−klog⁡pH(p) = -k\log p(对某常数 k>0k>0)——正是这一个函数方程加上连续性,就是熵必须是对数形式的原因。在概率论中,等待时间的无记忆性(无论你已经等了0分钟还是20分钟,公交车在接下来5分钟内到达的可能性都相同)正是应用于生存函数的柯西指数方程,迫使指数分布成为唯一的连续无记忆分布。

例题: 推导香农熵的对数形式

设概率为 pp 的单一事件的不确定性函数 H:(0,1]→R≥0H:(0,1]\to\mathbb{R}_{\ge 0},对概率为 p,qp,q 的独立事件满足 H(pq)=H(p)+H(q)H(pq) = H(p)+H(q),且 HH 连续。证明对某常数 k≥0k \ge 0,有 H(p)=−klog⁡pH(p) = -k\log p。

解答

第1步:对 u,v≥0u,v \ge 0 代入 p=e−up = e^{-u},q=e−vq=e^{-v},并定义 G(u):=H(e−u)G(u) := H(e^{-u})。则 H(pq)=H(p)+H(q)H(pq) = H(p)+H(q) 变为 H(e−ue−v)=H(e−u)+H(e−v)H(e^{-u}e^{-v}) = H(e^{-u})+H(e^{-v}),即 H(e−(u+v))=G(u)+G(v)H(e^{-(u+v)}) = G(u)+G(v),即 G(u+v)=G(u)+G(v)G(u+v) = G(u)+G(v)——这是 GG 在 [0,∞)[0,\infty) 上的柯西加性方程。

第2步:因为 HH 连续且 p↦e−up\mapsto e^{-u} 连续,故 GG 连续。由定理1的连续情形,存在常数 k=G(1)=H(e−1)k = G(1) = H(e^{-1}) 使 G(u)=kuG(u) = ku。

第3步:因为 H≥0H\ge 0(不确定性非负)且概率 p≤1p\le 1 对应 u=−log⁡p≥0u = -\log p \ge 0,我们需要对所有 u≥0u\ge 0 有 G(u)=ku≥0G(u)=ku\ge 0,这迫使 k≥0k \ge 0。

第4步:还原代换:H(p)=H(e−u)=G(u)=ku=k(−log⁡p)=−klog⁡pH(p) = H(e^{-u}) = G(u) = ku = k(-\log p) = -k\log p,即为所求。

例题: 无记忆性迫使指数分布

设 S(t)=P(X>t)S(t) = P(X>t) 是连续随机变量 X≥0X\ge 0 的生存函数,并设 XX 无记忆:对所有 s,t≥0s,t\ge 0,P(X>s+t∣X>t)=P(X>s)P(X>s+t \mid X>t) = P(X>s)。证明对某 λ>0\lambda>0,S(t)=e−λtS(t) = e^{-\lambda t},即 XX 服从指数分布。

解答

第1步:用条件概率的定义重写条件概率:P(X>s+t∣X>t)=P(X>s+t, X>t)P(X>t)=P(X>s+t)P(X>t)=S(s+t)S(t)P(X>s+t\mid X>t) = \frac{P(X>s+t,\, X>t)}{P(X>t)} = \frac{P(X>s+t)}{P(X>t)} = \frac{S(s+t)}{S(t)}(利用对 s≥0s\ge 0 有 X>s+t⇒X>tX>s+t \Rightarrow X>t,故联合事件正是 X>s+tX>s+t)。

第2步:无记忆假设 P(X>s+t∣X>t)=P(X>s)P(X>s+t\mid X>t) = P(X>s) 变为 S(s+t)S(t)=S(s)\frac{S(s+t)}{S(t)} = S(s),即对所有 s,t≥0s,t\ge 0 有 S(s+t)=S(s)S(t)S(s+t) = S(s)S(t)——这正是 SS 的柯西乘性(指数化)方程。

第3步:SS 单调(非增,因为是生存函数:P(X>t)P(X>t) 随 tt 增大而减小)且连续(因为 XX 是连续随机变量),又 0≤S(t)≤10 \le S(t) \le 1 故 SS 有界。由定理1的正则性推广(应用于 g(t):=log⁡S(t)g(t) := \log S(t),通过对第2步取对数满足 g(s+t)=g(s)+g(t)g(s+t) = g(s)+g(t),且由于 log⁡\log 单调、SS 亦然,故其单调/连续),存在常数 λ\lambda 使 g(t)=−λtg(t) = -\lambda t(记 −λ=g(1)=log⁡S(1)-\lambda = g(1) = \log S(1))。

第4步:还原对数:S(t)=eg(t)=e−λtS(t) = e^{g(t)} = e^{-\lambda t}。因为 SS 非增且 S(0)=1S(0)=1,需要 λ≥0\lambda \ge 0;若 λ=0\lambda=0 则 S≡1S\equiv 1,不是有效的(非退化的)概率分布,故 λ>0\lambda>0。这正是速率为 λ\lambda 的指数分布的生存函数,证明了无记忆性迫使 XX 服从指数分布。

对满足所有有理数上 f(x+y)=f(x)+f(y)f(x+y)=f(x)+f(y) 的 f:Q→Qf:\mathbb{Q}\to\mathbb{Q},用 c=f(1)c=f(1) 表示 f(3/2)f(3/2) 是什么?

为什么定理1对 Q\mathbb{Q} 的证明在没有任何额外假设(连续性、单调性或有界性)下无法推广到 R\mathbb{R}?

在证明詹森方程归约为柯西方程时,使用了什么代换 g(x)g(x)?

连续等待时间分布的无记忆性对生存函数 S(t)=P(X>t)S(t)=P(X>t)转化为哪个柯西方程?

参考文献

  1. Christopher G. Small (2007). Functional Equations and How to Solve Them
  2. Thomas M. Cover, Joy A. Thomas (2006). Elements of Information Theory
  3. D. H. Hyers (1941). On the Stability of the Linear Functional Equation