Строки Фибоначчи

Последовательности могут быть, разумеется, не только числовыми. Например, последовательность строк; определим одну такую.

Пусть \(S_0 = 0\), \(S_1 = 1\), а следующие строки получаются приписыванием вместе двух предыдущих: \(S_{n+1} = S_{n-1} S_n\).

К примеру, \(S_2 = S_0S_1 = 01\), \(S_3 = S_1S_2 = 101\), \(S_4 = 01101\), \(S_5 = 10101101\), \(S_6 = 0110110101101\).

Легко показать, что длины этих строк образуют последовательность чисел Фибоначчи: \(|S_0| = |S_1| = 1\), а \(|S_{n+1}| = |S_{n-1} S_n| = |S_{n-1}|+|S_n|\) — для \(|S_n|\) получаются те же соотношения, что и для \(F_n\).

Ещё видно, что чётные и нечётные члены этой последовательности можно рассматривать как левые кусочки бесконечных строк \(101011010110\ldots\) и \(011011010110\ldots\)

А теперь два задания:

  1. Если убрать из этих бесконечных строк два первых символа, получится ли одно и то же?
  2. Возьмите какую-нибудь из них и найдите замкнутую [это неформальное понятие, довольно хорошо о его смысле рассказывают в «Конкретной математике» Грэхэм, Кнут и Паташник] формулу, превращающую индекс символа в его значение (именно потому я взял \(0\) и \(1\), хотя мне кажутся красивее A и B. Нет, конечно, математика не спасует перед A и B, но операции над ними придётся определять явно, тогда как целые \(0\) и \(1\) можно складывать, умножать и даже растворять).

На вознаграждение остаётся только надеяться, так как, быть честным, я его ещё не придумал.

Строки Фибоначчи: 2 комментария

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

:) :D :( :E: ;) :yes: :no: :donno: more »

Этот сайт использует Akismet для борьбы со спамом. Узнайте как обрабатываются ваши данные комментариев.