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

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

Мы удостоверились, что формула работает для n = 8, на основе того, что знали про n = 7.

В случае n = 9 мы точно так же опираемся на результат для n = 8 (убедитесь в этом самостоятельно). Разумеется, доказав верность (*) для n, мы можем быть уверены, что (*) верно и для n + 1.

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

Вначале мы доказываем (*) в простейшем случае, для n = 0. Мы просто проверяем, что F₀ = F_{0 + 2} – 1. Так как F₀ = 1, а F₂ = 2, очевидным образом 1 = 2 – 1, а F₀ = F₂ – 1.

Дальше нам достаточно показать, что верность формулы для одного значения n (скажем, n = k) автоматически означает верность для n + 1 (в нашем примере n = k + 1). Нам лишь надо продемонстрировать, как устроено это «автоматически». Что нам нужно сделать?

Возьмем некоторое число k.

Предположим, мы уже знаем, что

F₀ + F₁ + … + F_k = F_{k + 2}– 1.

Мы ищем величину

F₀ + F₁ + … + F_k + F_{k + 1}.

Мы уже знаем сумму чисел Фибоначчи вплоть до F_k, поэтому у нас получается:

(F₀ + F₁ + … + F_k) + F_{k + 1} = (F_{k + 2}–1) + F_{k + 1}.

Правая часть равна F_{k + 2} – 1 + F_{k + 1}, и мы знаем, чему равна сумма следующих друг за другом чисел Фибоначчи:

F_{k+ 2}–1 + F_{k + 1} = (F_{k + 2} + F_{k + 1}) – 1 = F_{k + 3}– 1

Подставим в наше равенство:

(F₀ + F₁ + … + F_k) + F_{k + 1} = F_{k + 3}– 1

Сейчас я объясню, что мы сделали. Если мы знаем, что (*) верно, когда мы суммируем числа вплоть до F_k, тогда (*) должно быть верно, если мы приплюсуем F_{k + 1}.

Подытожим:

• Формула (*) верна для n = 0.

• Если формула (*) верна для n, она верна и для n + 1.

Мы можем уверенно сказать, что (*) верно для любых значений n. Верно ли (*) для n = 4987? Это так, если выражение верно для n = 4986, что основано на верности выражения для n = 4985, и так далее до n = 0. Следовательно, формула (*) верна для всех возможных значений n.

Этот метод доказательства известен под названием математическая индукция (или доказательство по индукции). Мы проверяем базовый случай и даем шаблон, по которому каждый следующий случай может быть доказан на основе предыдущего.

Комбинаторное доказательство

А вот совершенно другое доказательство тождества (*). Основной подход тут – воспользоваться тем фактом, что число F_n – это количество способов облицевать прямоугольник 1 × n квадратами и костяшками домино.

Напомню, что нам нужно доказать:

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

Идея заключается в том, чтобы рассматривать обе части уравнения как решение задачи с облицовкой. Если мы докажем, что левая и правая часть – решение для одного и того же прямоугольника, они совпадут между собой. Эта техника носит название комбинаторного доказательства[97].

На какой вопрос по комбинаторике уравнение (*) дает два верных ответа? Эта головоломка похожа на те, что встречаются в шоу Jeopardy![98], где участники должны формулировать вопрос, заранее зная правильный ответ.

Правая часть выглядит проще, поэтому начнем с нее. Ответ: F_{n + 2} – 1. Каков вопрос? Если бы ответ был равен просто F_{n + 2}, мы с легкостью сформулировали бы вопрос: сколькими способами можно облицевать прямоугольник 1 × (n + 2) с помощью квадратов и костяшек домино?

Это почти то, что нужно, но ответ меньше на единицу. Попробуем мягко поменять вопрос и уменьшить ответ. Уберем один вариант облицовки и пересчитаем оставшиеся. Сложность состоит в том, чтобы найти один вариант, который кардинально отличается от остальных. Есть ли такой?

Каждый способ облицовки подразумевает использование квадратов и/или домино. Только квадраты задействованы в единственном варианте, в прочих есть хотя бы одна костяшка домино. Возьмем это за основу нового вопроса.

Вопрос: Сколько существует вариантов облицовки квадратами и костяшками домино прямоугольной рамки 1 × (n + 2), включающих по меньшей мере одну костяшку домино?

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

Один из ответов мы уже обсуждали. Есть F_{n + 2} вариантов укладки. Только один из них подразумевает использование исключительно квадратов, без домино.

Таким образом, ответ № 1 на наш вопрос таков: F_{n + 2} – 1.

Второй ответ должен быть – я надеюсь – левой частью уравнения (*). Посмотрим, как это работает.

Нужно пересчитать варианты заполнения рамки, включающие хотя бы одну костяшку домино. Давайте подумаем, где будет расположена самая первая костяшка. Есть n + 2 позиций, и первая костяшка может располагаться в позициях от 1 до n + 1.