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

。

第 5/6 步：得到递推式

上一步下一步

a_k=2a_{k-1}+2^{k-1}-1

详细分析

计算 $2^k-1$ 处的 $f$ 得 $a_k=2a_{k-1}+2^{k-1}-1$ 。该递推对 $k\ge1$ 成立，初值为 $a_0=a_1=0$ 、 $a_2=1$ 。