第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\}

。

第 1/6 步：求 L

上一步下一步

f(2k+1)-f(2k)=k\quad(k>0)

详细分析

由定义得 f(2k+1)−f(2k)=k。因此所有正偶数指标属于 L。又 f(4k+1)=2k+4f(k)=f(4k+2)，且 f(0)=f(1)=0，所以 0 以及所有模 4 同余 1 的数属于 E。