第4問

\mathbb N_0

を非負整数全体とする。

f:\mathbb N_0\to\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

について

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

を

k

の式で表せ。

ステップ 6/6: 漸化式を解く

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

詳しい解説

漸化式を展開して等比項を和すれば、すべての $k\ge0$ について $a_k=k2^{k-1}-2^k+1$ を得る（この式は $a_0=0$ も与える）。