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

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

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

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

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

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

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

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

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

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

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

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

Заметим, что аксиому индукции можно заменить на аксиому существования минимума, и доказать аксиому индукции как теорему.

Также в скобках заметим, что существует принцип полной математической индукции. Вот его строгая формулировка:

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

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

Принцип полной математической индукции также может быть доказан при помощи математической индукции. Верно и обратное: принцип математической индукции можно доказать, предполагая принцип полной математической индукции. Так что в аксиомах Пеано можно выбрать в качестве одной из аксиом как аксиому существования минимума, как принцип полной математической индукции, так и принцип математической индукции. Какое из этих трёх утверждений брать за теорему, а какую за аксиомы — дело вкуса. Доказательство эквивалентности этих утверждений смотри в приложении B

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

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

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

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

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$-ю прямую и одну из прямых, обозначем её $i$ из списка $1$-я, $2$-я, …, $k$-я прямая. Как мы уже доказали в [БАЗЕ] любые две прямые, удовлетворящие условиям задачи, пресекаются ровно в одной точке, а значит и прямые $k+1$ и $i$ пересекаются в одной точке. Вспомним, что $i$ обозначает любую прямую из списка $1$-я, $2$-я, …, $k$. Отсюда $k+1$-я прямая пересекается с каждой из этих $k$ прямых ровно в одной точке.

Рассмотрим список из $k+1$ прямых и их точек пересечения. Уберём прямую $k+1$ вместе с её точками пересечения. Останется $k$ прямых удовлетворяющих [ШАГУ]. Значит количество точек пересечения у этих $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}$ вырезали одну клетку. Докажите, что полученную фигуру можно разрезать на «уголки» из трёх клеток.

Решение:

[БАЗА] Для $n=1$ получим квадрат размером $2\times 2$. Вырежем, скажем, правый верхний квадрат. Останется три квадрата, представляющие из себя «уголки». Утверждение верно.

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

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

[ВЫВОД] Таким образом, получаем четыре квадрата, в каждом из которых вырезано по одной клетке, и по предположению индукции их мы можем замостить уголками. Замощение квадрата $2^{k+1}\times 2^{k+1}$ будет состоять из замощения четырёх квадратов $2^{k}\times 2^{k}$ c вырезанной одной клеткой по середине. Что и требовалось доказать.

Интуиция

Возможно, вы, прочитав решение, скажете себе, что вы всё поняли, но сами бы такую задачу решить не смогли. На вопрос «почему?» вы скажите: что-то, непонято почему нужно было делить квадрат $2^{k+1}\times 2^{k+1}$ на четыре части.

В большинстве учебников вопросу интуиции в решении задач не уделяется внимание вообще. Даётся просто формально правильное решение. Отчасти это объясняется экономией места, отчасти тем, что это не являются частью решения, отчасти тем, что у каждого своя интуиция и не сильно понятно что именно нужно описывать, отчасти тем, что достаточно просто перерешать большое количество задач, как у вас появится интуиция. Не споря с этими утверждениями, я всё же решил, что в некоторых относительно трудных случаях я буду писать пару слов о том, почему нужно сделать то или иное действие. В подсказках к решению задач вы часто также будете находить то действие или тот факт, которое нужно было найти «интуитивно», как здесь деление квадрата на четыре части.

В этом примере интуиция могла бы быть такой. Возьмём квадрат $2^{k+1}\times 2^{k+1}$. Нам нужно применить к нему метод математической индукции, а значит нам надо «найти» в нём квадрат $2^{k}\times 2^{k}$. Допустим, это будет центр большего квадрата. Меньший квадрат без одной клетки мы можем вымостить «угольником». Но что сделать с оставшимися $2^{k+1}\times 2^{k+1}-2^{k}\times 2^{k}=2^{2k+2}-2^{2k}=2^{2k}(2^{2}-1)=3\cdot 2^{2k}$ квадратиками (плюс вырезанный квадратик из меньшего квадрата). Но постойте, $3\cdot 2^{2k}$ — это количество клеток в ещё трёх квадратах! Мы взяли один квадрат, а из оставшихся клеток можно сделать ещё три одинаковых квадрата! Нужно только подумать о том, чтобы эти клетки располагались в форме квадрата (у нас они располагаются «полосами»), а также о том, чтобы «вырезанные» клетки каждого меньшего квадрата не были разбросаны как попало.

