Условие

Вроде как делать по индукции. База легко делается. А вот шаг, я не понимаю, как делать. Если предположить, что для 2 x n верно, то надо док-ать для 2 x (n-1) . Рисую прямоугольник 2 x (n-1), горизонтально отсекаю нижний и получаю 2 прямоугольника, один из которых 2 x 1, а другой 2 x n, для этой ситуации имеем Fn+1 способов, но как получить остальные Fn способов?

задан 14 Сен '14 21:13

изменен 15 Сен '14 16:32

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


9917

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

Здесь схема рассуждения по индукции несколько отличается от той, где осуществляется переход от одного значения к следующему. Есть другая схема, которую здесь надо применить. Выглядит она так: мы доказываем утверждение для значения $%n$%, в предположении, что оно уже доказано для всех значений, строго меньших $%n$%.

Разница в том, что в "обычной" схеме, если я хочу доказать утверждение для $%n=13$%, то опираюсь на истинность утверждения только при $%n=12$%. А в новом варианте я могу опираться на истинность утверждения и для $%n=11$%, и для всех меньших. Поскольку имеется в виду, что доказательство проводится последовательно для значений $%n=1$%, $%n=2$%, и так далее, то такое рассуждение с логической точки зрения корректно.

В данной задаче, при рассмотрении прямоугольника $%2\times n$% можно опираться на уже установленные факты для прямоугольников $%2\times(n-1)$% и $%2\times(n-2)$%, и тогда как раз получается $%F_n+F_{n-1}=F_{n+1}$%. Самая нижняя плитка может лежать горизонтально, а могут вместо неё две плитки лежать вертикально. Это даёт два случая, которые всё исчерпывают.

ссылка

отвечен 14 Сен '14 21:24

Правильно я понимаю, что Вы применили здесь принцип полной математической индукции?

(14 Сен '14 21:57) Leva319

Да, принцип имелся в виду этот. Его иногда называют таким именем называют, хотя мне этот термин не кажется удачным. Всё-таки под полной индукцией принято понимать нечто иное (полный перебор всех возможных вариантов).

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

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

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

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

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

отмечен:

×846

задан
14 Сен '14 21:13

показан
242 раза

обновлен
14 Сен '14 22:13

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

по почте:

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

по RSS:

Ответы

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

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