Магия математики. Как найти x и зачем это нужно - Артур Бенджамин

Мы заглянули лишь в замочную скважину той двери, за которой раскинулся сад самых настоящих чудес. Только растут в нем не деревья, а числовые закономерности, уходящие корнями в последовательность Фибоначчи. И вам, наверняка, не терпится узнать, для чего еще, кроме подсчета поголовья кроликов, нужны эти числа. На самом деле – много для чего. В 1150 году (задолго до того, как Леонардо Пизанский представил миру задачку про кроликов) индийский поэт Хемачандра задался очень интересным вопросом: сколькими способами можно сложить стихотворную стопу из n безударных или ударных слогов. Давайте сперва переведем эту проблему из плоскости поэзии в плоскость математики.

Вопрос: Сколькими способами можно записать число n как сумму единиц и двоек?

Ответ: Обозначим результат как f_n. Вот что будем иметь при стартовых значениях n:

У нас есть один вариант, дающий в сумме 1, два варианта, дающих 2 (1 + 1 и 2), и три варианта, дающих 3 (1 + 1 + 1, 1 + 2 и 2 + 1). Повторимся: для получения нужной нам суммы доступны только единицы и двойки. При этом порядок этих цифр имеет значение: 1 + 2 и 2 + 1 суть две разные комбинации. Получить 4 можно уже пятью разными вариантами: 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1, 2 + 2. По всему выходит, что числа в правой части нашей таблицы – это числа из последовательности Фибоначчи, и так оно есть на деле.

Давайте попробуем понять, почему вдруг 5 можно получить f5 = 8 различными способами. Начинаться сложение может с 1 или 2. Сколько вариантов будет начинаться именно с 1? За первой цифрой должна следовать некая комбинация 1 и 2, которая в сумме даст 4, а по предыдущей строке мы знаем, что таких комбинаций у нас f₄ = 5. Теперь так же посчитаем, сколько вариантов будет начинаться с 2. В этом случае комбинация после первой цифры должна давать нам 3. Смотрим чуть выше по таблице и видим, что f₃ = 3. Значит, общее количество комбинаций 1 и 2, дающих в сумме 5, должно быть 5 + 3 = 8. Тот же алгоритм приведет нас к тому, что для 6 таких комбинаций будет 13: f₅ = 8, начинающихся с 1, плюс f₄ = 5, начинающихся с 2. В целом же, для суммы n их число равно f_n, из которых f_n–1 имеют в начале 1, а f_n–2 – 2. Следовательно,

fn = fn – 1 + fn – 2

Причем все значения f_n дублируют числа последовательности Фибоначчи и будут и дальше их дублировать с увеличением значения n. Причина в том, что это и есть последовательность Фибоначчи, только в несколько измененном виде – с небольшим смещением. Обратите внимание, что f₁ = 1 = F₂, f₂ = 2 = F₃, f₃ = 3 = F₄ и т. д. (для удобства договоримся, что f₀ = F₁ = 1, а f_–1 = F₀ = 0). Обобщая, мы можем утверждать, что при n ≥ 1

f_n = F_n+1

А так как мы с вами уже знаем, что означают числа последовательности, мы с их помощью можем доказать состоятельность многих и многих других удивительных закономерностей. Возьмем, к примеру, ту из них, о которой мы говорили в конце главы 4, когда просчитывали диагонали Паскалева треугольника:

Так, восьмая диагональ дает нам

1 + 7 + 15 + 10 + 1 = 34 = F₉

С точки зрения «подсчета комбинаций» это значит, что

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