第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

の式で表せ。

ステップ 1/6: L を求める

f(2k+1)-f(2k)=k\quad(k>0)

詳しい解説

定義から f(2k+1)−f(2k)=k である。従って正の偶数添字はすべて L に属する。また f(4k+1)=2k+4f(k)=f(4k+2)、f(0)=f(1)=0 なので、0 と4を法として1に合同な数は E に属する。