9. (GBR 5) ${ }^{1 \mathrm{M} 03}$ Let $\{f(n)\}$ be a strictly increasing sequence of positive integers: $0<f(1)<f(2)<f(3)<\cdots$. Of the positive integers not belonging to the sequence, the $n$th in order of magnitude is $f(f(n))+1$. Determine $f(240)$.
9. Since the $n$th missing number (gap) is $f(f(n))+1$ and $f(f(n))$ is a member of the sequence, there are exactly $n-1$ gaps less than $f(f(n))$. This leads to
$$
f(f(n))=f(n)+n-1 .
$$

Since 1 is not a gap, we have $f(1)=1$. The first gap is $f(f(1))+1=2$. Two consecutive integers cannot both be gaps (the predecessor of a gap is of the form $f(f(m)))$. Now we deduce $f(2)=3$; a repeated application of the formula above gives $f(3)=3+1=4, f(4)=4+2=6, f(6)=9$, $f(9)=14, f(14)=22, f(22)=35, f(35)=56, f(56)=90, f(90)=145$, $f(145)=234, f(234)=378$.
Also, $f(f(35))+1=91$ is a gap, so $f(57)=92$. Then by (1), $f(92)=148$, $f(148)=239, f(239)=386$. Finally, here $f(f(148))+1=387$ is a gap, so $f(240)=388$.
Second solution. As above, we arrive at formula (1). Then by simple induction it follows that $f\left(F_{n}+1\right)=F_{n+1}+1$, where $F_{k}$ is the Fibonacci sequence $\left(F_{1}=F_{2}=1\right)$.
We now prove by induction (on $n$ ) that $f\left(F_{n}+x\right)=F_{n+1}+f(x)$ for all $x$ with $1 \leq x \leq F_{n-1}$. This is trivially true for $n=0,1$. Supposing that it holds for $n-1$, we shall prove it for $n$ :
(i) If $x=f(y)$ for some $y$, then by the inductive assumption and (1)
$$
\begin{aligned}
f\left(F_{n}+x\right) & =f\left(F_{n}+f(y)\right)=f\left(f\left(F_{n-1}+y\right)\right) \\
& =F_{n}+f(y)+F_{n-1}+y-1=F_{n+1}+f(x) .
\end{aligned}
$$
(ii) If $x=f(f(y))+1$ is a gap, then $f\left(F_{n}+x-1\right)+1=F_{n+1}+f(x-1)+1$ is a gap also:
$$
\begin{aligned}
F_{n+1}+f(x)+1 & =F_{n+1}+f(f(f(y)))+1 \\
& =f\left(F_{n}+f(f(y))\right)+1=f\left(f\left(F_{n-1}+f(y)\right)\right)+1 .
\end{aligned}
$$

It follows that $f\left(F_{n}+x\right)=F_{n+1}+f(x-1)+2=F_{n+1}+f(x)$.
Now, since we know that each positive integer $x$ is expressible as $x=$ $F_{k_{1}}+F_{k_{2}}+\cdots+F_{k_{r}}$, where $0<k_{\mathrm{r}} \neq 2, k_{i} \geq k_{i+1}+2$, we obtain $f(x)=F_{k_{1}+1}+F_{k_{2}+1}+\cdots+F_{k_{r}+1}$. Particularly, $240=233+5+2$, so $f(240)=377+8+3=388$.
Remork. It can be shown that $f(x)=[o x]$, where $\alpha=(1+\sqrt{5}) / 2$.