Путеводитель для влюбленных в математику

Мы нашли пять возможностей, но где гарантия, что мы ничего не упустили? Есть способ проверить себя.

В левом конце рамки может быть или квадрат, или костяшка домино. В верхнем ряду на рисунке – варианты, когда слева квадрат, в нижнем ряду – когда слева домино.

Допустим, слева квадрат. Оставшуюся часть нужно заполнить квадратами и домино. Другими словами, нужно заполнить рамку 1 × 3. Это дает 3 варианта, так как F₃ = 3.

Если слева домино, размер оставшейся части 1 × 2, и заполнить ее можно двумя вариантами, так как F₂ = 2.

Таким образом, у нас есть 3 + 2 = 5 вариантов, и мы удостоверились, что F₄ = 5.

Теперь ваша очередь. Подумайте пару минут и найдите все варианты заполнения для рамки 1 × 5. Их немного. Решение – в конце главы. Можете отвлечься и подумать.

Вернемся к нашим квадратам. Хочется верить, что вы нашли 8 вариантов, так как есть 5 способов укладки, где слева квадрат, и еще 3 способа, где слева домино. Таким образом, F₅ = 8.

Подытожим. Мы обозначили F_N количество способов заполнения рамки 1 × n квадратами и костяшками домино. Нам необходимо найти F₁₀. Вот что мы уже знаем:

Двигаемся дальше. Чему равно F₆? Можно нарисовать все варианты, но это скучно. Лучше разобьем вопрос на две части. Сколькими способами можно заполнить рамку 1 × 6, если слева (a) квадрат и (b) костяшка домино? Хорошая новость: мы уже знаем ответ!

В первом случае нам остается пять квадратов, а мы знаем, что F₅ = 8. Во втором случае нужно заполнить четыре квадрата; нам известно, что F₄ = 5. Таким образом, F₅ + F₄ = 13.

Чему равно F₇? Исходя из тех же соображений, F₇ = F₆ + F₅ = 13 + 8 = 21. А как насчет F₈? Очевидно, F₈ = F₇ + F₆ = 21 + 13 = 34. И так далее. Мы обнаружили следующую взаимосвязь:

F_n = F_{n – 1} + F_{n – 2}.

Еще несколько шагов – и мы найдем искомое число F₁₀. Правильный ответ – в конце главы.

Числа Фибоначчи

Числа Фибоначчи – это последовательность:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Она выстраивается по таким правилам:

– первые два числа 1 и 1;

– каждое следующее число получаем сложением двух предыдущих.

Будем обозначать n-ный элемент последовательности F_n, начиная с нуля:

F₀ = 1, F₁ = 1, F₂ = 2, F₃ = 3, F₄ = 5, …

Очередной элемент мы вычисляем по формуле:

F_n = F_{n – 1} + F_{n – 2}.

Как мы видим, задача об укладке квадратов и домино привела нас к последовательности чисел Фибоначчи[96].

Сумма чисел Фибоначчи

Попробуем сложить первые несколько чисел Фибоначчи. Что мы можем сказать о сумме F₀ + F₁ + … + F_n для любого n? Давайте проделаем кое-какие вычисления и посмотрим, что получится.

Обратите внимание на результаты сложения внизу. Видите ли вы закономерность? Повремените немного, прежде чем двигаться дальше: будет лучше, если вы найдете ответ самостоятельно, а не прочтете уже готовое решение.

Хочется верить, вы увидели, что результаты суммирования, если к ним приплюсовать по единице, тоже выстраиваются в последовательность чисел Фибоначчи. Например, сложение чисел от F₀ до F₅ дает:

F₀ + F₁ + F₂ + F₃ + F₄ + F₅ = 1 + 1 + 2 + 3 + 5 + 8 = 20 = F₇ – 1.

Сложение чисел от F₀ до F₆ дает 33, что на единицу меньше F₈ = 34. Мы можем записать формулу для неотрицательных целых чисел n:

F₀ + F₁ + F₂ + … + F_n = F_{n + 2}–1. (*)

Вероятно, лично вам достаточно будет увидеть, что формула (*) работает в дюжине случаев, чтобы вы поверили, что она верна, но математики жаждут доказательств. Мы рады представить вам два возможных доказательства того, что она верна для всех неотрицательных целых чисел n. Первое называется доказательством по индукции, второе – комбинаторным доказательством.

Доказательство по индукции

Формула (*) представляет собой бесконечно много формул в свернутом виде. Доказать, что (*) верно для конкретного значения n, скажем для n = 6, – простая арифметическая задача. Достаточно будет записать числа от F₀ до F₆ и сложить их:

F₀ + F₁ + … + F₆ = 1 + 1 + 2 + 3 + 5 + 8 + 13 = 33.

Несложно увидеть, что F₈ = 34, поэтому формула действует.

Перейдем к F₇. Не будем тратить время и складывать все числа: мы уже знаем сумму вплоть до F₆. Таким образом,

(F₀ + F₁ + … + F₆) + F₇ = 33 + 21 = 54.

Как и раньше, все сходится: F₉ = 55.

Если сейчас мы начнем проверять, работает ли формула для n = 8, наши силы окончательно иссякнут. Но все же посмотрим, что мы уже знаем и что хотим выяснить:

F₀ + F₁ + … + F₇ = F₉–1.F₀ + F₁ + … + F₇ + F₈ =?

Воспользуемся предыдущим результатом:

(F₀ + F₁ + … + F₇) + F₈ = (F₉– 1) + F₈.

Мы, конечно, можем вычислить (F₉ – 1) + F₈ арифметически. Но так мы устанем еще больше. В то же время мы знаем, что F₈ + F₉ = F₁₀. Таким образом, нам не нужно ничего высчитывать или заглядывать в таблицу чисел Фибоначчи: