第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

の式で表せ。

ステップ 2/6: 隣接差を評価する

f(n+1)-f(n)\le n\quad(n\ge0)

詳しい解説

帰納法で f(n+1)−f(n)≤n を示す。n=2t なら差は t。n=2t+1 なら t に対する帰納法の仮定から 2(f(t+1)−f(t))−t≤t<n を得る。