第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

の式で表せ。

ステップ 5/6: 漸化式を得る

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

詳しい解説

$2^k-1$ における $f$ を計算すると $a_k=2a_{k-1}+2^{k-1}-1$ となる。この漸化式は $k\ge1$ で成り立ち、初期値は $a_0=a_1=0$ 、 $a_2=1$ である。