Последовательности и индукция

Прошлая глава началась с шахматной доски: на первую клетку одно зерно, на вторую два, на третью четыре, и так до шестьдесят четвёртой. Всего зёрен, как мы там сказали, $2^{64} - 1$. Эту сумму мы приняли на веру. Складывать по одному шестьдесят четыре числа, последнее из которых девятнадцатизначное, никто не стал. Но слагаемые подчиняются правилу, каждое вдвое больше предыдущего, а сумму по правилу можно получить сразу, не складывая слагаемые по одному. В этой главе мы научимся так делать.

Есть и вопрос серьёзнее. Формулу для суммы легко проверить при $n = 1, 2, 3$ и даже при $n = 1000$, но значений $n$ бесконечно много, и никакой компьютер их все не переберёт. Как убедиться, что формула верна всегда? Ответ похож на детскую забаву. Поставьте костяшки домино в ряд так, чтобы каждая, падая, задевала следующую, и толкните первую. Упадут все, сколько бы их ни было, и смотреть на каждую не нужно: достаточно знать, что первая упадёт и что любая упавшая уронит соседку. Эта картина пройдёт через всю главу. Каждую формулу мы сначала найдём — хитростью, картинкой или догадкой, — а потом докажем для всех $n$ сразу.

Сто слагаемых

Самую знаменитую сумму в истории математики пересказывают так. В школе Брауншвейга учитель, желая надолго занять класс, велел сложить все числа от $1$ до $100$. Едва он успел сесть, как девятилетний Карл Фридрих Гаусс положил перед ним грифельную доску с одним числом: $5050$. У остальных учеников ответы появились только к концу урока, и почти все неверные.

Каким бы ни был ряд, приём, которым, по всей видимости, воспользовался мальчик, стоит знать. Выпишем сумму дважды: сначала по возрастанию, потом по убыванию, одну строку под другой.

$$\begin{array}{rcccccccccccc} S &=& 1 &+& 2 &+& 3 &+& \dots &+& 99 &+& 100 \\ S &=& 100 &+& 99 &+& 98 &+& \dots &+& 2 &+& 1 \\ \hline 2S &=& 101 &+& 101 &+& 101 &+& \dots &+& 101 &+& 101 \end{array}$$

В каждом столбце одно слагаемое на единицу больше предыдущего, а другое на единицу меньше, поэтому сумма в столбце не меняется: всюду $101$. Столбцов сто, значит, $2S = 100 \cdot 101 = 10\,100$ и $S = 5050$. Одно сложение, одно умножение, одно деление.

Ничего в этом приёме не зависит от числа $100$. Его можно нарисовать, и тогда он доказывает формулу для любого числа слагаемых сразу.

Идея: приложить сумму к самой себе так, чтобы получилась фигура с легко считаемой площадью. Выложим слагаемые столбиками из клеток: в первом столбике $1$ клетка, во втором $2$, в последнем $n$. Получилась лесенка площадью $S = 1 + 2 + \dots + n$. Возьмём вторую такую же лесенку. Её площадь тоже $S$, вместе у двух лесенок $\p3{2}S$. Перевернём копию вверх ногами и поставим на первую лесенку. Столбики копии теперь идут в обратном порядке, от $n$ до $1$, поэтому над столбиком высоты $k$ оказывается столбик высоты $n + 1 - k$. Значит, каждый столбец фигуры имеет высоту $k + (n + 1 - k) = \p2{n + 1}$, одну и ту же при любом $k$, а столбцов $\p1{n}$. Две лесенки без щелей и наложений заполнили прямоугольник $n \times (n + 1)$. Площадь прямоугольника $n(n + 1)$ равна $2S$, откуда $S = \frac{n(n + 1)}{2}$. Мы ни разу не пользовались тем, чему равно $n$, так что формула верна при любом $n$.

Часы с боем каждый час бьют столько раз, сколько показывает часовая стрелка: в час — один раз, в двенадцать — двенадцать. Сколько ударов они делают за сутки?

За один оборот стрелки часы бьют $1 + 2 + \dots + 12 = \frac{12 \cdot 13}{2} = 78$ раз, а за сутки стрелка обходит циферблат дважды: $2 \cdot 78 = 156$ ударов.

Гауссу повезло: у его суммы нашлась хитрость, которая сразу работает для всех $n$. Так везёт не всегда. Часто формулу удаётся угадать по нескольким примерам, а объясняющей её хитрости не видно. Тогда нужны костяшки домино.

Как уронить бесконечный ряд

Сложим подряд первые нечётные числа:

$$1 = 1, \qquad 1 + 3 = 4, \qquad 1 + 3 + 5 = 9, \qquad 1 + 3 + 5 + 7 = 16.$$

Выходят квадраты: $1^2$, $2^2$, $3^2$, $4^2$. В главе 0 мы видели, как такие совпадения обманывают, и пообещали, что этот ряд не обманет. Пора это доказать. Обозначим через $P(n)$ утверждение «сумма первых $n$ нечётных чисел равна $n^2$». Утверждений на самом деле бесконечно много — $P(1)$, $P(2)$, $P(3)$, … — и каждое из них — костяшка в бесконечном ряду.

Уронить все костяшки можно в два приёма. Сначала толкнуть первую: проверить $P(1)$. Потом убедиться, что ряд расставлен правильно: любая упавшая костяшка роняет следующую, то есть из $P(k)$ следует $P(k + 1)$ — при любом $k$, а не при каком-то одном.

База, $n = 1$: слева одно слагаемое $1$, справа $1^2 = 1$. На картинке это одна клетка, квадрат $1 \times 1$. Первая костяшка упала. Предположение: пусть для какого-то $k$ уже известно, что $1 + 3 + \dots + (2k - 1) = k^2$, то есть первые $k$ нечётных чисел укладываются квадратом $k \times k$. Каким бы ни было $k$ (его меняет ползунок), рассуждение то же. Следующее нечётное число — $\p1{2k + 1}$. Разложим его клетки уголком: $k$ клеток вдоль правой стороны квадрата, $k$ клеток вдоль нижней и одна клетка в углу. Всего $k + k + 1 = 2k + 1$. Приложим уголок к квадрату. Обе стороны удлинились на единицу, получился квадрат $(k + 1) \times (k + 1)$. В буквах это $k^2 + (2k + 1) = (k + 1)^2$ — формула квадрата суммы из главы о буквах. Значит, из $P(k)$ следует $P(k + 1)$. База верна, и шаг доказан для любого $k$. По принципу индукции, о котором ниже, формула верна при всех $n$.

Мы воспользовались правилом, которое пора записать явно.

Идея: если бы цепочка где-то оборвалась, у обрыва было бы начало, и именно там шаг не сработал бы. Допустим противное: база и шаг есть, но $P(n)$ верно не при всех $n$. На языке домино — в ряду остались стоящие костяшки. Среди номеров стоящих костяшек есть наименьший: в любом непустом множестве натуральных чисел есть наименьшее число. Назовём его $m$. Это первая стоящая костяшка: $P(m)$ неверно, а все $P$ с меньшими номерами верны. $m \ne 1$, потому что по базе $P(1)$ верно — первая костяшка упала. Значит, $m \ge 2$, и $m - 1$ — тоже натуральное число. Костяшка $m - 1$ стоит раньше первой стоящей, поэтому она упала: $P(m - 1)$ верно. Шаг, применённый при $k = m - 1$, говорит: из $P(m - 1)$ следует $P(m)$. Упавшая костяшка $m - 1$ обязана уронить костяшку $m$, а мы выбрали $m$ стоящей. Противоречие. Значит, стоящих костяшек нет: $P(n)$ верно при всех натуральных $n$.

Честности ради: доказательство опирается на свойство «в любом непустом множестве натуральных чисел есть наименьшее». Оно и принцип индукции выводятся одно из другого, это два лица одного свойства натуральных чисел. Джузеппе Пеано в 1889 году включил индукцию прямо в аксиомы арифметики; об аксиомах — в главе о логике и множествах.

Шаг часто вызывает подозрение: не доказываем ли мы то, что сами предположили? Нет. Мы не утверждаем, что $P(k)$ верно, а доказываем связь: если костяшка $k$ упадёт, она уронит костяшку $k + 1$. Упадёт ли она на самом деле, решают база и цепочка шагов до неё.

Индукцией можно передоказать и формулу Гаусса. База: $1 = \frac{1 \cdot 2}{2}$. Шаг: прибавим $k + 1$ к обеим частям равенства $1 + 2 + \dots + k = \frac{k(k+1)}{2}$:

$$\frac{k(k + 1)}{2} + (k + 1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k + 1)(k + 2)}{2},$$

а это формула Гаусса при $n = k + 1$. Лесенка объясняет, почему формула такая, индукция проверяет, что она верна. Хорошо иметь и то и другое.

Что из этого доказывает, что утверждение $P(n)$ верно при всех натуральных $n$?

$P(1), P(2), \dots, P(10^{9})$ проверены на компьютере $P(1)$ верно, и из $P(k)$ следует $P(k + 1)$ при любом $k$ Из $P(k)$ следует $P(k + 1)$ при любом $k$ $P(1)$ верно, и из $P(1)$ следует $P(2)$

Нужны обе части: база запускает цепочку, а шаг, доказанный для произвольного $k$, передаёт её дальше без конца.

В обычной речи «индукция» — вывод от частного к общему: солнце всходило каждое утро, значит, взойдёт и завтра. Математическая индукция устроена иначе: это строгий вывод, просто цепочка его шагов бесконечна.

Прогрессия с шагом

У Гаусса каждое слагаемое было на единицу больше предыдущего. Шаг бывает и другим, и такие ряды удобно обсуждать в общем виде.

Задать последовательность можно формулой $n$-го члена, например $a_n = n^2$: $1, 4, 9, 16, \dots$ А можно правилом, по которому следующий член получается из предыдущих. Например, $a_1 = 1$ и $a_{n+1} = 2a_n + 1$ дают $1, 3, 7, 15, 31, \dots$

Рекуррентное правило — готовый ряд домино: первый член — база, правило — шаг. Отсюда и главный способ что-то о таких последовательностях доказывать.

Примеры: $5, 8, 11, 14, \dots$ (разность $3$); $10, 7, 4, 1, -2, \dots$ (разность $-3$, прогрессия убывает); $7, 7, 7, \dots$ (разность $0$). Номера домов на чётной стороне улицы — прогрессия с разностью $2$.

Идея: от первого члена до $n$-го идём шагами, и каждый шаг прибавляет одно и то же число. Начинаем с первого члена $\p1{a_1}$. По определению прогрессии каждый следующий член равен предыдущему плюс $\p3{d}$: $a_2 = a_1 + d$, $a_3 = a_2 + d = a_1 + 2d$, и так далее. От $a_1$ до $a_n$ — $\p2{n - 1}$ шагов: шагов на один меньше, чем членов, как пролётов в заборе на один меньше, чем столбов. Каждый шаг добавил $d$, всего добавилось $(n - 1)d$. Значит, $a_n = a_1 + (n - 1)d$. Слова «и так далее» строго заменяет индукция: при $n = 1$ формула даёт $a_1$, а если $a_k = a_1 + (k - 1)d$, то $a_{k+1} = a_k + d = a_1 + kd$.

Почему прогрессию назвали арифметической? Каждый её член, кроме первого, — среднее арифметическое своих соседей: $a_n = \frac{a_{n-1} + a_{n+1}}{2}$, ведь левый сосед меньше на $d$, а правый больше на $d$. В ряду $5, 8, 11$ восьмёрка ровно посередине: $\frac{5 + 11}{2} = 8$.

Теперь сумма. Лесенка Гаусса работает и здесь, только ступеньки бывают любой высоты.

Идея та же, что у Гаусса. Выложим члены прогрессии столбиками: высоты $a_1, a_2, \dots, a_n$, каждая на $d$ больше предыдущей. Площадь лесенки — $S_n$. Ползунки меняют $a_1$, $d$ и $n$; на картинке $d \ge 0$, но в выкладках ниже знак $d$ нигде не важен. Возьмём такую же лесенку, её площадь тоже $S_n$. Перевернём её и поставим сверху. Столбики копии идут от $a_n$ к $a_1$, поэтому над столбиком $a_k$ оказывается столбик $a_{n+1-k}$. По формуле $n$-го члена $a_k = a_1 + (k - 1)d$, а $a_{n+1-k} = a_1 + (n - k)d$, то есть $a_n - (k - 1)d$. Сложим: $a_k + a_{n+1-k} = \p1{a_1 + a_n}$. На сколько своя лесенка выше $a_1$, на столько копия ниже $a_n$, и все столбцы одной высоты. Столбцов $\p2{n}$: получился прямоугольник. Площадь прямоугольника $(a_1 + a_n) \cdot n$ — это две лесенки, $2S_n$. Делим пополам и получаем формулу.

В амфитеатре $20$ рядов. В первом ряду $12$ мест, а в каждом следующем на $3$ больше, чем в предыдущем. Сколько всего мест в амфитеатре?

Места по рядам образуют прогрессию с $a_1 = 12$ и $d = 3$. В последнем ряду $a_{20} = 12 + 19 \cdot 3 = 69$ мест. Всего $S_{20} = \frac{(12 + 69) \cdot 20}{2} = 81 \cdot 10 = 810$.

Прогрессия с множителем

Вернёмся к шахматной доске. На каждой клетке зёрен вдвое больше, чем на предыдущей: шаг здесь не прибавляется, а умножается.

Примеры: $1, 2, 4, 8, \dots$ ($q = 2$, это доска); $3, -6, 12, -24, \dots$ ($q = -2$, знаки чередуются); $1000, 100, 10, 1, 0{,}1, \dots$ ($q = \frac{1}{10}$). Нули запрещены: после нуля шли бы одни нули, и знаменатель было бы не восстановить. Название объясняется так же, как у арифметической: каждый член положительной геометрической прогрессии, кроме первого, — среднее геометрическое соседей, $b_n = \sqrt{b_{n-1} b_{n+1}}$. В ряду $2, 4, 8$ четвёрка — это $\sqrt{2 \cdot 8}$.

Идея та же, что для арифметической прогрессии, только шаг — умножение. Начинаем с первого члена $\p1{b_1}$. Каждый следующий член — предыдущий, умноженный на $\p2{q}$: $b_2 = b_1 q$, $b_3 = b_2 q = b_1 q^2$, и так далее. От $b_1$ до $b_n$ — $\p3{n - 1}$ шагов, и на каждом появляется множитель $q$: всего $\underbrace{q \cdot q \cdot \ldots \cdot q}_{n - 1} = q^{n-1}$. Значит, $b_n = b_1 q^{n-1}$. Индукцией: $b_1 = b_1 q^0$, и из $b_k = b_1 q^{k-1}$ следует $b_{k+1} = b_k q = b_1 q^k$.

Геометрическая прогрессия — это показательный рост из прошлой главы, увиденный целыми шагами. Теперь сумма, ради которой всё затевалось. Приём Гаусса здесь не помогает: перевернув ряд $1 + 2 + 4 + \dots + 2^{63}$, одинаковых столбцов не получишь. Нужна другая хитрость.

Идея: умножение на знаменатель сдвигает прогрессию на одно место, и почти все слагаемые у суммы и её сдвига общие. Запишем сумму строкой: $S = b_1 + b_1 q + \dots + b_1 q^{n-1}$. На картинке $b_1 = 1$; при другом $b_1$ каждая клетка просто умножится на $b_1$. Умножим сумму на $q$, умножив на $q$ каждое слагаемое (распределительный закон): $qS = b_1 q + b_1 q^2 + \dots + b_1 q^n$. Каждое слагаемое превратилось в следующее, и строка сдвинулась на одно место вправо. Слагаемые $b_1 q, \dots, b_1 q^{n-1}$ стоят в обеих строках. При вычитании $qS - S$ они взаимно уничтожаются. Остаются только крайние: последняя клетка нижней строки $\p2{b_1 q^n}$ и первая клетка верхней $\p1{b_1}$. Получаем $qS - S = b_1 q^n - b_1$, то есть $S(q - 1) = b_1(q^n - 1)$. Если $q \ne 1$, делим обе части на $\p3{q - 1}$ и получаем $S_n = b_1 \cdot \frac{q^n - 1}{q - 1}$.

Для доски $b_1 = 1$, $q = 2$, $n = 64$, и сумма равна $2^{64} - 1 = 18\,446\,744\,073\,709\,551\,615$. Долг прошлой главы закрыт.

Вы получили «письмо счастья» и разослали его троим знакомым. Каждый из них тоже отправил письмо троим, и так шесть кругов: в каждом круге каждый новый получатель пишет троим новым людям. Сколько писем отправлено всего, включая ваши три?

По кругам писем $3, 9, 27, \dots$ — геометрическая прогрессия с $b_1 = 3$ и $q = 3$, в ней шесть членов. Всего $S_6 = 3 \cdot \frac{3^6 - 1}{3 - 1} = 3 \cdot \frac{728}{2} = 1092$. Будь кругов не шесть, а двадцать один, писем вышло бы $S_{21} = \frac{3(3^{21} - 1)}{2} \approx 1{,}6 \cdot 10^{10}$ — вдвое больше, чем людей на Земле.

Ахиллес и черепаха

Около двух с половиной тысяч лет назад Зенон Элейский придумал рассуждение, которое дошло до нас в пересказе Аристотеля. Быстроногий Ахиллес бежит за черепахой. Пока он добегает до места, где черепаха была, она успевает немного отползти, пока он пробегает этот кусок — ещё немного, и так без конца. Значит, заключал Зенон, Ахиллес никогда её не догонит.

Возьмём числа. Пусть Ахиллес бежит со скоростью $10$ м/с, черепаха ползёт в десять раз медленнее, $1$ м/с (очень быстрая черепаха), а фора у неё $100$ м. Ахиллес пробегает $100$ м за $10$ с — черепаха отползла на $10$ м. Эти $10$ м он пробегает за $1$ с — она уползла ещё на $1$ м. Дальше $0{,}1$ с, потом $0{,}01$… Этапов бесконечно много, а их длительности — геометрическая прогрессия со знаменателем $\frac{1}{10}$:

$$10 + 1 + 0{,}1 + 0{,}01 + \dots = 11{,}111\dots = 11{,}(1) \text{ с}.$$

Бесконечно много слагаемых дали конечную сумму, $\frac{100}{9}$ секунды. Тот же ответ получается и без всяких этапов: Ахиллес приближается к черепахе на $10 - 1 = 9$ м каждую секунду, и сто метров форы исчезнут за $\frac{100}{9}$ с. Зенон был прав, что этапов бесконечно много, но ошибался, думая, что на бесконечно много этапов нужно бесконечно много времени.

Сложить бесконечно много слагаемых по одному нельзя, зато можно складывать первые $n$ и смотреть, к чему подбираются такие частичные суммы.

Идея: следить не за суммой, а за тем, сколько ей не хватает до числа $L = \frac{b_1}{1 - q}$. Первый член $\p1{b_1}$ — первая полоска. Заметим, что $b_1 = (1 - q)L$: так число $L$ и выбрано. На картинке $b_1 = 1$, знаменатель $q$ меняет ползунок. После первого слагаемого до $L$ не хватает $L - b_1 = L - (1 - q)L = qL$. По формуле суммы из прошлого раздела $S_n = b_1 \cdot \frac{1 - q^n}{1 - q} = L(1 - q^n)$, поэтому недостача после $n$ слагаемых равна $L - S_n = \p2{q}^n L$. Каждое новое слагаемое уменьшает её в $\frac{1}{|q|}$ раз. При отрицательном $q$ суммы перескакивают через $L$ то вправо, то влево — сдвиньте ползунок. Если $\p3{|q| < 1}$, число $|q|^n$ становится меньше любого положительного числа, стоит взять $n$ побольше: $0{,}5^{10} < 0{,}001$, $0{,}5^{20} < 0{,}000\,001$. Почему так при любом $|q| < 1$ — в раскрывашке ниже. Значит, и недостача $|L - S_n| = |q|^n |L|$ становится сколь угодно малой. Суммы $S_n$ подходят к $L$ сколь угодно близко, и по определению сумма бесконечной прогрессии равна $L = \frac{b_1}{1 - q}$.

Почему $|q|^n$ становится сколь угодно малым

Пусть $0 < |q| < 1$ (при $q = 0$ доказывать нечего). Тогда $\frac{1}{|q|} > 1$, запишем $\frac{1}{|q|} = 1 + h$ с $h > 0$. Докажем индукцией неравенство Бернулли: $(1 + h)^n \ge 1 + nh$. База: $(1 + h)^1 = 1 + h$. Шаг: если $(1 + h)^k \ge 1 + kh$, умножим обе части на положительное $1 + h$:

$$(1 + h)^{k+1} \ge (1 + kh)(1 + h) = 1 + (k + 1)h + kh^2 \ge 1 + (k + 1)h.$$

Значит, $|q|^n = \frac{1}{(1 + h)^n} \le \frac{1}{1 + nh}$. Какое бы маленькое положительное число $\varepsilon$ нам ни назвали, при $n > \frac{1}{h\varepsilon}$ получится $1 + nh > \frac{1}{\varepsilon}$ и $|q|^n < \varepsilon$. Такие рассуждения «для любого $\varepsilon$ найдётся $n$» — язык пределов, о них подробно в главе о пределах, а бесконечным суммам любого вида посвящена глава о рядах.

Теперь можно ещё раз посмотреть на равенство, которое многих смущало в главе о дробях.

Запишите периодическую дробь $0{,}(12) = 0{,}121212\dots$ в виде несократимой обыкновенной дроби, сложив геометрическую прогрессию.

$0{,}(12) = \frac{12}{100} + \frac{12}{10\,000} + \dots$ — прогрессия с $b_1 = \frac{12}{100}$ и $q = \frac{1}{100}$. Сумма равна $\frac{12/100}{1 - 1/100} = \frac{12/100}{99/100} = \frac{12}{99} = \frac{4}{33}$. Проверка делением: $4 : 33 = 0{,}1212\dots$

Чему равна сумма $1 + 2 + 4 + 8 + 16 + \dots$ (без конца)?

$-1$, по формуле $\frac{1}{1 - 2}$ Никакому числу: суммы $2^n - 1$ растут без предела $2^{64} - 1$, как на шахматной доске

Сумма первых $n$ слагаемых равна $2^n - 1$ и становится больше любого наперёд заданного числа. Конечной суммы у такого ряда нет.

Кубы, сложенные в квадрат

Нечётные числа складывались в квадраты. Сложим теперь кубы:

$$1^3 = 1, \quad 1^3 + 2^3 = 9, \quad 1^3 + 2^3 + 3^3 = 36, \quad 1^3 + 2^3 + 3^3 + 4^3 = 100.$$

Снова квадраты, причём квадраты треугольных чисел: $1 = 1^2$, $9 = 3^2$, $36 = 6^2$, $100 = 10^2$, а $1$, $3$, $6$, $10$ — это $1$, $1 + 2$, $1 + 2 + 3$, $1 + 2 + 3 + 4$.

Идея: разрезать квадрат со стороной $\p1{1 + 2 + \dots + n}$ на куски площадью $1^3, 2^3, \dots, n^3$. Обозначим $T_k = 1 + 2 + \dots + k$ и разметим сторону квадрата отрезками $1, 2, \dots, n$ — вся сторона равна $T_n$, площадь квадрата $T_n^2$. Отметим из левого верхнего угла квадраты со сторонами $T_1, T_2, \dots, T_{n-1}$. Они режут большой квадрат на уголки: уголок номер $k$ — это квадрат $T_k \times T_k$ без квадрата $T_{k-1} \times T_{k-1}$. Его ширина $T_k - T_{k-1} = k$. Разрежем уголок номер $k$ на две полосы шириной $k$: вертикальную длиной $T_k$ и горизонтальную длиной $T_{k-1}$. Его площадь $k \cdot T_k + k \cdot T_{k-1} = k(T_k + T_{k-1})$. А $T_k + T_{k-1} = \frac{k(k+1)}{2} + \frac{(k-1)k}{2} = \frac{k \cdot 2k}{2} = k^2$ — две соседние лесенки Гаусса складываются в квадрат. Значит, площадь уголка $k \cdot k^2 = k^3$. Картинка показывает это и без выкладок: уголок номер $k$ складывается ровно из $k$ квадратов $k \times k$. При чётном $k$ один из них разрезан пополам, и половинки лежат на двух концах уголка. Весь квадрат состоит из уголков с номерами $1, 2, \dots, n$, поэтому $T_n^2 = 1^3 + 2^3 + \dots + n^3$ при любом $n$.

К той же формуле ведёт и числовая дорога. У Никомаха из Герасы (около 100 года нашей эры) есть наблюдение: кубы складываются из подряд идущих нечётных чисел, $1 = 1^3$, $3 + 5 = 2^3$, $7 + 9 + 11 = 3^3$, $13 + 15 + 17 + 19 = 4^3$. В $k$-й группе $k$ нечётных чисел стоят симметрично вокруг $k^2$, так что их сумма равна $k \cdot k^2$. Группы идут подряд, поэтому первые $n$ кубов — это первые $1 + 2 + \dots + n$ нечётных чисел, а их сумма равна квадрату их количества.

Тождество о сумме кубов часто называют теоремой Никомаха. Встречается оно и у индийского математика Ариабхаты в V веке, и у персидского математика ал-Караджи около 1000 года; рассуждение ал-Караджи историки считают одним из первых проблесков индукции.

Сломанная костяшка

Индукция надёжна, пока надёжны обе её части. Сломайте одну — и ряд устоит, как бы убедительно ни выглядело рассуждение. Вот знаменитый пример; его обычно связывают с именем венгерского математика Дьёрдя Пойа.

Вывод явно ложен, значит, ошибка есть. База верна. Шаг при $k = 2, 3, 4, \dots$ действительно верен. Но он должен работать и при $k = 1$, для перехода от одной лошади к двум. Тогда «все, кроме последней» — это первая лошадь, а «все, кроме первой» — вторая. Лошадей «посередине» нет, общей у двух групп нет, и связать их масти нечем. Одна костяшка стоит слишком далеко, и цепочка обрывается на первом же шаге.

На каком переходе ломается доказательство того, что все лошади одной масти?

От одной лошади к двум От двух лошадей к трём База неверна На каждом переходе понемногу

При $k = 1$ две группы по одной лошади не пересекаются. Все остальные шаги верны — но без перехода от одной лошади к двум они ничего не дают: цепочка обрывается сразу после первой костяшки.

Обратная поломка — шаг есть, а базы нет. Утверждение «$n = n + 1$» ложно при любом $n$, и всё же шаг для него доказывается честно: прибавим к обеим частям равенства $k = k + 1$ единицу и получим $k + 1 = k + 2$. Каждая костяшка уронила бы следующую, если бы хоть одна упала. Но первую толкнуть нечем.

Третья поломка самая частая: база проверена, и не один раз, а шага нет совсем. Выражение $n^2 + n + 41$ из главы 0 даёт простые числа при сорока значениях $n$ подряд — сорок костяшек, поставленных отдельно, без связи между ними. При $n = 40$ получается $40^2 + 40 + 41 = 41^2$, составное число.

Кролики Фибоначчи

В 1202 году Леонардо Пизанский, которого позже прозвали Фибоначчи, закончил «Книгу абака» — ту самую, что принесла в Европу индийские цифры (о ней мы рассказывали в главе о счёте). Среди сотен задач в ней есть одна про кроликов. Пара кроликов каждый месяц приносит новую пару, а новорождённая пара начинает приносить потомство через месяц. Кролики не умирают. Сколько пар будет через год, если вначале была одна взрослая пара?

Будем считать по месяцам. Вначале одна пара, через месяц две, ещё через месяц три: взрослая пара снова принесла потомство, а молодая только подросла. Дальше пять, восемь, тринадцать… Правило такое: пар в следующем месяце столько, сколько в этом, плюс новорождённые, а новорождённых столько, сколько было пар месяц назад, — все они уже взрослые. Получается ряд $1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377$, и ответ Фибоначчи — $377$ пар.

Пары через месяц. Пары сейчас: все они доживут до следующего месяца. Пары месяц назад: к следующему месяцу все они взрослые, и каждая принесёт новую пару. Пример: $F_{13} = F_{12} + F_{11} = 144 + 89 = 233$, $F_{14} = 233 + 144 = 377$ — кроличий ответ.

Своё имя последовательность получила в XIX веке от французского математика Эдуарда Люка. Числа Фибоначчи всплывают где угодно: они показывают, сколько шагов в худшем случае делает алгоритм Евклида, и прячутся на пологих диагоналях треугольника Паскаля.

Индукция для таких последовательностей устроена чуть иначе: каждая костяшка падает от удара двух предыдущих, поэтому толкать приходится две первые.

Растут они всё-таки быстро, почти как геометрическая прогрессия. Выложим квадраты со сторонами $1, 1, 2, 3, 5, 8, \dots$, каждый новый — вдоль длинной стороны уже собранного прямоугольника. Сторона нового квадрата равна сумме двух предыдущих, поэтому он всякий раз ложится точно, и снова получается прямоугольник, со сторонами $F_n$ и $F_{n+1}$.

Отношения соседних чисел Фибоначчи — $\frac11 = 1$, $\frac21 = 2$, $\frac32 = 1{,}5$, $\frac53 \approx 1{,}667$, $\frac85 = 1{,}6$, $\frac{13}{8} = 1{,}625$ — колеблются и сходятся к числу $1{,}618\dots$ Иоганн Кеплер заметил это ещё в 1611 году. Какое это число, можно выяснить, даже не доказывая, что отношения к чему-то сходятся.

Число $\varphi = \frac{1 + \sqrt5}{2} \approx 1{,}6180339887$ называют золотым сечением. Что оно иррационально и в некотором смысле «самое иррациональное» из всех чисел, рассказывает глава о корне из двух. Что предел отношений и правда существует, аккуратно доказывают с помощью пределов (глава 25). А точная формула для $F_n$, формула Бине, выражает его через степени $\varphi$ и второго корня того же уравнения; выводить её проще всего с помощью матриц, это сделано в главе о собственных векторах.

Найдите сумму первых десяти чисел Фибоначчи: $F_1 + F_2 + \dots + F_{10}$. Посчитайте сумму первых двух, трёх, четырёх чисел — и угадайте закономерность.

$1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 = 143$. Суммы первых чисел — $1, 2, 4, 7, 12, 20, \dots$ — на единицу меньше чисел Фибоначчи через одно: $F_1 + \dots + F_n = F_{n+2} - 1$, и действительно, $143 = F_{12} - 1 = 144 - 1$. Индукция: база $F_1 = 1 = F_3 - 1$; шаг — прибавим $F_{k+1}$ к $F_{k+2} - 1$ и получим $F_{k+3} - 1$.

Тренировка

В тренажёре три уровня. На первом — арифметические прогрессии: найти член, сумму, разность по двум членам. На втором — геометрические. На третьем задачи посложнее: бесконечные суммы, периодические дроби, число членов по сумме.

Свою задачу про прогрессию можно разобрать по шагам в решателе, а все тренажёры курса собраны на странице практики.

Куда дальше

Суммы в этой главе раз за разом оказывались многочленами от $n$: $1 + 2 + \dots + n = \frac{n^2 + n}{2}$, сумма кубов равна $\frac{n^4 + 2n^3 + n^2}{4}$, и у суммы квадратов $1^2 + 2^2 + \dots + n^2$ тоже есть такая формула — попробуйте угадать её и доказать индукцией. Главный вопрос о многочленах тот же, что о квадратном трёхчлене: где они обращаются в ноль. Вот многочлен третьей степени: $x^3 - 6x^2 + 11x - 6$. Подставьте $x = 1$, $2$ и $3$ — каждый раз получится ноль. А есть ли у него другие корни? Как их искать, если угадать не удалось, и есть ли для третьей степени формула, как для второй? Многое о корнях можно узнать без всякой формулы, если понимать, как устроены многочлены. Об этом глава о многочленах — и об итальянских математиках XVI века, решавших такие уравнения на публичных поединках.