Задача 60583

Тема:    [ Числа Фибоначчи ]

Сложность: 3 Классы: 8,9,10,11

Условие

Сколько существует последовательностей из единиц и двоек, сумма всех элементов которых равна n? Например, если  n = 4,  то таких последовательностей пять: 1111,  112,  121,  211,  22.

Решение

  Докажем по индукции, что таких последовательностей F_n+1.
  База  (n = 1, 2)  легко проверяется.
  Шаг индукции. Последовательность с суммой  n + 1  можно получить двумя способами: приписать 1 к последовательности с суммой n или приписать 2 к последовательности с суммой  n – 1.  По предположению инлукции последовательностей первого вида F_n+1, а второго – F_n. Следовательно, последовательностей с суммой  n + 1  ровно  F_n+1 + F_n = F_n+2.

Ответ

F_n+1.

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	3
Название	Алгоритм Евклида и основная теорема арифметики
Тема	Алгебра и арифметика
параграф
Номер	4
Название	О том, как размножаются кролики
Тема	Классическая комбинаторика
задача
Номер	03.131