OMC190(F) - ユーザー解説

　$a_n=\lfloor\frac{1+\sqrt{5}}{2}n\rfloor+1$ の別証です．

　明らかに $a_{n+1}\gt a_n\geq n+1$ なので，題意より
$$a_n=a_1+1×(n-1-\#(k|a_k\leq n))+2×\#(k|a_k\leq n)=n+1+\#(k|a_k\leq n)$$ がわかる．
　以降，数学的帰納法で $a_n=\lfloor\frac{1+\sqrt{5}}{2}n\rfloor+1$ を示す．
　$n=1$ のときは明らかに成り立つ．
　$n\leq m$ のとき成り立つとする．このとき，$m+1\geq 2，a_{n+1}-a_n\leq 2$ より $a_l=m+1$ または $a_l=m+2$ なる整数 $l$ をとれる．
　$a_l=m+1$ なる $l$ が存在するとき， $$a_{m+1}=a_{a_l}= a_l+1+\#(k|a_k\leq a_l)=l+m+2$$ である．$\frac{1+\sqrt{5}}{2}l$ が整数となることは明らかにないので，$a_l=m+1$ より $$\frac{1+\sqrt{5}}{2}l-1\lt m\lt \frac{1+\sqrt{5}}{2}l$$ であることから $$\frac{1+\sqrt{5}}{2}(m+1)=\frac{-1+\sqrt{5}}{2}m+m+\frac{1+\sqrt{5}}{2}\gt \frac{-1+\sqrt{5}}{2}(\frac{1+\sqrt{5}}{2}l-1)+m+\frac{1+\sqrt{5}}{2}=l+m+1$$ $$\frac{1+\sqrt{5}}{2}(m+1)=\frac{-1+\sqrt{5}}{2}m+m+\frac{1+\sqrt{5}}{2}\lt l+m+2$$ となるため $$\lfloor \frac{1+\sqrt{5}}{2}(m+1)\rfloor+1=l+m+2=a_{m+1}$$ がわかる．
　そうでないときは，$a_l=m+2$ なる $l$ が存在するので $$a_{m+1}=a_{a_l-1}= (a_l-1)+1+\#(k|a_k\leq a_l-1)=l+m+1$$ である．$a_l=m+2$ より $$\frac{1+\sqrt{5}}{2}l-2\lt m\lt \frac{1+\sqrt{5}}{2}l-1$$ となり，先程と同様の議論から $$l+m\lt \frac{1+\sqrt{5}}{2}(m+1)\lt l+m+1$$ がわかるので $$\lfloor \frac{1+\sqrt{5}}{2}(m+1)\rfloor+1=l+m+1=a_{m+1}$$ である．
　以上より，$n=m+1$ のときも成立することが示せた．
　したがって，$a_n=\lfloor\frac{1+\sqrt{5}}{2}n\rfloor+1$ がわかる．

　余談ですが， $$a_{a_n}=a_n+1+\#(k|a_k\leq a_n)=a_n+n+1$$ より，$b_1=n，b_{n+1}=a_{b_n}$ とおいて $b_n$ についての三項間漸化式の特性方程式を解くことで $\frac{1+\sqrt{5}}{2}$ という値が何とは無しに見えたりします．