Вот задача

Я примерно представляю, как решать это через индукцию и правило Паскаля, но это муторно - надо рассматривать два случая, когда n четно и нет, плюс ко всему для базы нужны два утверждения. В общем, хочется понять, как решить это более лаконично, если можно.

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

изменен 17 Сен '14 17:06

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

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

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

С биномиальными коэффициентами всё ясно: $%C_n^k$% выражает число способов выбрать $%k$% элементов из $%n$%. Для чисел Фибоначчи надо взять любую задачу, в которой возникает такой ответ. Например, пусть нас интересует число строк из нулей и единиц длиной $%n$%, где никакие две единицы не идут подряд. При $%n=0$% такая строка одна (пустая), при $%n=1$% их две. Далее при $%n\ge2$% строка оканчивается либо на 0, либо на 01. Поэтому число таких строк будет равно сумме двух предыдущих чисел последовательности -- для длин $%n-1$% и $%n-2$% соответственно. Это и есть рекуррентная зависимость для чисел Фибоначчи.

Если мы положим $%F_1=F_2=1$% и далее $%F_n=F_{n-1}+F_{n-2}$% при $%n\ge3$%, то окажется, что число $%F_{n+2}$% описывает количество строк длиной $%n$% с указанным выше свойством. Допишем 0 у строки слева. Тогда получатся строки длиной $%n+1$%, начинающиеся с нуля, у которых 11 не встречается в качестве подстроки. Мы показали, что их количество равно $%F_{n+2}$%, а теперь сосчитаем его же другим способом.

Легко видеть, что все такие строки составляются из 0 и 01 в произвольном количестве. Пусть $%k\ge0$% -- число единиц в строке. Тогда 01 встречается столько же раз, и общее число позиций для 0 и 01 равно $%n+1-k$%. На этих местах 01 можно расставить $%C_{n+1-k}^k$% способами, где $%2k\le n+1$%. Если эти числа просуммировать по всем допустимым значениям $%k$%, то получится сумма $$C_{n+1}^0+C_n^1+C_{n-1}^2+\cdots+C_{n+1-k}^k+\cdots$$ из левой части равенства. Она равна $%F_{n+2}$%, что и требовалось.

Хотя чисто комбинаторные доказательства обычно оказываются более предпочтительными, в данном случае прямая вычислительная проверка рекуррентной формулы выглядит даже несколько проще с учётом правила формирования элементов треугольника Паскаля.

ссылка

отвечен 17 Сен '14 14:50

Спасибо за ответ! Перед тем как прочел Ваш ответ, нашел это в книге Виленкиных, там практически так же.

(17 Сен '14 17:48) Leva319

Не удивительно: хотя я и не знаком с текстом самого нового издания, но все мы учились по книгам Н.Я.Виленкина (там сейчас уже третье поколение присутствует), поэтому мыслим схоже.

(17 Сен '14 18:03) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×846

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

показан
635 раз

обновлен
17 Сен '14 18:03

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

по почте:

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

по RSS:

Ответы

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

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