Пусть $%G$% - язык в алфавите $%\{0,1,2\}$%, состоящий из всех слов, в которых соседние символы отличаются (как числа) не более чем на $%1$%, например, $%210\in G, 201 \notin G$%. Найдите рекуррентное соотношение, которому удовлетворяет последовательность $%\{g_n,n=1,2,...\}$%, где $%g_n$% равно числу слов длины $%n$% в $%G$%, и оцените $%g_{2014}$%.

задан 8 Мар '16 15:13

10|600 символов нужно символов осталось
1

Введём числа $%x_n$% и $%y_n$% для $%n\ge1$%. Первое означает число слов из $%G$% длиной $%n$%, оканчивающихся символом 0. Из соображений симметрии, столько же будет слов, оканчивающихся на 2. Вторая величина даёт количество слов той же длины, оканчивающихся символом 1.

Очевидно, что $%x_{n+1}=x_n+y_n$% (так как 0 можно приписать после 0 или 1), а также $%y_{n+1}=2x_n+y_n$% (так как 1 можно приписать после любого из символов). Из этих соотношений легко выводится, что $%y_{n+2}=2y_{n+1}+y_n$%, где $%y_1=1$%, $%y_2=3$%. Понятно также, что $%g_n=y_{n+1}$%, то есть рекуррентное уравнение такое же. Начальные значения: $%g_0=1$%, $%g_1=3$%.

Общую формулу для $%g_n$% нетрудно получить, решив характеристическое уравнение $%\lambda^2-2\lambda-1=0$%, корнями которого являются числа $%1\pm\sqrt2$%. При этом $%g_1=C_1(1+\sqrt2)^n+C_2(1-\sqrt2)^n$%, и из начальных значений легко найти константы. Окончательно получается $$g_n=\dfrac{(1+\sqrt2)^{n+1}+(1-\sqrt2)^{n+1}}2.$$

Поскольку $%|1-\sqrt2| < 1$%, степени этого числа быстро стремятся к нулю, и при больших значениях $%n$% можно пренебречь вторым слагаемым. После этого величину $%g_{2014}$% легко оценить с помощью логарифмов. Получается примерно $%9,816932955\cdot10^{770}$%.

ссылка

отвечен 8 Мар '16 15:51

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

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

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

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

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

отмечен:

×237
×150
×63
×21

задан
8 Мар '16 15:13

показан
411 раз

обновлен
8 Мар '16 15:51

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

по почте:

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

по RSS:

Ответы

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

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