В алфавите $%{a, b}$% определены слова Фибоначчи: $%Ф_0=b$%, $%Ф_1=a$%, ... , $%Ф_{n+1}=Ф_{n}Ф_{n-1}$%. Как доказать, что существует $%Ф$% как предел $%Ф_n$%? Как показать, что Ф квазипериодично, т.е. любое его подслово повторяется бесконечное число раз?

задан 22 Июл '19 17:42

1

Первое утверждение очевидно, так как по построению, Ф(n) есть начало слова Ф(n+1) при n>=1. Мы к предыдущему слову каждый раз что-то дописываем, и получаем "предел" Ф в виде abaababa... .

Всякое подслово Ф входит в некоторое Ф(k) для фиксированного k. Тогда оно входит во все слова Ф(n) при n>=k по индукции. Поэтому в Ф(k+2)=Ф(k+1)Ф(k) оно входит как минимум 2 раза, в Ф(k+3)=Ф(k+2)Ф(k+1) не менее 3 раз, в следующее слово не менее 5 раз, и так по числам Фибоначчи, которые стремятся к бесконечности.

(22 Июл '19 17:57) falcao

@falcao, понял, спасибо. А бесконечный предел, тоже что ли является пределом?

(22 Июл '19 18:04) Konon
1

@Konon: если имеется последовательность конечных слов w(1), w(2), ... , где каждое предыдущее есть собственное начало следующего, то этим задано бесконечное слово w, в котором i-й символ равен i-му символу w(i). Его можно назвать "пределом" бесконечной последовательности конечных слов. Примерно в том же смысле как число п есть предел последовательности рациональных чисел 3; 3.1; 3.14; ... . Это всего лишь аналогия, и за ней не обязательно видеть какой-то особый смысл. Хотя, конечно, можно ввести подходящую топологию на множестве слов, и тогда это будет предел в топологическом смысле слова.

(22 Июл '19 18:35) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,463

задан
22 Июл '19 17:42

показан
168 раз

обновлен
22 Июл '19 18:35

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru