Хочется верить, вы увидели, что результаты суммирования, если к ним приплюсовать по единице, тоже выстраиваются в последовательность чисел Фибоначчи. Например, сложение чисел от F0 до F5 дает:
F0 + F1 + F2 + F3 + F4 + F5 = 1 + 1 + 2 + 3 + 5 + 8 = 20 = F7 – 1.
Сложение чисел от F0 до F6 дает 33, что на единицу меньше F8 = 34. Мы можем записать формулу для неотрицательных целых чисел n:
F0 + F1 + F2 + … + Fn = Fn + 2–1. (*)
Вероятно, лично вам достаточно будет увидеть, что формула (*) работает в дюжине случаев, чтобы вы поверили, что она верна, но математики жаждут доказательств. Мы рады представить вам два возможных доказательства того, что она верна для всех неотрицательных целых чисел n. Первое называется доказательством по индукции, второе – комбинаторным доказательством.
Доказательство по индукции
Формула (*) представляет собой бесконечно много формул в свернутом виде. Доказать, что (*) верно для конкретного значения n, скажем для n = 6, – простая арифметическая задача. Достаточно будет записать числа от F0 до F6 и сложить их:
F0 + F1 + … + F6 = 1 + 1 + 2 + 3 + 5 + 8 + 13 = 33.
Несложно увидеть, что F8 = 34, поэтому формула действует.
Перейдем к F7. Не будем тратить время и складывать все числа: мы уже знаем сумму вплоть до F6. Таким образом,
(F0 + F1 + … + F6) + F7 = 33 + 21 = 54.
Как и раньше, все сходится: F9 = 55.
Если сейчас мы начнем проверять, работает ли формула для n = 8, наши силы окончательно иссякнут. Но все же посмотрим, что мы уже знаем и что хотим выяснить:
F0 + F1 + … + F7 = F9–1.F0 + F1 + … + F7 + F8 =?
Воспользуемся предыдущим результатом:
(F0 + F1 + … + F7) + F8 = (F9– 1) + F8.
Мы, конечно, можем вычислить (F9 – 1) + F8 арифметически. Но так мы устанем еще больше. В то же время мы знаем, что F8 + F9 = F10. Таким образом, нам не нужно ничего высчитывать или заглядывать в таблицу чисел Фибоначчи:
(F0 + F1 + … + F7) + F8 = (F9–1) + F8 = (F8 + F9) – 1 = F10– 1.
Мы удостоверились, что формула работает для n = 8, на основе того, что знали про n = 7.
В случае n = 9 мы точно так же опираемся на результат для n = 8 (убедитесь в этом самостоятельно). Разумеется, доказав верность (*) для n, мы можем быть уверены, что (*) верно и для n + 1.
Мы готовы дать полное доказательство. Как уже было сказано, (*) представляет собой бесконечное количество формул для всех значений n от нуля до бесконечности. Посмотрим, как работает доказательство.
Вначале мы доказываем (*) в простейшем случае, для n = 0. Мы просто проверяем, что F0 = F0 + 2 – 1. Так как F0 = 1, а F2 = 2, очевидным образом 1 = 2 – 1, а F0 = F2 – 1.
Дальше нам достаточно показать, что верность формулы для одного значения n (скажем, n = k) автоматически означает верность для n + 1 (в нашем примере n = k + 1). Нам лишь надо продемонстрировать, как устроено это «автоматически». Что нам нужно сделать?
Возьмем некоторое число k.
Предположим, мы уже знаем, что
F0 + F1 + … + Fk = Fk + 2– 1.
Мы ищем величину
F0 + F1 + … + Fk + Fk + 1.
Мы уже знаем сумму чисел Фибоначчи вплоть до Fk, поэтому у нас получается:
(F0 + F1 + … + Fk) + Fk + 1 = (Fk + 2–1) + Fk + 1.
Правая часть равна Fk + 2 – 1 + Fk + 1, и мы знаем, чему равна сумма следующих друг за другом чисел Фибоначчи:
Fk + 2–1 + Fk + 1 = (Fk + 2 + Fk + 1) – 1 = Fk + 3– 1
Подставим в наше равенство:
(F0 + F1 + … + Fk) + Fk + 1 = Fk + 3– 1
Сейчас я объясню, что мы сделали. Если мы знаем, что (*) верно, когда мы суммируем числа вплоть до Fk, тогда (*) должно быть верно, если мы приплюсуем Fk + 1.
Подытожим:
• Формула (*) верна для n = 0.
• Если формула (*) верна для n, она верна и для n + 1.
Мы можем уверенно сказать, что (*) верно для любых значений n. Верно ли (*) для n = 4987? Это так, если выражение верно для n = 4986, что основано на верности выражения для n = 4985, и так далее до n = 0. Следовательно, формула (*) верна для всех возможных значений n.
Этот метод доказательства известен под названием математическая индукция (или доказательство по индукции). Мы проверяем базовый случай и даем шаблон, по которому каждый следующий случай может быть доказан на основе предыдущего.
Комбинаторное доказательство
