https://spherical-harmonics.hateblo.jp/entry/Todai/1992/Bunka

2024.01.07記

[3] $p_1=1$ ， $p_2=1$ ， $p_{n+2}=p_n+p_{n+1}$ （ $n\geqq 1$ ）によって定義される数列 $\{p_n\}$ をフィボナッチ数列といい，その一般項は
$p_n=\dfrac{1}{\sqrt5} \left\{ { \left( \dfrac{1+\sqrt5}{2} \right) }^n-{ \left( \dfrac{1-\sqrt5}{2} \right) }^n \right\}$
で与えられる．必要ならばこの事実を用いて，次の問いに答えよ．

各桁の数字が $0$ か $1$ であるような自然数の列 $X_n$ （ $n=1$ ， $2$ ，…）を次の規則により定める．

(i) $X_1=1$

(ii) $X_n$ のある桁の数字 $\alpha$ が $0$ ならば $\alpha$ を $1$ で置き換え， $\alpha$ が $1$ ならば $\alpha$ を ` $10$ ' で置き換える． $X_n$ の各桁ごとにこのような置き換えを行って得られる自然数を $X_{n+1}$ とする．

たとえば， $X_1=1$ ， $X_2=10$ ， $X_3=101$ ， $X_4=10110$ ， $X_5=10110101$ ，… となる．

(1) $X_n$ の桁数 $a_n$ を求めよ．

(2) $X_n$ の中に ` $01$ ' という数字の配列が現れる回数 $b_n$ を求めよ（たとえば， $b_1=0$ ， $b_2=0$ ， $b_3=1$ ， $b_4=1$ ， $b_5=3$ ，…）．

2024.01.07記

[解答]
(1) $X_n$ の各桁を表す $0$ の個数を $x_n$ ， $1$ の個数を $y_n$ とおくと，
$x_1=0$ ， $y_1=1$ ，
$x_{n+1}=y_n$ ， $y_{n+1}=x_n+y_n$
だから，
$x_1=0$ ， $x_2=1$ ， $x_{n+2}=x_{n+1}+x_n$ ，
$y_1=1$ ， $y_2=1$ ， $y_{n+2}=y_{n+1}+y_n$
が成立する．よって $a_n=x_n+y_n$ について
$a_1=1$ ， $a_2=2$ ， $a_{n+2}=a_{n+1}+a_n$
が成立する．よって
$a_n=p_{n+1}=\dfrac{1}{\sqrt5} \left\{\left( \dfrac{1+\sqrt5}{2} \right)^{n+1}-\left( \dfrac{1-\sqrt5}{2} \right)^{n+1} \right\}$
となる．

(2) $X_n$ は ` $1$ ' と ` $10$ ' を並べたものであるから ` $0$ ' は連続せず，先頭は必ず ` $1$ ' となるので
$X_n$ の末尾が` $1$ 'ならば $b_n$ は ` $0$ ' の個数 $x_n$ に等しく，
$X_n$ の末尾が` $0$ 'ならば $b_n$ は ` $0$ ' の個数 $x_n$ より1小さい．

ここで $X_n$ の末尾が ` $0$ 'ならば $X_{n+1}$ の末尾が ` $1$ ' であり，
$X_n$ の末尾が ` $1$ 'ならば $X_{n+1}$ の末尾が ` $0$ ' であるから，末尾は` $0$ '，` $1$ 'を交互に繰り返し， $n$ が奇数ならば` $1$ '， $n$ が偶数ならば` $0$ 'となる．

よって，

$n$ が奇数のとき： $b_n=x_n=p_{n-1}$ $=\dfrac{1}{\sqrt5} \left\{\left( \dfrac{1+\sqrt5}{2} \right)^{n-1}-\left( \dfrac{1-\sqrt5}{2} \right)^{n-1} \right\}$

$n$ が偶数のとき： $b_n=x_n-1=p_{n-1}-1$ $=\dfrac{1}{\sqrt5} \left\{\left( \dfrac{1+\sqrt5}{2} \right)^{n-1}-\left( \dfrac{1-\sqrt5}{2} \right)^{n-1} \right\}-1$