Упражнение. Допустим, сторона квадрата будет $3^{n}\times 3^{n}$. Попытайтесь «интуитивно» понять, почему застелить его «уголками» не получится. Пройдитесь по доказательству в случае квадрата $2^{n}\times 2^{n}$ и найдите место, где доказательство «падает». Постройте контр-пример.

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

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

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

Задача 1.1. Докажите, что при каждом натуральном $n$, начиная с $3$, существует выпуклый $n$-угольник, имеющий ровно три острых угла.

Подсказка .

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

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

Подсказка .

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

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

Подсказка .

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

Задача 1.4. Чему равно количество кусочков, на которые $n$ прямых (не проходящих через одну точку) делят плоскость на части? Одна прямая — на две части, две — на четыре. А пятнадцать прямых?

Подсказка

Доказательства тождеств

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

Пример 2.1. Если $x\geqslant 0$, $c\geqslant 0$, то

$(x+c)^{n}=x^{n}+O(x^{n-1})$, где $O(x^{n-1})$ обозначает полином степени не большей чем $n-1$.

Разъяснение

существует точная формула, которая называется бином Ньютона, которая будет доказана ниже

Приведём несколько примеров для разъяснения смысла знака $O(x^{n-1})$. Воспульзуемся формулами сокращённого умножения.

$(x+c)^{1}=x+c=x+O(x^{1-1})=x+O(x^{0})$, где $O(x^{0})$ обозначает «полином степени не большей чем $0$», то есть $O(x^{0})$ обозначает скаляр (число). В данном случае $O(x^{0})=c$, так как $c$ — число, не зависимое от $x$.

$(x+c)^{2}=x^{2}+2xc+c^{2}=x^{2}+((2c)x+c^{2}x^{0})=x^{2}+O(x^{1})$

$(x+c)^{3}=x^{3}+3x^{2}c+3xc^{2}+c^{3}=x^{3}+(3cx^{2}+3c^{2}x+c^{3}+x^{0})=x^{3}+O(x^{2})$

Докажем три тождества, которые мы тут же используем в доказательстве ниже.

$a\cdot O(x^{k})=O(x^{k})$. (1)

В самом деле, слева у нас «полином степени не большей чем $k$», умноженный на скаляр (число) $a$. Мы можем перемножить все его коэффициенты на $a$, от этого степень полинома не изменится, он останется «полиномом степени не большей чем $k$», а это и есть выражение справа.

$x\cdot O(x^{k-1})=O(x^{k})$. (2)

В самом деле, если умножим $x$ на «полином степени не большей чем $k-1$», то есть у такого полинома существует ненулевой коэффициент при $x^{k-1}$ и для всех $s\geqslant k$ степени при $x^{s}$ равны нулю, то у нас будет ненулевой коэффициент при $x\cdot x^{k-1}=x^{k}$, и для всех $s\geqslant k$ степени при $x\cdot x^{s}=x^{s+1}$ равны нулю, то есть слева у нас будет полином с коэффициентами при степенях $s\geqslant (k+1)$ $x^{s}$ равными нулю, и при $x^{k}$ будет ненулевой коэффициент, то есть это будет равняться «полиному степени не большей чем $k$» в правой части.

$O(x^{k})+O(x^{k-1})+cx^{k}=O(x^{k})$. (3)

В самом деле, слева мы имеем сложение «полинома степени не большей чем $k$» с «полиномом степени не большей чем $k-1$» с (конкретным) «полиномом степени не большей чем $k$». По свойству полиномов мы получим «полином степени не большей чем $k$», что и является полиномом в правой части.

Доказательство

БАЗА. $n=1$. Нужно доказать, что $(x+c)^{1}=x^{1}+O(x^{1-1})$, то есть что $(x+c)=x+O(x^{0})$. Возьмём в качестве $O(x^{0})$ число $C$. Тождество доказано.

ПРЕДПОЛОЖИМ, что тождество верно при $n=k$, то есть

$(x+c)^{k}=x^{k}+O(x^{k-1})$.

ШАГ индукции будет соответствовать проверке этого тождества при $n=k+1$, то есть нужно доказать, что

$(x+c)^{k+1}=x^{k+1}+O(x^{k})$.

В самом деле, применяя последовательно ММИ, тождества (2) и (3), получаем

