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

。

第 3/6 步：求 G

上一步下一步

f(4k+4)-f(4k+3)=4\bigl(f(k+1)-f(k)\bigr)-(4k+1)<0

详细分析

由递推式，f(4k+4)−f(4k+3)=4(f(k+1)−f(k))−(4k+1)，由前述估计该值为负。因此所有模 4 同余 3 的指标属于 G。三个互不相交的类覆盖全部非负整数，故 L={2k:k>0}，E={0}∪{4k+1:k≥0}，G={4k+3:k≥0}。