Доказательство методом индукции
Вернемся к теоремам о положительных числах. В главе 1 мы выяснили, что
и предположили, что сумма первых n нечетных чисел равна n?. Позже мы это подтвердили, причем очень красиво и остроумно – с помощью комбинаторного доказательства, подсчитав двумя разными способами количество клеток на шахматной доске. А почему бы нам не попробовать другой метод – пусть и не такой эффектный, но при этом ничуть не менее эффективный. Предположим, я сказал вам (или вы просто верите в то), что первые 10 нечетных чисел 1 + 3 +… + 19 дают в сумме 10? = 100. Если вы с этим согласны, значит, прибавление следующего нечетного числа – 21 – даст нам уже 121, что равно 11?. Другими словами, если мое утверждение правдиво для десяти чисел, оно будет правдивым и для одиннадцатого. В этом и состоит суть математического доказательства по индукции: сначала мы доказываем, что некое утверждение относительно числа n является изначально верным (обычно при n = 1), а затем показываем, что, если это верно для n = k, оно останется автоматически верным для n = k + 1 и так далее – для любого значения n. Доказательство по индукции подобно подъему по лестнице: поднявшись на первую ступеньку, вы имеете все основания и все возможности подняться и на вторую. Ну а старая добрая логика настойчиво подсказывает, что так вы рано или поздно сможете оказаться и на пятой, и на десятой, и на n-ной ступени.
Так, в примере с первыми n нечетными числами наша задача – показать, что при любом значении n ? 1
1 + 3 + 5 +… + (2n – 1) = n?
Мы видим, что сумма самого первого нечетного числа – 1 – и в самом деле составляет 1?, то есть для n = 1 наше предположение абсолютно верно. Дальше нам следует обратить внимание на то, что, если сумма первых k нечетных чисел составляет k?, а именно
1 + 3 + 5 +… + (2k – 1) = k?
при добавлении следующего нечетного числа (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.?
Последнее тождество имеет много полезных применений. Давайте докажем его по индукции, добавив парочку других способов. Какова сумма первых n чисел, которые получаются при возведении 2 в последовательные степени, начиная с 20 = 1?
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024…
Приступим к сложению:
Видите закономерность? Каждая сумма на 1 меньше следующего числа, получаемого от возведения 2 в степень. Все это сводится вот к чему.
Теорема: Для n ? 1
1 + 2 + 4 + 8 +… + 2n–1 = 2n – 1
Доказательство по индукции: Как мы уже отмечали, утверждение является верным при n = 1 (а также 2, 3, 4 и 5). При n = k мы можем утверждать, что
1 + 2 + 4 + 8 +… + 2k–1 = 2k – 1
Добавив к обеим частям следующее число, получаемое при возведении 2 в степень (то есть 2k), приходим к
1 + 2 + 4 + 8 +… + 2k–1 + 2k = (2k – 1) + 2k = 2 ? 2k – 1 = 2k+1 – 1 ?
В 4 и 5 главах мы подтвердили множество закономерностей, находя ответ двумя разными способами. Возможно, комбинаторный подход покажется вам наиболее ценным.
Вопрос: В хоккейной команде n игроков (соответственно, их свитера пронумерованы от 1 до n). Созывается пресс-конференция, на которую должен прийти хотя бы один игрок. Чему равно количество возможных «составов» команды на этой пресс-конференции?
Ответ 1: У каждого игрока два варианта: идти или не идти. Значит, у команды в целом есть 2n вариантов. Но из этого числа нам нужно вычесть единицу, чтобы исключить вероятность того, что на конференцию не придет никто. В итоге получается 2n – 1.
Ответ 2: За основу «состава» положим хоккеиста с наибольшим номером на свитере. «Состав» с единицей в качестве наибольшего числа всего 1, с двойкой их 2 (потому что хоккеист № 2 может пойти либо в одиночестве, либо в компании хоккеиста № 1), с тройкой – 4 (потому что хоккеист № 3 может пойти либо один, либо в компании хоккеиста № 2, который точно так же может позвать, а может и не позвать с собой хоккеиста № 1). Следуя этой логике и дальше, мы увидим, что всего возможных «составов» будет 2n–1, ведь хоккеист № n будет обязан пойти на конференцию, а у каждого из его товарищей (начиная с № 1 и заканчивая № n – 1), которых он может позвать с собой, будет по 2 варианта выбора. То есть 1 + 2 + 4 +… + 2n–1.
Оба результата верны, а значит, равны. Таким образом, получается, что 1 + 2 + 4 +… + 2n–1 = 2n – 1.?
При всех достоинствах комбинаторного метода наиболее простым здесь будет алгебраический – схожий с тем, который мы использовали для преобразования периодической десятичной дроби в простую.
Алгебраическое доказательство:
Пусть S = 1 + 2 + 4 + 8 +… + 2n–1.
Удвоив обе части, получим
2S = 2 + 4 + 8 +… + 2n–1 + 2n
Вычтем первое уравнение из второго, что позволит нам избавиться от всего лишнего и оставить только S из первого и 2S из второго, то есть
S = 2S – S = 2n – 1
Теорема эта – ключ к двоичной системе, имеющей огромное практическое значение: именно на ее основе проводят числовые операции все компьютеры. Смысл ее заключается в том, чтобы представить любое число как уникальную сумму различных степеней основания числа 2. Например,
83 = 64 + 16 + 2 + 1
Запишем это двоичным кодом, заменяя каждое возведенное в степень число 2 единицей, а каждое пропущенное значение 2 в степени – нолем. В нашем примере это 83 = (1 ? 64) + (0 ? 32) + (1 ? 16) + (0 ? 8) + (0 ? 4) + (1 ? 2) + (1 ? 1). Следовательно, в двоичной системе число 83 выглядит так:
83 = (1010011)2
Как удостовериться, что в таком виде можно представить любое положительное число? Предположим, что каждое число от 1 до 99 есть уникальная сумма степеней основания 2. Сможем ли мы представить в столь же уникальном виде число 100? Начнем с наибольшей степени основания 2, которая меньше 100, то есть с 64. (Почему именно 64? Да потому что меньшие значения – 1, 2, 4, 8, 16 и 32 – дадут в сумме лишь 63, а значит, 100 нам никак не получить.) Остается добрать 36 – точно так же, с помощью чисел, которые получаются от возведения 2 в разные степени. Как это сделать? Проще всего – следуя той же логике, что и с сотней, то есть начать с самого большого подходящего нам числа. Так как 36 = 32 + 4, значит 100 = 64 + 32 + 4, в двоичной системе – (1100100)2. Обобщив это (с помощью так называемого убедительного индуктивного подтверждения), приходим к выводу, что любое положительное число имеет уникальное двоичное представление.