難しいです。

1→10 0→1 の変換規則に従い

1,10,101,10110,10110101...
という数列を考える
この時、第n項は第n-1項の末尾に第n-2項をつなげたものであることを示せ (n≥3)


お願いします。

No.2 ベストアンサー 回答者： 20170130 回答日時： 2020/08/03 16:56

数学的帰納法でどうでしょう

文字列の結合を意味する記号として＆を使い、文字列の世代を進める記号としてF()を使い、文字列をa(n)で示すと
a(1) = 1
a(2) = F(a(1)) =10
a(3) = F(a(2)) = 101 = a(2)&a(1)
a(4) = F(a(3)) = 10110 = a(3)&a(2) = F(a(2))&F(a(1))
．．．．．．．．．．．
証明すべき事項は、3 ≤ n で a(n) = a(n-1)&a(n-2)

n = 3 で成立、 a(3) = a(2)&a(1) = 101

n = k で成立するとすれば a(k) = a(k-1)&a(k-2)
n = k+1 でも
a(k+1) = F(a(k)) = F(a(k-1)&a(k-2)) = F(a(k-1))&F(a(k-2)) = a(k)&a(k-1)
成立

以上により、3 ≤ n で a(n) = a(n-1)&a(n-2) は証明された
．．．．．．．．．．．．．
言葉で
第3項は第2項の末尾に第1項をつなげたものである

第k項が第k-1項の末尾に第k-2項をつなげたものである場合
第k+1項は、変換規則通りに第k項を変換したものである
第k項が第k-1項の末尾に第k-2項をつなげたものであるから、第k項に変換規則を使うことは、（前側）第k-1項に変換規則を使い、それにつなげて、（末尾）第k-2項に変換規則を使うことに同じ
変換規則によって、第k-1項は第k項に、第k-2個は第k-1項に、変換されるから
第k+1項は第k項の末尾に第k-1項をつなげたものとなる

以上の推論によりn=3で成立しn=kで成立すればn=k+1でも成立するから
n≥3 で成立する

この回答へのお礼

ありがとうございます

お礼日時：2020/08/03 19:37

No.1 回答者： varietyknowledge 回答日時： 2020/08/03 10:30

これ数学というより、プログラムロジックの範疇だなぁ。

>1,10,101,10110,10110101...

この数列は漸化式が作れない。
なぜなら、第1項と第2項は+1の加算だが、第3項以降は文字列の連結になっている。

>第n項は第n-1項の末尾に第n-2項をつなげたものであることを示せ (n≥3)

と書かれても、そのようなプログラムロジックにしたからとしかいえない。

この回答へのお礼

東京大学の問題らしいです。わからなくてもしょうがないと思います。

お礼日時：2020/08/03 11:42