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

。

第 6/6 步：展开递推式

上一步下一步

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

详细分析

展开递推式并求等比项之和，得到对所有 $k\ge0$ ， $a_k=k2^{k-1}-2^k+1$ （该式也给出 $a_0=0$ ）。