Рассмотрим последовательность 0,1,10,101,10110,10110101... Каждое следующие число получается из предыдущего так:каждый 0 заменяется на 1, а 1 на 10 А) рассмотрим другое описание кроличьих чисел. Каждое следующие число получается так: берём предыдущее число и припысываем к нему справа предыдущее. Докажите что эти два описания задают одну и ту же последовательность Б) найдите количество цифр в n-м кроличтем числе В) Найдите количество нулей и количество единиц в n-м кроличьем числе

задан 22 Сен '17 19:14

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

Обозначим через $%\phi$% операцию замены букв в слове по правилу $%0\to1$%, $%1\to10$%. Ясно, что $%\phi(uv)=\phi(u)\phi(v)$% для любых слов $%u$%, $%v$%.

Последовательность $%w_n$% задана так, что $%w_1=0$%, $%w_{n+1}=\phi(w_n)$% для всех $%n\ge1$%. Непосредственно видно, что $%w_3=w_2w_1$%. Применяя отображение $%\phi$% к обеим частям, имеем $%w_4=\phi(w_3)=\phi(w_2)\phi(w_1)=w_3w_2$%, и далее по индукции получается $%w_{k+2}=w_{k+1}w_k$% для всех натуральных $%k$%.

Отсюда понятно, что длины слов $%w_k$% -- это числа Фибоначчи: $%F_1=F_2=1$%, $%F_{k+2}=F_{k+1}+F_k$% ($%k\ge1$%). Количество нулей и единиц также удовлетворяет данному рекуррентному соотношению, так как число нулей (единиц) в $%w_{k+2}$% равно сумме числа нулей (единиц) в $%w_{k+1}$% и $%w_k$%. Легко заметить, что число нулей в $%w_k$% равно $%F_{n-2}$%, а число единиц равно $%F_{n-1}$%, где $%F_0=0$%, $%F_{-1}=1$%.

ссылка

отвечен 22 Сен '17 20:18

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

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

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

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

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

отмечен:

×3,701

задан
22 Сен '17 19:14

показан
411 раз

обновлен
22 Сен '17 20:18

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

по почте:

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

по RSS:

Ответы

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

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