Числа Фибоначчи и число разложений

[Niksan]

Здравствуйте, помогите, пожалуйста, решить задачу:
Выразить через числа Фибоначчи число разложений n на части равные 1 или 2

[mihailm]

забудьте пока про Фибоначчи, поймите вначале задание посчитав сколько там разложений при маленьких n

[svv]

А разложения, отличающиеся только порядком слагаемых, считаются одним разложением или разными?

[Хорхе]

Считаются разными. На то они и разложения, а не разбиения

[Niksan]

получилось, что число разбиений для 2n равно числу разбиений для 2n+1
ну и формула, вроде бы, нахождения количества разбиений:
[n/2]+1
что делать дальше?

[ИСН]

По-моему, больше. Смотрите: 5
=1+1+1+1+1
=1+1+1+2
=1+1+2+1
=1+2+1+1
=2+1+1+1
=1+2+2
=2+1+2
=2+2+1

[Niksan]

о, получается, что число разложений n на части, равные 1 или 2 равно Fn, это и есть ответ?

[mihailm]

а разве не это написано в условии задачи?

[Niksan]

спасибо, все оказалось действительно просто

[Niksan]

понятно, что количество разложений числа n равно числу n+2 в ряде Фибоначчи, но ведь то, что разложение нескольких чисел совпадают таким образом с числами Фибоначчи это ведь не доказательство
как доказать, что это будет выполняться для всех чисел?

[Joker_vD]

Niksan в сообщении #424029 писал(а):

как доказать, что это будет выполняться для всех чисел?

По индукции?

[Niksan]

так ведь для того, чтобы доказать по индукции нужно знать формулу нахождения количества таких разложений для числа n

[ИСН]

да, и мы её знаем: это число Фибоначчи номер n

[Niksan]

понятно, что
Р(n-1)=F(n-1)
P(n)=F(n)
тогда нужно выразить как то P(n+1) через P(n-1) и P(n), как это сделать я не понимаю

[ИСН]

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

-- Пт, 2011-03-18, 00:25 --

сколько у нас разложений, у которых в нач...