$(x+c)^{k+1}=(x+c)(x+c)^{k}=(x+c)(x^{k}+O(x^{k-1})=x^{k+1}+x\cdot O(x^{k-1})+cx^{k}+c\cdot O(x^{k-1})=$.

$x^{k+1}+O(x^{k})+O(x^{k-1})+cx^{k}=x^{k+1}+O(x^{k})$

[ВЫВОД] Тождество верно для любого $n$.

Другой пример.

Пример 2.2. $1^{2}+2^{2}+3^{2}+\dots +n^{2}={\frac {n(n+{\frac {1}{2}})(n+1)}{3}}$.

Доказательство. Проверим, работает ли эта формула при $n=1$:

$1^{2}={\frac {1(1+{\frac {1}{2}})(1+1)}{3}}=1,$.

Это верно и даёт БАЗУ индукции.

ПРЕДПОЛОЖИМ, что тождество верно при $n=k$, то есть

$1^{2}+2^{2}+3^{2}+\dots +k^{2}={\frac {k(k+{\frac {1}{2}})(k+1)}{3}}$

ШАГ индукции будет соответствовать проверке этого тождества при $n=k+1$, то есть нужно доказать, что

$1^{2}+2^{2}+3^{2}+\dots +k^{2}+(k+1)^{2}={\frac {(k+1)(k+{\frac {3}{2}})(k+2)}{3}}$.

$1^{2}+2^{2}+3^{2}+\dots +k^{2}+(k+1)^{2}=(1^{2}+2^{2}+3^{2}+\dots +k^{2})+(k+1)^{2}=$

$={\frac {k(k+{\frac {1}{2}})(k+1)}{3}}+(k+1)^{2}={\frac {k(k+{\frac {1}{2}})(k+1)+3(k+1)^{2}}{3}}={\frac {(k+1)\left(k(k+{\frac {1}{2}})+3(k+1)\right)}{3}}=$

$={\frac {(k+1)\left(k(k+{\frac {1}{2}}+1-1)+3(k+1+1-1)\right)}{3}}={\frac {(k+1)\left(k(k+{\frac {3}{2}})+3(k+2)-k-3)\right)}{3}}=$

$={\frac {(k+1)\left(k(k+{\frac {3}{2}})+2k+3\right)}{3}}={\frac {(k+1)\left(k(k+{\frac {3}{2}})+2(k+{\frac {3}{2}})\right)}{3}}={\frac {(k+1)(k+{\frac {3}{2}})(k+2)}{3}}$

[ВЫВОД] Тождество верно для любого $n$.

Задача 2.1. $1^{3}+2^{3}+3^{3}+\dots +n^{3}={\frac {n^{2}(n+1)^{2}}{4}}$.

Задача 2.2. $1\cdot 2+2\cdot 3+3\cdot 4+\dots +n\cdot (n+1)={\frac {n(n+1)(n+2)}{3}}$.

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

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

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

Почему именно многочлен третьей степени? Степень многочлена не может быть меньше трёх. Предположим, от противного, что степень многочлена $B(n)$ меньше трёх. Тогда степень многочлена $B(k+1)$ меньше трёх и степень многочлена $B(k)$ меньше трёх. Но $B(k+1)=B(k)+(k+1)^{2}$. Степень многочлена слева меньше трёх. Степень многочлена справа меньше или равняется максимуму степени многочлена $B(n)$ и степени многочлена $(k+1)^{2}$, то есть максимальному числу, строго меньше трёх и двух, то есть два. Имеем справа многочлен второй степени, слева многочлен третьей степени. Противоречие.

С другой стороны, она не может быть больше трёх. Допустим от противного, что степень многочлена $B(n)$ больше или равняется $4$. В таком случае $B(k+1)-B(k)=(k+1)^{2}$, то есть $B(k+1)-B(k)$ является многочленом второй степени.

Докажем, по индукции, что степень многочлена $B(k+1)-B(k)$ больше или равняется трём (а значит, не равняется двум — это и будет нашим противоречием), при допущении, что степень многочлена $B(n)$ больше или равняется $4$.

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

БАЗА. Нужно доказать, что для $k=1$, если степень многочлена $B(1)$ больше или равняется $4$, то степень многочлена $B(2)-B(1)$ больше или равняется $3$. Это утверждение является верным, так как предположение (если…) не выполняется, степень многочлена $B(1)$ не больше или равняется $4$ (оно равняется 1, так как после подстановки скаляра (числа) в полином он превращается в скаляр (число)). А если предположение неверно, то импликация верна.

ПРЕДПОЛОЖЕНИЕ. Если степень многочлена $B(k)$ больше или равняется $4$, то степень многочлена $B(k+1)-B(k)$ больше или равняется $3$.

ШАГ. Нужно доказать, если степень многочлена $B(k+1)$ больше или равняется $4$, то степень многочлена $B(k+2)-B(k+1)$ больше или равняется $3$.

ИНТУИЦИЯ. Нам надо оценить степень многочлена $B(k+2)-B(k+1)$, зная про степень многочлена $B(k+1)-B(k)$. Легко заметить, что у них есть общее слагаемое $B(k+1)$, правда, с разным знаком. Так, давайте привнесём руками недостающее для применения ММИ слагаемое $B(k)$ (а знак нам не помеха, вынесем его за скобки, так как он не влияет на степень многочлена).

Этот «трюк» по «добавлению нуля» (наряду с «умножением на единицу») — довольно часто встречающиеся трюк при доказательствах.

$B(k+2)-B(k+1)=B(k+2)-B(k+1)+B(k)-B(k)=-{\Big (}-B(k+2)+(B(k+1)-B(k))+B(k){\Big )}$. (*)

По условию, степень многочлена $-B(k+2)$ и степень многочлена $B(k)$ больше или равняется $4$. Согласно ММИ степень многочлена $B(k+1)-B(k)$ больше или равняется $3$. Возьмём такое $s$, что коэффициент при $x^{s}$ в многочлене $B(k+1)-B(k)$, обозначим его за $bk^{s}$, будет не равен нулю. Так как степень многочлена $B(k+1)-B(k)$ больше или равнятеся $3$, то существует такое $s\geqslant 3$, что коэффициент при $k^{s}$ $b\neq 0$.

Давайте посмотрим на коэффициенты при $k^{s}$ во всём выражении (*) (как было сказано в идее доказательства, этот коэффициент должен быть не равен нулю). Обозначим коэффициент при $k^{s}$ в $B(k)$ за $ak^{s}$. Тогда коэффициент при $k^{s}$ в $-B(k+2)$ будет $-a(k+2)^{s}$. Как было сказано выше, $b\neq 0$.

Получим коэффициент при $k^{s}$. В (*) он равняется $-(-a(k+2)^{s}+bk^{3}+ak^{3})$. Применим тождество из примера 2.1 (а мы можем это сделать, так как $2\geqslant 0$ и $k\geqslant 0$), получим

$-(-a(k+2)^{s}+bk^{s}+ak^{s})=a{\Big (}k^{s}+O(k^{s-1}){\Big )}-bk^{s}-ak^{s}=ak^{s}+a\cdot O(k^{s-1})-bk^{s}-ak^{s}=-bk^{s}+a\cdot O(k^{s-1})$.

Применим тождество (1), получим

$-bk^{s}+O(k^{s-1})$, где, как было сказано выше, $b\neq 0$. То есть в выражении (*) будет присутствовать ненулевой коэффициент при $k^{s}$. Вспомним, что $s\geqslant 3$, получим, что полином (*) как минимум является полиномом третьей степени.

[ВЫВОД] Тождество верно для всех $n$.

Почему предлагается вычислить именно четыре значения $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}.$. Значит, для того, чтобы найти все коэффициенты, нужно четыре уравнения.

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. а) Угадайте явное выражение для суммы ${\frac {1}{1\cdot 2}}+{\frac {1}{2\cdot 3}}+{\frac {1}{3\cdot 4}}+\dots +{\frac {1}{(n-1)n}}$.

Подсказка .

б) докажите его при помощи ММИ.

3. Докажите, что $1\cdot 2+2\cdot 2^{2}+3\cdot 2^{3}+\ldots +n\cdot 2^{n}=(n-1)\cdot 2^{n+1}+2$.

4. Докажите, что $1+q+\cdot s+q^{n}={\frac {1-q^{n+1}}{1-q}}$.

Подсказка

.

5. Найдите сумму $1\cdot {\frac {1}{2}}+2\cdot {\frac {1}{2^{2}}}+3\cdot {\frac {1}{2^{3}}}+\dots +n\cdot {\frac {1}{2^{n}}}$.

Подсказка .

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

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

Доказать, что

${\frac {x_{1}+x_{2}+\ldots +x_{n}}{n}}\geqslant {\sqrt[{n}]{x_{1}x_{2}\ldots x_{n}}}$

для любых неотрицательных чисел $x_{1},x_{2},\ldots ,x_{n}$.

ИНТУИЦИЯ. Нам надо будет, в ШАГЕ, связать каким-то образом ${\frac {x_{1}+x_{2}+\ldots +x_{n+1}}{n+1}}$ с ${\frac {x_{1}+x_{2}+\ldots +x_{n}}{n}}$. Заметим, что если у нас есть среднее арифметическое $n$ чисел и если к ним добавить $n+1$ число, равное среднему арифметическому, то среднее арифметическое $n+1$ таких чисел будет равно среднему арифметическому $n$ чисел. Например, если у нас есть числа $3$ и $5$, то если к ним добавить их среднее арифметическое, число $4$, то среднее арифметическое $3$,$4$,$5$ останется $4$.

${\frac {x_{1}+x_{2}+\ldots +x_{k-1}+{\frac {x_{1}+x_{2}+\ldots +x_{k-1}}{k-1}}}{k}}={\frac {(k-1)x_{1}+(k-1)x_{2}+\ldots +(k-1)x_{k-1}+x_{1}+x_{2}+\ldots +x_{k-1}}{(k-1)k}}=$

$={\frac {kx_{1}+kx_{2}+\ldots +kx_{k-1}}{(k-1)k}}={\frac {x_{1}+x_{2}+\ldots +x_{k-1}}{k-1}}$.

Однако, каким образом мы может добавить число, которое нам вздумается? Ведь мы должны доказать ПЕРЕХОД для любых $k+1$ чисел. Значит нам нужно сначала как-то «сократить» количество с $k+1$. Для этого полезно следующие наблюдение. Мы можем сгруппировать числа парами, и тогда количество чисел уменьшиться и мы сможем добавить нужные нам числа.

Однако делать это нужно аккуратно. Так, если у нас есть нечётное количество чисел, то у нас останется «лишнее» число. Заметим, что добавлением нуля проблему не решишь, например,

${\frac {x_{1}+x_{2}+x_{3}}{3}}={\frac {(x_{1}+x_{2})+(x_{3}+0)}{3}}$,

и, несмотря на то, что у нас есть две пары, то есть с числителем дроби всё вроде бы в порядке, у нас проблема со знаменателем, нам нужно, чтобы в знаменателе было $2$, а не $3$. Попытка

${\frac {2}{3}}\cdot {\frac {(x_{1}+x_{2})+(x_{3}+0)}{2}}={\frac {2}{3}}{\sqrt[{2}]{(x_{1}+x_{2})(x_{3}+0)}}$

ни к чему не приводит, получили и корень не той степени, и неправильное подкоренное выражение, и коэффициент ${\frac {2}{3}}$, с которым вообще непонятно, что делать. Значит, нужно искать другой путь. А что, если в числитель «поднять» из знаменателя $3$?

$2\cdot {\frac {\frac {(x_{1}+x_{2})+(x_{3}+0)}{3}}{2}}=2\cdot {\frac {{\frac {(x_{1}+x_{2})}{3}}+{\frac {(x_{3}+0)}{3}}}{2}}=2{\sqrt[{2}]{{\frac {(x_{1}+x_{2})}{3}}{\frac {(x_{3}+0)}{3}}}}$.

Получили ${\frac {x_{1}+x_{2}+x_{3}}{3}}=2{\sqrt[{2}]{{\frac {(x_{1}+x_{2})}{3}}{\frac {(x_{3}+0)}{3}}}}$.

Если бы в подкорневом выражении вместо умножения на $x_{3}$ было бы сложение, то мы бы имели бы одно и то же выражение в разной степени (отвлекаясь от двойки) и могли бы дальше что-то делать. А так…

Давайте посмотрим на этот путь при чётных $n$. Но и этого недостаточно, например, для $n=6$ мы будем иметь

${\frac {x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}}{6}}={\frac {(x_{1}+x_{2})+(x_{3}+x_{4})+(x_{5}+x_{6})}{6}}$

Чтобы могли применить ММИ, нужно чтобы в знаменателе было $x_{3}$ (так как $x_{3}$ пары), но $6=2\cdot 3$, поэтому получим

${\frac {{\frac {(x_{1}+x_{2})}{2}}+{\frac {(x_{3}+x_{4})}{2}}+{\frac {(x_{5}+x_{6})}{2}}}{3}}$.

Однако для $n=3$ невозможно применить индукцию, так как $3$ — число нечётное.

Попутно можно заметить, что никакие числа у нас теперь «не торчат». Если бы мы могли применить ММИ, то получили бы выражение ${\sqrt[{3}]{{\frac {(x_{1}+x_{2})}{2}}{\frac {(x_{3}+x_{4})}{2}}{\frac {(x_{5}+x_{6})}{2}}}}$. И тут мы можем применить снова неравенство Коши для $n=1$ и получить ${\sqrt[{3}]{{\sqrt[{2}]{(x_{1}\cdot x_{2})}}{\sqrt[{2}]{(x_{3}\cdot x_{4})}}{\sqrt[{2}]{(x_{5}\cdot x_{6})}}}}={\sqrt[{6}]{x_{1}\cdot x_{2}\cdot x_{3}\cdot x_{4}\cdot x_{5}\cdot x_{6}}}$, и утверждение доказано. Вполне возможно, что мы натолкнулись на плодотворную идею. Для чётного $n=2s$ мы можем разбить числитель на $s$ разных пар и «поднять» из знаменателя $2$, то есть если наши пары будут выглядеть как ${\frac {(x_{i}+x_{i+1})}{2}}$. Однако, число в знаменателе должно подходить к применению ММИ.

Значит $n$ должно быть чётным, и при том «настолько» чётным, чтобы мы могли применить к нему индукцию (чтобы ${\frac {n}{2}}$ было тоже чётным). Может быть достаточно взять $n=4s$? Попробуем:

для $n=12$ мы будем иметь

${\frac {x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}+x_{7}+x_{8}+x_{9}+x_{10}+x_{11}+x_{12}}{12}}=$

$={\frac {{\frac {x_{1}+x_{2}}{2}}{\frac {x_{3}+x_{4}}{2}}{\frac {x_{5}+x_{6}}{2}}{\frac {x_{7}+x_{8}}{2}}{\frac {x_{9}+x_{1}0}{2}}{\frac {x_{1}1+x_{1}2}{2}}}{6}}$.

И для применения ММИ $6$ должно делиться на $4$. Если устранить это препятствие, то всё получится:

${\sqrt[{3}]{{\frac {x_{1}+x_{2}}{2}}{\frac {x_{3}+x_{4}}{2}}{\frac {x_{5}+x_{6}}{2}}{\frac {x_{7}+x_{8}}{2}}{\frac {x_{9}+x_{10}}{2}}{\frac {x_{11}+x_{12}}{2}}}}=$

$={\sqrt[{3}]{{\sqrt[{2}]{x_{1}\cdot x_{2}}}{\sqrt[{2}]{x_{3}\cdot x_{4}}}{\sqrt[{2}]{x_{5}\cdot x_{6}}}{\sqrt[{2}]{x_{7}\cdot x_{8}}}{\sqrt[{2}]{x_{9}\cdot x_{10}}}{\sqrt[{2}]{x_{11}\cdot x_{12}}}}}=$

$={\sqrt[{6}]{x_{1}\cdot x_{2}\cdot x_{3}\cdot x_{4}\cdot x_{5}\cdot x_{6}\cdot x_{7}\cdot x_{8}\cdot x_{9}\cdot x_{10}\cdot x_{11}\cdot x_{12}}}$)

Значит, нам нужно выбрать «настолько чётное $n$» (делиться на $8$?), что половина его также будет «настолько чётным». Как мы уже убедились кратность двум или четырём недостаточно. А что, если $n$ будет состоять из степеней двойки, то есть существует такое $s$, что $n=2^{s}$? В таком случае половина $n$ также будет состоять из степеней двойки, так как ${\frac {n}{2}}={\frac {2^{s}}{2}}=2^{s-1}$. Вроде как должно сработать. Это довольно общее замечание, если вы хотите доказать что-то для чётных $n$, то сначала вы должны доказать это для степени двойки, $n=2^{s}$.

Итак, опишем схему доказательства.

