Ознакомительная версия. Доступно 10 страниц из 62
при добавлении следующего нечетного числа (2k + 1) у нас получится
1 + 3 + 5 +… + (2k – 1) + (2k + 1) = k² + (2k + 1) = (k + 1)²Другими словами, если сумма первых k нечетных чисел равна k², то сумма первых k + 1 нечетных чисел обязательно будет равна (k + 1)². Значит, теорема, истинная в отношении n = 1, будет столь же истинной в отношении любого значения n.◻
Индукция – инструмент действенный. Эта книга начиналась с проблемы определения суммы первых n чисел. Разными путями мы пришли к тому, что
Это предположение, безусловно, правдиво при n = 1 (потому что 1 = 1(2)/2). Предположим, что оно правдиво и для числа k:
Тогда, прибавив к этой сумме (k + 1), получим
В этой формуле k + 1 использовано вместо n. Значит, если она верна для n = k (где под k может скрываться любое положительное число), она будет так же верна и для n = k + 1. Равно как и для любого положительного значения n.◻
В этой главе (да и в книге вообще) будет еще много примеров использования индуктивного метода. А пока для закрепления материала вот вам песня, написанная «музыкантами от математики» Дэйном Кэмпом и Ларри Лессером на мотив знаменитой «Blowin' in the Wind» Боба Дилана.
Откуда нам знать, что теорема верна
С любым значением n?
Миллиард вариантов – все не перебрать,
Никак не свести в один.
Но как же иначе найти нам ответ,
Чтоб не свалиться в сплин?
Индукция, друг мой, – вот наш господин.
Индукция – наш господин.
Сначала находим, с чего бы начать,
К чему наш закон примени́м,
Потом переносим все это на k,
Потом – и на k + 1.
Ну а дальше легко – ведь эффект домино
Нисколечко не отмени́м.
Индукция, друг мой, – вот наш господин.
Индукция – наш господин!
n раз повторю, да хоть n + 1:
Индукция – наш господин!
В главе 5 мы рассмотрели несколько задач, основанных на числах последовательности Фибоначчи. Попробуем доказать парочку из них, используя метод индукции.
Теорема: Для n ≥ 1
F1 + F2 +… + Fn = Fn+2 – 1Доказательство (методом индукции): Если n = 1, то F1 = F3 – 1, что соответствует 1 = 2 – 1, что безусловно истинно. Применим это к n = k, то есть
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 равных сектора, как на рисунке выше.
Сектор с квадратиком имеет размер 2k на 2k, что значит, что его можно полностью выложить тримино (исходя из того, что наше утверждение истинно при n = k). Затем положим одну костяшку тримино в центр доски так, чтобы она находилась одновременно в трех оставшихся секторах, каждый из которых также равен 2k на 2k и в каждом из которых у нас теперь есть по одному квадратику, что делает их абсолютно похожими на первый. Ну а если можно полностью выложить неперекрывающимися тримино каждую часть (размером 2k на 2k) доски, то ими можно выложить и всю доску размером 2k+1 на 2k+1.☺
Ознакомительная версия. Доступно 10 страниц из 62
