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

Отступление

В главе 5 мы рассмотрели несколько задач, основанных на числах последовательности Фибоначчи. Попробуем доказать парочку из них, используя метод индукции.

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

F₁ +F₂ +… +F_n=F_n+2 – 1

Доказательство (методом индукции): Если n = 1, то F₁ = F₃ – 1, что соответствует 1 = 2 – 1, что безусловно истинно. Применим это к n = k, то есть

F₁ +F₂ +… +F_k=F_k+2 – 1

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

F₁ +F₂ +… +F_k+F_k+1 =F_k+1 +F_k+2 – 1 =F_k+3 – 1

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

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

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

F₁² +F₂² +… +F_n² =F_nF_n+1

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

F₁² +F₂² +… +F_k² =F_kF_k+1

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

F₁² +F₂² +… +F_k² +F²_k+1 =F_kF_k+1+F²_k+1 =F_k+1(F_k + F_k+1) =F_k+1+F_k+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-образной формы.