1. Сначала, докажем тождество для степени двойки $n=2^{s}$ для $y_{1}={\frac {x_{1}+x_{2}}{2}},\ y_{2}={\frac {x_{3}+x_{4}}{2}},\ \ldots ,\ y_{2^{s}}={\frac {x_{2^{s+1}-1}+x_{2^{s+1}}}{2}}$. Идею доказательства смотри выше.
2. Доказав для чисел вида $2^{s}$, нужно распространить доказательства для всех чисел. Выберем любое $k$ такое, что $2^{k}\geqslant n$. Для $2^{k}$ неравенство доказано. Значит, мы должны доказать тождество и для $2^{k}-1$ (тогда оно будет верно и для $2^{k}-2$, и так далее, пока не доберёмся до $n$).
3. Затем, предположив, что тождество верно для $n=k$, нужно доказать его для $n=k-1$. Идея доказательства состоит в добавлении $k$-го элемента, равного среднему арифметическому.

Решение

Сначала ММИ докажем это равенство для всех $n$, равных степени двойки.

БАЗА: нужно показать, что ${\frac {x_{1}+x_{2}}{2}}\geqslant {\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}}\geqslant 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}}}\geqslant {\sqrt[{2^{k}}]{y_{1}y_{2}\ldots y_{2^{k}}}}$. Следовательно,

${\frac {x_{1}+x_{2}+\ldots +x_{2^{k+1}}}{2^{k+1}}}={\frac {y_{1}+y_{2}+\ldots +y_{2^{k}}}{2^{k}}}\geqslant$

$\geqslant {\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}})}}\geqslant$

$\geqslant {\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}}\geqslant$

$\geqslant {\sqrt[{k}]{x_{1}x_{2}\ldots x_{k-1}{\frac {x_{1}+x_{2}+\ldots +x_{k-1}}{k-1}}}}$.

Домножим левую и правую части на $\left({\frac {x_{1}+x_{2}+\ldots +x_{k-1}}{k-1}}\right)^{-1/k},$ получим

$\left({\frac {x_{1}+x_{2}+\ldots +x_{k-1}}{k-1}}\right)^{1-1/k}\geqslant {\sqrt[{k}]{x_{1}x_{2}\ldots x_{k-1}}}$.

Возведя обе части в степень ${\frac {k}{k-1}}$, получаем

${\frac {x_{1}+x_{2}+\ldots +x_{k-1}}{k-1}}\geqslant {\sqrt[{k-1}]{x_{1}x_{2}\ldots x_{k-1}}}$,

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

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

Формула бинома Ньютона

Формула бинома Ньютона является обобщением формул сокращенного умножения

$(a+b)^{n}=C_{n}^{0}*a^{n}b^{0}+C_{n}^{1}*a^{n-1}*b^{1}+C_{n}^{2}*a^{n-2}*b^{2}+\ldots +C_{n}^{n}*a^{0}*b^{n}$

$C_{n}^{m}$ — число сочетаний из n по m

$C_{n}^{m}={{n!} \over m!(n-m)!}$

n! - n факториал

--89.232.230.186 14:30, 5 сентября 2008 (UTC) первокурсник ЮГУ

Задачи на делимость

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

Докажите, что сумма кубов трёх последовательных натуральных чисел делится на $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=$

$=9m+27k+9k^{2}+27=9(m+3k+k^{2}+3)$

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

Задача про делимость $3^{2n+2}+8n-9$ и $4^{n}+15n-1$

Докажите, что

а) $3^{2n+2}+8n-9$ делится на $16$.

Подсказка .

б) $4^{n}+15n-1$ делится на $9$.

Подсказка .

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

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

Утверждение 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$ квадратов одинакового размера так, что их стороны параллельны осям координат. Доказать, что все квадраты можно разбить на три группы так, что в каждой группе квадраты не будут пересекаться.

Приложение A

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

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

Следовательно, базой индукции должн был быть случай $n=2$, а не $n=1$, как в нашем доказательстве.

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

Аналогично: мы предполагали, что прямые $l$ и $l'$ имеют по крайней мере две общие точки $M_{2}$ и $M_{k}$, значит $k\geqslant 3$.

Следовательно, базой индукции должны были быть случаи $n=1$, $n=2$ и $n=3$. Но база для $n=3$ не верна.

Приложение B

Здесь будет написано доказательство эквивалентности принципа математической индукции, принципа полной математической индукции и аксиомы существования минимума.

• "Индукция как она есть!"