|
Вроде как делать по индукции. База легко делается. А вот шаг, я не понимаю, как делать. Если предположить, что для 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 
Leva319 |
|
Здесь схема рассуждения по индукции несколько отличается от той, где осуществляется переход от одного значения к следующему. Есть другая схема, которую здесь надо применить. Выглядит она так: мы доказываем утверждение для значения $%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 
falcao Правильно я понимаю, что Вы применили здесь принцип полной математической индукции?
(14 Сен '14 21:57)
Leva319
Да, принцип имелся в виду этот. Его иногда называют таким именем называют, хотя мне этот термин не кажется удачным. Всё-таки под полной индукцией принято понимать нечто иное (полный перебор всех возможных вариантов).
(14 Сен '14 22:13)
falcao
|