MathLabs

第4题

考虑函数 f:N0→N0f:\mathbb N_0\to\mathbb N_0，其中 N0\mathbb N_0 是所有非负整数的集合，定义为 f(0)=0f(0)=0，且对所有 n≥0n\ge0 有 f(2n)=2f(n)f(2n)=2f(n)、f(2n+1)=n+2f(n)f(2n+1)=n+2f(n)。(a) 求三集合 L={n∣f(n)<f(n+1)}L=\{n\mid f(n)<f(n+1)\}、E={n∣f(n)=f(n+1)}E=\{n\mid f(n)=f(n+1)\} 和 G={n∣f(n)>f(n+1)}G=\{n\mid f(n)>f(n+1)\}。(b) 对每个 k≥0k\ge0，用 kk 表示 ak=max⁡{f(n):0≤n≤2k}a_k=\max\{f(n):0\le n\le2^k\}。
第 4/6 步：确定最大值位置
上一步下一步
ak=f(2k−1)(k≥2)a_k=f(2^k-1)\quad(k\ge2)
详细分析

当 k=2k=2 时显然。假设对 k−1k-1 成立。在 0≤n≤2k0\le n\le2^k 的上半段，对偶数 n=2tn=2t，递推给出 f(n)≤2ak−1f(n)\le2a_{k-1}；对奇数 n=2t+1n=2t+1，f(n)≤2k−1−1+2ak−1f(n)\le2^{k-1}-1+2a_{k-1}。两者均不超过 f(2k−1)=2k−1−1+2f(2k−1−1)f(2^k-1)=2^{k-1}-1+2f(2^{k-1}-1)，故最大值在 2k−12^k-1 处取得。