第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

の式で表せ。

ステップ 3/6: G を求める

前のステップ次のステップ

f(4k+4)-f(4k+3)=4\bigl(f(k+1)-f(k)\bigr)-(4k+1)<0

詳しい解説

漸化式から f(4k+4)−f(4k+3)=4(f(k+1)−f(k))−(4k+1) で、前の評価により負である。従って4を法として3に合同な添字は G に属する。3つの互いに素な類が全非負整数を覆うので、L={2k:k>0}, E={0}∪{4k+1:k≥0}, G={4k+3:k≥0} である。