第3問

0<f(1)<f(2)<f(3)<\ldots

を、正の整数からなる数列とする。この数列に属さない正の整数のうち

n

番目のものは

f(f(n))+1

である。

f(240)

を求めよ。

ステップ 2/5: 計数漸化式を導く

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

ざっくり言うと

1つの既知の値から、下にある項と欠番を数えて2つの新しい項が得られる。

f(n)=k \;\Longrightarrow\; f(k)=n+k-1,\quad f(k+1)=n+k+1

詳しい解説

$f(n)=k$ とする。 $n$ 番目の欠番は $f(k)+1$ なので、 $1$ から $f(k)+1$ までには欠番が $n$ 個、数列の項が $k$ 個ある。よって $n+k=f(k)+1$ 、すなわち $f(k)=n+k-1$ 。したがって $n$ 番目の欠番は $n+k$ であり、その次の整数 $n+k+1$ は数列に属して $f(k+1)$ に等しい。