n буквенное слово, состоящее из букв a, b называется хорошим, если не содержит подслово "aaa". Докажите, что для больших n количество хороших слов превышает (1.7)^n. Я получил рекуррентное соотношение a(n)=2a(n-1)-a(n-4), где a(n) - количество хороших слов длинной n. Как дальше доказать?

задан 7 Дек '18 16:30

1

соответствующее характеристическое уравнение сводится к кубическому уравнению. Один корень действительный примерно равный 1.839 и два комплексных, по модулю меньших 1. В асимптотике остается только действительный корень.

(7 Дек '18 19:20) spades
10|600 символов нужно символов осталось
1

Рекуррентное соотношение тут есть и более простое ("числа трибоначчи"): a(n)=a(n-1)+a(n-2)+a(n-3). Как обычно, составляется характеристическое уравнение p(k)=k^3-k^2-k-1=0. Вещественный корень у него всего один, что проверяется стандартными способами. Подставляя k=1.7 или даже k=1.8, проверяем, что p(k) < 0, в то время как p(2) > 0. Значит, корень заключён между 1.8 и 2. Далее можно воспользоваться общей теорией, согласно которой a(n)=c1k1^n+c2k2^n+c3k3^n для некоторых констант c1, c2, c3, где k1, k2, k3 -- комплексные корни. Однако мы не знаем значений мнимых корней, а также значений констант, которые теоретически могут быть и отрицательными. В принципе, этот путь можно довести до конца, оценивая комплексные модули мнимых корней, но можно поступить проще.

Прежде всего, a(0)=1, a(1)=2, a(2)=4, a(3)=7, и так далее. Докажем индукцией по n, что a(n)>=C*1,8^n, где C -- некоторая положительная константа. От неё требуется только одно -- чтобы она давала верные неравенства при n=0,1,2. Однако для этих значений a(n)=2^n, поэтому подходит значение C=1 (а точное нам и не нужно). Далее доказательство совсем простое: для n<=2 неравенство верно, а при n>=3 мы по рекуррентное формуле получаем a(n)=a(n-1)+a(n-2)+a(n-3)>=1,8^{n-1}+1,8^{n-2}+1,8^{n-3}. Выше мы проверяли, что k^3 < k^2+k+1 при k=1,8. Правая часть нашего неравенства равна 1,8^{n-3}(k^2+k+1) > 1,8^{n-3}k^3=1,8^n, что и требовалось доказать.

Здесь должен быть виден общий "механизм" нахождения числа, для которого такое индуктивное доказательство проходит: это число, близкое к корню характеристического уравнения.

ссылка

отвечен 7 Дек '18 19:36

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×63
×21

задан
7 Дек '18 16:30

показан
264 раза

обновлен
7 Дек '18 19:36

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

по почте:

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

по RSS:

Ответы

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

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