12240004

NO.12240004　変な規則の数列 ～難易度☆★★★★

問題

 22 ：以下、名無しにかわりましてVIPがお送りします：2008/11/13(木) 01:04:38.49 ID:gHadZh570
   各桁の数字が0か1であるような自然数の列X_n（n=1,2,3,……）を次の規則により定める。
   i) X_1 = 1
   ii) X_nのある桁の数字αが0ならばαを1で置き換え、αが1ならばαを10で置き換える。
   X_nの各桁ごとにこのような置き換えを行って得られる自然数をX_(n+1)とする
   例えば、X_1 = 1 , X_2 = 10 , X_3 = 101 , X_4 = 10110 , X_5=10110101 , X_6=1011010110110　……
   このとき、X_nの中に01と言う数字の配列が表れる回数x_nを求めよ 

解答

...

x_n=1/√5( ( (√5+1)/2)^(n-1)-(1-√5)^(n-1)/2)-(1+(-1)^n)/2

解説

自分なりのとき方ですが参考に

X_n=X_(n-1)X_(n-2)となるのが規則性からわかる(証明は略でX_(n-1)X_(n+2)は積ではなく自然数の並び)

これより、

x_(2m+1)=x_2m+x_(2m-1)+1

x_2m=x_(2m-1)+x_(2m-2)が成り立つ。

つまり、x_n=x_(n-1)+x_(n-2)+(1-(-1)^n)/2。

よって、これを解けば終了です。

ですが、これはかなり面倒なので省略。

x_n=1/√5( ( (√5+1)/2)^(n-1)-(1-√5)^(n-1)/2)-(1+(-1)^n)/2