Задача
Сколько существует последовательностей из единиц и двоек, сумма всех элементов которых равна n? Например, если n = 4, то таких последовательностей пять: 1111, 112, 121, 211, 22.
Решение
Докажем по индукции, что таких последовательностей Fn+1.
База (n = 1, 2) легко проверяется.
Шаг индукции. Последовательность с суммой n + 1 можно получить двумя способами: приписать 1 к последовательности с суммой n или приписать 2 к последовательности с суммой n – 1. По предположению инлукции последовательностей первого вида Fn+1, а второго – Fn. Следовательно, последовательностей с суммой n + 1 ровно Fn+1 + Fn = Fn+2.
Ответ
Fn+1.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет