Знакомство с методом математической индукции

Авторы исходного текста: Т. Шульман и А. В. Ворожцов

Что такое принцип математической индукции?

Вообразим очередь, где первой стоит женщина, за ней снова женщина, а за ней снова женщина. Верно ли, что все стоящие в очереди — женщины?

Конечно, верно! Раз первые три человека в очереди — женщины, то, скорее всего, это очередь за косметикой, или за чем-нибудь таким, в чём нуждаются и разбираются исключительно женщины, и мужчин в этой очереди нет.

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

Рассмотрим два утверждения:

1. Первый человек в очереди есть женщина
2. За женщиной в очереди может стоять только женщина

Из этих двух утверждений строго следует, что в очереди стоят только женщины. Мы можем последовательными шагами показать что любой человек в очереди — женщина.

Вот строгая формулировка принципа математической индукции:

Пусть имеется последовательность утверждений $Y_{1},Y_{2},Y_{3}\ldots \,\!$ И пусть первое утверждение $Y_{1}\,\!$ верно и мы умеем доказать, что из верности утверждения $Y_{k}\,\!$ следует верность $Y_{k+1}\,\!$. Тогда все утверждения в этой последовательности верны.

Решим одну известную задачу на ММИ:

Ханойские башни.

Есть три стержня и $n\,\!$ колец разного размера. Класть можно только кольцо меньшего размера на кольцо большего размера. Можно ли переместить пирамидку с одного стрежня на другой?

• Пирамидку, в которой только одно кольцо ($n=1\,\!$) переместить можно (очевидно).
• Предположим, что мы умеем перемещать пирамидки с числом колец $n\leq K\,\!$.
• Попробуем научиться перемещать пирамидку с $n=K+1\,\!$. Пирамидку из $K\,\!$ колец, лежащих на самом большом $(K+1)\,\!$-м кольце, мы можем согласно предположению переместить на любой другой стержень. Сделаем это. Неподвижное $(K+1)\,\!$-е кольцо не будет нам мешать провести алгоритм перемещения, так как оно самое большое. После перемещения $K\,\!$ колец переместим это самое большое $(K+1)\,\!$-е кольцо на оставшийся стержень. И затем опять применим известный нам по предположению алгоритм перемещения $K\,\!$ колец и переместим их на стержень с лежащим внизу $(K+1)\,\!$-м кольцом. Таким образом, если мы умеем перемещать пирамидки с $K\,\!$ кольцами, то умеем перемещать пирамидки и с $(K+1)\,\!$ кольцом.
• Следовательно утверждение верно для всех случаев,то есть для всех $n\,\!$.

Заметим, что всё решение было разбито на 4 этапа:

1. [БАЗА] Показываем, что доказываемое утверждение верно для некоторых простейших частных случаев ( в нашей задачке это был случай $n=1\,\!$)
2. [ПРЕДПОЛОЖЕНИЕ] Предполагаем, что утверждение доказано для первых $K\,\!$ случаев.
3. [ШАГ] В этом предположении доказываем утверждение для случая $n=K+1\,\!$.
4. [ВЫВОД] Утверждение верно для всех случаев, то есть для всех $n\,\!$.

Решение задач по данной схеме и называется методом математической индукции.

Ясно, что ММИ можно решать не все задачи, а только задачи, параметризованные некоторой переменной. Эта переменная называется переменной индукции.

В задаче «Ханойские башни» роль переменной индукции играло количество колец в пирамидке.

Пересечение прямых

Докажите, что любые $n\,\!$ прямых, никакие две из которых не параллельны, и никакие три не пересекаются в одной точке, пересекаются ровно в ${\frac {n(n-1)}{2}}\,\!$ точках.

Решение:

[БАЗА] В простейшем случае, когда прямых две, точка пересечения одна и утверждение верно.

[ПРЕДПОЛОЖЕНИЕ] Предположим, что оно верно для $k\,\!$ прямых, то есть что любые $k\,\!$ прямых, никакие две из которых не параллельны, и никакие три не пересекаются в одной точке, пересекаются ровно в ${\frac {k(k-1)}{2}}\,\!$ точках.

[ШАГ] Попробуем доказать его для $k+1\,\!$ прямой. По предположению, $1\,\!$-я, $2\,\!$-я, ..., $k\,\!$-я прямая пересекаются в ${\frac {k(k-1)}{2}}\,\!$ точках. $(k+1)\,\!$-я прямая пересекается с каждой из этих $k\,\!$ прямых ровно в одной точке. Следовательно количество точек пересечения всех $k+1\,\!$ прямых есть ${\frac {k(k-1)}{2}}+k={\frac {k^{2}+k}{2}}={\frac {(k+1)k}{2}}\,\!$.
То есть для $k+1\,\!$ прямых утверждение доказано.

[ВЫВОД] Утверждение верно для любого количества прямых.

Разрезание квадрата

Из квадрата клетчатой бумаги размером $2^{n}\times 2^{n}\,\!$ вырезали одну клетку. Докажите, что полученную фигуру можно разрезать на «уголки» из трех клеток

Решение:

[БАЗА]: для квадрата размера $2\times 2\,\!$ утверждение верно.

[ПРЕДПОЛОЖЕНИЕ]: Пусть это уже доказано для квадратов со стороной $2\,\!$, $4\,\!$, $8,\ldots ,2^{k}\,\!$. Докажем для квадратов $2^{k+1}\times 2^{k+1}\,\!$.

[ШАГ]: Разбиваем квадрат $2^{k+1}\times 2^{k+1}\,\!$ на четыре квадрата $2^{k}\times 2^{k}\,\!$ и вырезаем из каждой недырявой части угловую клетку так, чтобы вырезанные клетки образовали уголок:

[ВЫВОД]: Таким образом, получаем четыре квадрата, в каждом из которых вырезано по одной клетке, и по предположению индукции их мы можем замостить уголками.

Попробуйте решить самостоятельно следующие геометрические задачи:

Геометрические задачи на ММИ

Три острых угла

1. Докажите, что при каждом натуральном $n\,\!$, начиная с $3\,\!$,

существует выпуклый $n\,\!$-угольник, имеющий ровно три острых угла.

^{Подсказка}

Раскраска плоскости

1. Плоскость разделена на части $n\,\!$

прямыми. Докажите, что эти части можно раскрасить в два цвета так, что соседние куски будут раскрашены в разные цвета.

^{Подсказка}

Сумма углов $n\,\!$-угольника.

Докажите что сумма углов выпуклого $n\,\!$-угольника равна $(n-2)\cdot 180^{\circ }\,\!$, (или $(n-2)\pi \,\!$ радиан). В частности для треугольника получаем $(3-2)\cdot 180^{\circ }=180^{\circ }\,\!$, а для четырехугольника — $(4-2)\cdot 180^{\circ }=360^{\circ }\,\!$

Число кусочков

Чему равно количество кусочков, на которые прямые из задачи ^[1] делят плоскость? Одна прямая — на две части, две — на четыре. А пятнадцать прямых?

^{Подсказка}

Применение ММИ для решения задач на делимость

Задача про кубы

Докажите, что сумма кубов трех последовательных натуральных чисел делится на $9\,\!$.

Решение: Поскольку $1^{3}+2^{3}+3^{3}=36\,\!$ делится на $9\,\!$, то для $n=1\,\!$ утверждение верно. Предположим, что оно верно для $n=k\,\!$, то есть $k^{3}+(k+1)^{3}+(k+2)^{3}=9m\,\!$ для некоторого натурального числа $m\,\!$. Нам нужно доказать для $n=k+1\,\!$. Но действительно $(k+1)^{3}+(k+2)^{3}+(k+3)^{3}=(k+1)^{3}+(k+2)^{3}+k^{3}+27k+9k^{2}+27=9(m+3k+k^{2}+3)\,\!$ делится на $9\,\!$, и мы заключаем, что утверждение верно для любого $n\,\!$.

Задача про делимость (3²ⁿ⁺² + 8 n - 9) и (4ⁿ + 15 n - 1)

Докажите, что а) $3^{2n+2}+8n-9\,\!$ делится на $16\,\!$; б) $4^{n}+15n-1\,\!$ делится на $9\,\!$.

Применение ММИ для доказательства тождеств

Есть целый ряд тождеств, которые удобно доказывать ММИ, к примеру:

а) $1^{2}+2^{2}+3^{2}+\dots +n^{2}={\frac {n(n+1/2)(n+1)}{3}}\,\!$;

б) $1^{3}+2^{3}+3^{3}+\dots +n^{3}={\frac {n^{2}(n+1)^{2}}{4}}\,\!$;

в) $1\cdot 2+2\cdot 3+3\cdot 4+\dots +n\cdot (n+1)={\frac {n(n+1)(n+2)}{3}}.\,\!$

Докажем а). При $n=0\,\!$ с обоих сторон стоит $0\,\!$. Проверим, работает ли эта формула при $n=1\,\!$: $n=1:\;\;1^{2}={\frac {1(1+1/2)(1+1)}{3}}=1,\,\!$ Это верно и дает БАЗУ индукции. Рассмотрим функцию $B(n)={\frac {n(n+1/2)(n+1)}{3}}.\,\!$ ПРЕДПОЛОЖИМ, что она дает верный ответ при $n<k\,\!$. ШАГ индукции будет соответствовать проверке равенства $B(k+1)-B(k)=(k+1)^{2}.\,\!$ Раскрываем левую часть: ${\frac {(k+1)(k+3/2)(k+2)-(k)(k+1/2)(k+1)}{3}}=\,\!$ $={\frac {(k+1)((k+3/2)(k+2)-(k+1/2)k)}{3}}=\,\!$ $={\frac {(k+1)((3/2)k+2k+3-(1/2)k)}{3}}={\frac {3(k+1)^{2}}{3}}=(k+1)^{2}.\,\!$

Докажите самостоятельно б) и в).

Доказывать такие тождества просто. Трудно догадаться до того, что должно стоять справа от знака <<равно>>.

Как догадаться, чему равно $1^{2}+2^{2}+3^{2}+\dots +n^{2}=B(n)\,\!$? Например, так: можно вычислить четыре значения $B(1)=1\,\!$, $B(2)=5\,\!$, $B(3)=13\,\!$, $B(4)=29\,\!$, а затем попытаться подобрать такой многочлен третьей степени, который в точках 1, 2, 3, 4 принимает именно эти значения. А потом можно ММИ убедиться, что $B(k+1)-B(k)=k^{2}\,\!$.

Почему именно многочлен третьей степени? Потому что если бы $B(k)\,\!$ был многочленом степени большей или равной $4\,\!$, то разница $B(k+1)-B(k)\,\!$ была бы многочленом степени большей или равной $3\,\!$ (докажите это утверждение опять же ММИ), то есть не могла бы быть равной $k^{2}\,\!$.

Почему предлагается вычислить именно четыре значения $B(1)=1\,\!$, $B(2)=5\,\!$, $B(3)=13\,\!$, $B(4)=29\,\!$? Потому что многочлен третьей степени полностью определяется своими значениями в четырех разных точках. Действительно, он задается коэффициентами $a\,\!$, $b\,\!$, $c\,\!$, $d\,\!$ при $1\,\!$, $x\,\!$, $x^{2}\,\!$, $x^{3}\,\!$: $a+bx+cx^{2}+dx^{3}.\,\!$ Значит, для того, чтобы их найти все коэффициенты, нужно $4\,\!$ уравнения.

1. Докажите тождество $1\cdot 2\cdot 3+2\cdot 3\cdot 4+3\cdot 4\cdot 5+\dots +n\cdot (n+1)\cdot (n+2)={\frac {n(n+1)(n+2)(n+3)}{4}}.\,\!$
2. Докажите тождество $1+x+x^{2}+\ldots +x^{n}={\frac {x^{n+1}-1}{x-1}}\,\!$.
3. Найдите сумму ${1 \over 1\cdot 2}+{1 \over 2\cdot 3}+{1 \over 3\cdot 4}+\dots \,\!$
4. Угадайте явное выражение для суммы ${1 \over 1\cdot 2}+{1 \over 2\cdot 3}+{1 \over 3\cdot 4}+\dots +{1 \over (n-1)n}\,\!$.
5. Докажите, что $1\cdot 2+2\cdot 2^{2}+3\cdot 2^{3}+\ldots +n\cdot 2^{n}=(n-1)\cdot 2^{n+1}+2\,\!$.
6. Найдите сумму $1{1 \over 2}+2{1 \over 2^{2}}+3{1 \over 2^{3}}+\dots \,\!$ .

Иногда ММИ надо применять не совсем прямолинейно.

Неравенство Коши (неравенство между средним арифметическим и средним геометрическим)

Доказать, что ${\frac {x_{1}+x_{2}+\ldots +x_{n}}{n}}\geq {\sqrt[{n}]{x_{1}x_{2}\ldots x_{n}}}\,\!$ для любых неотрицательных чисел $x_{1},x_{2},\ldots ,x_{n}\,\!$.

Решение: Сначала методом мат. индукции докажем это равенство для всех $n\,\!$, равных степени двойки. БАЗА: нужно показать, что ${\frac {x_{1}+x_{2}}{2}}\geq {\sqrt {x_{1}x_{2}}}\,\!$. Действительно, ${\frac {x_{1}+x_{2}}{2}}-{\sqrt {x_{1}x_{2}}}={\frac {x_{1}+x_{2}-2{\sqrt {x_{1}x_{2}}}}{2}}={\frac {({\sqrt {x_{1}}}-{\sqrt {x_{2}}})^{2}}{2}}\geq 0\,\!$. ПРЕДПОЛОЖИМ, что мы умеем доказывать неравенство при $n=2^{k}\,\!$. Докажем его для $n=2^{k+1}\,\!$. Итак, у нас есть $2^{k+1}\,\!$ чисел $x_{1},x_{2},\ldots ,x_{2^{k+1}}\,\!$. Обозначим ${\frac {x_{1}+x_{2}}{2}}=y_{1}\,\!$, ${\frac {x_{3}+x_{4}}{2}}=y_{2},\ldots \,\!$ ${\frac {x_{2^{k+1}-1}+x_{2^{k+1}}}{2}}=y_{2^{k}}\,\!$. Поскольку чисел $y_{1},y_{2},\ldots ,y_{2^{k}}\,\!$ всего $2^{k}\,\!$, то по предположению, ${\frac {y_{1}+y_{2}+\ldots +y_{2^{k}}}{2^{k}}}\geq {\sqrt[{2^{k}}]{y_{1}y_{2}\ldots y_{n}}}\,\!$. Следовательно, ${\frac {x_{1}+x_{2}+\ldots +x_{2^{k+1}}}{2^{k+1}}}={\frac {y_{1}+y_{2}+\ldots +y_{2^{k}}}{2^{k}}}\geq {\sqrt[{2^{k}}]{y_{1}y_{2}\ldots y_{2^{k}}}}=\,\!$ ${\sqrt[{2^{k}}]{({\frac {x_{1}+x_{2}}{2}})({\frac {x_{3}+x_{4}}{2}})\ldots ({\frac {x_{2^{k+1}-1}+x_{2^{k+1}}}{2}})}}\geq \,\!$ $\geq {\sqrt[{2^{k}}]{{\sqrt {x_{1}x_{2}}}{\sqrt {x_{3}x_{4}}}\ldots {\sqrt {x_{2^{k+1}-1}x_{2^{k+1}}}}}}=\,\!$ ${\sqrt[{2^{k+1}}]{x_{1}x_{2}\ldots x_{2^{k+1}}}}.\,\!$

Итак, неравенство доказано для случаев, когда $n\,\!$ есть степень двойки. Теперь индукцией вниз распространяем на остальные~$n\,\!$. Это относительно сложный момент в доказательстве. Предположим, что неравенство Коши доказано для $n=k\,\!$. Необходимо доказать, что оно верно и для $n=k-1\,\!$. Это можно сделать так. Пусть у нас есть $(k-1)\,\!$ чисел $x_{1}\,\!$, \ldots, $x_{k-1}\,\!$. Добавим к ним $x_{k}={\frac {x_{1}+x_{2}+\ldots +x_{k-1}}{k-1}},\,\!$ — $k\,\!$-ое число, равное их среднему арифметическому. Для этих $k\,\!$ чисел неравенство Коши по предположению верно и мы можем его использовать: ${\frac {x_{1}+x_{2}+\ldots +x_{k-1}}{k-1}}={\frac {x_{1}+x_{2}+\ldots +x_{k-1}+{\frac {x_{1}+x_{2}+\ldots +x_{k-1}}{k-1}}}{k}}\geq \,\!$ $\geq {\sqrt[{k}]{x_{1}x_{2}\ldots x_{k-1}{\frac {x_{1}+x_{2}+\ldots +x_{k-1}}{k-1}}}}.\,\!$ Домножим левую и правую части на $({\frac {x_{1}+x_{2}+\ldots +x_{k-1}}{k-1}})^{-1/k},\,\!$ получим: $({\frac {x_{1}+x_{2}+\ldots +x_{k-1}}{k-1}})^{1-1/k}\geq {\sqrt[{k}]{x_{1}x_{2}\ldots x_{k-1}}}.\,\!$ Возведя обе части в степень $k/{k-1}\,\!$, получаем ${\frac {x_{1}+x_{2}+\ldots +x_{k-1}}{k-1}}\geq {\sqrt[{k-1}]{x_{1}x_{2}\ldots x_{k-1}}},\,\!$ что и требовалось доказать.

Ясно, что теперь неравенство доказано для любого $n\,\!$: выбираем любое $k\,\!$, такое, что $2^{k}\geq n\,\!$. Для $2^{k}\,\!$ неравенство доказано. Значит оно верно, как мы только что показали, и для $2^{k}-1\,\!$, а раз верно для $2^{k}-1\,\!$, то верно и для $2^{k}-2\,\!$, и т.д., пока не доберемся до $n\,\!$.

А теперь проверим, действительно ли вы понимаете метод математической индукции.

Найдите ошибку в доказательстве

Утверждение 1: У всех людей глаза одинакового цвета.

Доказательство. Докажем, что в компании из $n\,\!$ людей у всех глаза одинакового цвета. При $n=1\,\!$ утверждение очевидно. Предположим, что оно верно при $n=k\,\!$. Докажем, что тогда оно верно и для $n=k+1\,\!$. Итак, пусть перед нами $k+1\,\!$ человек. Перенумеруем их: первый, второй, третий, ..., $k\,\!$-й, $(k+1)\,\!$-й. По предположению, у любых $k\,\!$ из этих людей глаза одинакового цвета. Значит, у первого, второго, ..., $k\,\!$-го — глаза одинакового цвета. Возьмём теперь другую группу из $k\,\!$ человек: второй, третий, ..., $k\,\!$-й, $(k+1)\,\!$-й. У них тоже глаза одинакового цвета. В обоих группах присутствовал второй человек. Значит у всех них глаза того же цвета, как и у второго, то есть у всех одинаковые.

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

Утверждение 2: Через любые $n\,\!$ точек на плоскости можно провести прямую.

Доказательство. При $n=1\,\!$ и $n=2\,\!$ теорема справедлива (в силу известной аксиомы геометрии). Остается доказать теорему для $n\,\!$, больших, чем $2\,\!$.

Допустим, что теорема справедлива при некотором $n=k\,\!$, и покажем, что в этом случае она будет сохранять силу и при $n=k+1\,\!$.

Итак, пусть произвольно заданы $(k+1)\,\!$ точек $M_{1}\,\!$, $M_{2}\,\!$, \ldots, $M_{k}\,\!$, $M_{k+1}\,\!$. В силу предположения индукции через $k\,\!$ точек $M_{1}\,\!$, $M_{2}\,\!$, \ldots, $M_{k}\,\!$ проходит некоторая прямая $l\,\!$. В силу того же предположения через $k\,\!$ точек $M_{2}\,\!$, \ldots, $M_{k}\,\!$, $M_{k+1}\,\!$ также проходит некоторая прямая $l'\,\!$. Эти две прямые имеют по крайней мере две общие точки $M_{2}\,\!$ и $M_{k}\,\!$. Но две точки определяют единственную прямую. Поэтому прямые $l\,\!$ и $l'\,\!$ должны совпадать. Следовательно, прямая $l\,\!$, проходящая через точки $M_{1}\,\!$, $M_{2}\,\!$, \ldots, $M_{k}\,\!$, проходит и через точку $M_{k+1}\,\!$. Утверждение доказано.

Подсказки даны в разделе «Подсказки и ответы», но для начала попытаетесь найти ошибку сами.

Задачи

1. На доске записано рациональное число $q={\frac {m}{n}}\,\!$. Его можно стереть и записать вместо него либо $q+1={\frac {m+n}{n}}\,\!$, либо ${\frac {1}{q}}={\frac {n}{m}}\,\!$. Докажите, что с помощью указанных двух операций можно из единицы получить любое рациональное число. Например, число ${\frac {2}{5}}\,\!$ можно получить так: $1\to 2\to {\frac {1}{2}}\to {\frac {3}{2}}\to {\frac {5}{2}}\to {\frac {2}{5}}.\,\!$
2. В прямоугольнике $3\times n\,\!$ ($3\,\!$ строки, $n\,\!$ столбцов) расставлены фишки трех цветов по $n\,\!$ штук каждого цвета. Докажите, что, переставляя фишки в строчках, можно сделать так, чтобы в каждом столбце были фишки всех трех цветов.
3. Плоскость поделена на области несколькими прямыми и окружностями.Докажите, что эти области можно раскрасить в два цвета так, чтобы любые две соседние области были раскрашены в различные цвета. Соседними считаются области, границы которых имеют общий отрезок.
4. В компании из $n\,\!$ человек ($n>3\,\!$) каждый узнал по одному новому анекдоту (все анекдоты разные).За один телефонный разговор двое сообщают друг другу все известные им анекдоты. Докажите, что за $2n-4\,\!$ звонков все смогут узнать все новые анекдоты.
5. На координатной плоскости расположено $n\,\!$ квадратов одинакового размера так, что их стороны параллельны осям координат. Доказать,что все квадраты можно разбить на $3\,\!$ группы так, что в каждой группе квадраты не будут пересекаться.

Подсказки и ответы

Подсказки к геометрическим задачам

1. ^  Шаг: Пусть есть такой K-угольник. Возьмем один из его тупых углов и отрежем его. Число вершин станет K+1. Новые два угла, появившиеся вместо старого, будут еще тупее, так как они — внешние углы отрезанного треугольника.
2. ^  При проведении следующей прямой инвертируйте одну из полуплоскостей.
3. ^ Е сли прямых $n\,\!$ штук, то число кусочков равно $n(n+1)/2+1\,\!$.

Где ошибка в доказательстве утверждения 1?

Делая переход от $n=k\,\!$ к $n=k+1\,\!$ мы предполагали, что множества $\{1,\;\ldots ,\;k\}\,\!$ и $\{2,\;\ldots ,\;k+1\}\,\!$ пересекаются, так как оба содержат $2\,\!$-й элемент. Но это значит, что $k\geq 2\,\!$. Следовательно, базой индукции должн был быть случай $n=2\,\!$, а не $n=1\,\!$, как в нашем доказательстве.

Где ошибка в доказательстве утверждения 2?

Аналогично: мы предполагали, что прямые $l\,\!$ и $l'\,\!$ имеют по крайней мере две общие точки $M_{2}\,\!$ и $M_{k}\,\!$, значит $k\geq 3\,\!$. Следовательно, базой индукции должны были быть случаи $n=1\,\!$, $n=2\,\!$ и $n=3\,\!$. Но база для $n=3\,\!$ не верна.