第4题

考虑函数

f:\mathbb N_0\to\mathbb N_0

，其中

\mathbb N_0

是所有非负整数的集合，定义为

f(0)=0

，且对所有

n\ge0

有

f(2n)=2f(n)

、

f(2n+1)=n+2f(n)

。(a) 求三集合

L=\{n\mid f(n)<f(n+1)\}

、

E=\{n\mid f(n)=f(n+1)\}

和

G=\{n\mid f(n)>f(n+1)\}

。(b) 对每个

k\ge0

，用

k

表示

a_k=\max\{f(n):0\le n\le2^k\}

。

第 2/6 步：估计相邻差

上一步下一步

f(n+1)-f(n)\le n\quad(n\ge0)

详细分析

用归纳法证明 f(n+1)−f(n)≤n。当 n=2t 时差为 t；当 n=2t+1 时，对 t 应用归纳假设得 2(f(t+1)−f(t))−t≤t<n。