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

F1 + F2 +… + Fk = Fk+2 – 1

Добавив к обеим частям число Фибоначчи Fk+1, получим

F1 + F2 +… + Fk + Fk+1 = Fk+1 + Fk+2 – 1 = Fk+3 – 1

что и требовалось доказать.

Столь же простым будет доказательство для суммы квадратов чисел Фибоначчи.

Теорема: Для n ≥ 1

F1² + F2² +… + Fn² = FnFn+1

Доказательство (методом индукции): Если n = 1, то F1² = F1F2, что верно потому, что F2 = F1 = 1. Применив это к n = k, получаем

F1² + F2² +… + Fk² = FkFk+1

А теперь добавим к обеим сторонам F²k+1:

F1² + F2² +… + Fk² + F²k+1 = FkFk+1 + F²k+1 = Fk+1(Fk + Fk+1) = Fk+1 + Fk+2

что и требовалось доказать.

В главе 1 мы выяснили, что сумма кубов равна квадрату суммы, то есть

но тогда мы не были готовы это доказать. Просто мы ничего не знали об индукции. При n ≥ 1 общая закономерность выглядит так:

1³ + 2³ + 3³ +… + n³ = (1 + 2 + 3 +… + n)²

А так как нам уже известно, что докажем схожую теорему.

Теорема: Для n ≥ 1

Доказательство (методом индукции): При n = 1 предположим, что 1³ = 1²(2²)/4, что истинно. Следовательно, если схожее предположение будет истинным и при n = k, теорема будет доказана:

Прибавим к обеим сторонам (k + 1)³ и получим

что и требовалось доказать.

Отступление

А вот геометрическое доказательство тождества суммы кубов.

Посчитаем площадь фигуры двумя разными способами, а потом сравним результаты. С одной стороны, перед нами явно квадрат, каждая из сторон которого равна 1 + 2 + 3 + 4 + 5, а общая площадь, таким образом, – (1 + 2 + 3 + 4 + 5)².

С другой стороны, если начать с верхнего левого угла, а затем двигаться вниз по диагонали, мы пройдем последовательно через один квадрат размером 1 на 1, два размером 2 на 2 (один из которых разбит на два прямоугольника), три квадрата размером 3 на 3, четыре размером 4 на 4 (и еще один «разрезанный» пополам) и, наконец, пять квадратов размером 5 на 5. Следовательно, их общая площадь будет равна

(1 × 1²) + (2 × 2²) + (3 × 3²) + (4 × 4²) + (5 × 5²) = 1³ + 2³ + 3³ + 4³ + 5³

Так как обе полученные нами площади должны быть равны, имеем

1³ + 2³ + 3³ + 4³ + 5³ = (1 + 2 + 3 + 4 + 5)²

То же можно сделать и с квадратом со сторонами длиной 1 + 2 +… + n, чтобы прийти к

1³ + 2³ + 3³ +… + n³ = (1 + 2 + 3 +… + n)²☺

Доказательство методом индукции применяется не только при сложении – оно отлично работает всякий раз, когда некую «большую» проблему (вроде k + 1) можно решить посредством «маленькой» (вроде k). Приведу вам свою любимую теорему, вроде той, что мы доказывали в начале главы, когда решали проблему с заполнением шахматной доски костяшками домино. Однако на этот раз поговорим не о невозможности, а наоборот, о возможности, причем возможности постоянной, а вместо домино используем тримино[16] L-образной формы.

Так как 64 (число клеток) на 3 не делится, одних лишь тримино для всей площади шахматной доски нам явно не хватит. Но стоит взять дополнительно один квадратик размером 1 на 1, и можно смело утверждать, что вне зависимости от его (квадратика) положения на доске для всего остального хватит тримино. Причем утверждение это справедливо не только для обычных шахматных досок 8 на 8, но и для досок размером 2 на 2, 4 на 4, 16 на 16 и т. д.

Теорема: Для любого значения n ≥ 1 шахматная доска размером 2n на 2n может быть выложена костяшками тримино и одним квадратиком размером 1 на 1 при любом положении последнего.

Доказательство (методом индукции): Утверждение является истинным при n = 1, потому что для того, чтобы выложить доску размером 2 на 2, достаточно одной костяшки тримино и одного квадратика (при любом его положении). Попробуем доказать то же в отношении n = k, то есть доски размером 2k на 2k (притом что нашей конечной целью остается 2k+1 на 2k+1). Сначала положим квадратик на любое место. Потом разделим доску на 4 равных сектора, как на рисунке выше.