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

16 апреля 2024
6 минут
2 021

Преподаватель математики и информатики. Кафедра бизнес-информатики Российского университета транспорта

Математическая индукция лежит в основе одного из самых распространенных методов математических доказательств. С его помощью можно доказать большую часть формул с натуральными числами $n$ , например, формулу нахождения суммы первых членов прогрессии $S_{n} = \frac{2 a_{1} + (n - 1) d}{2} \cdot n$ , формулу бинома Ньютона ${(a + b)}^{n} = C_{n}^{0} \cdot a^{n} \cdot C_{n}^{1} \cdot a^{n - 1} \cdot b + . . . + C_{n}^{n - 1} \cdot a \cdot b^{n - 1} + C_{n}^{n} \cdot b^{n}$ .

В первом пункте мы разберем основные понятия, потом рассмотрим основы самого метода, а затем расскажем, как с его помощью доказывать равенства и неравенства.

Понятия индукции и дедукции

Для начала рассмотрим, что такое вообще индукция и дедукция.

Определение 1

Индукция – это переход от частного к общему, а дедукция наоборот – от общего к частному.

Например, у нас есть утверждение: $254$ можно разделить на два нацело. Из него мы можем сделать множество выводов, среди которых будут как истинные, так и ложные. Например, утверждение, что все целые числа, которые имеют в конце цифру $4$ , могут делиться на два без остатка – истинное, а то, что любое число из трех знаков делится на $2$ – ложное.

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

Допустим, у нас есть последовательность чисел вида $\frac{1}{1 \cdot 2}, \frac{1}{2 \cdot 3}, \frac{1}{3 \cdot 4}, \frac{1}{4 \cdot 5}, . . ., \frac{1}{n (n + 1)}$ , где $n$ обозначает некоторое натуральное число. В таком случае при сложении первых элементов последовательности мы получим следующее:

$S_{1} = \frac{1}{1 \cdot 2} = \frac{1}{2}, S_{2} = \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} = \frac{2}{3}, S_{3} = \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \frac{1}{3 \cdot 4} = \frac{3}{4}, S_{4} = \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \frac{1}{3 \cdot 4} + \frac{1}{4 \cdot 5} = \frac{4}{5}, . . .$

Используя индукцию, можно сделать вывод, что $S_{n} = \frac{n}{n + 1}$ . В третьей части мы докажем эту формулу.

В чем заключается метод математической индукции

В основе этого метода лежит одноименный принцип. Он формулируется так:

Определение 2

Некое утверждение будет справедливым для натурального значения $n$ тогда, когда $1)$ оно будет верно при $n = 1$ и $2)$ из того, что это выражение справедливо для произвольного натурального $n = k$ , следует, что оно будет верно и при $n = k + 1$ .

Применение метода математической индукции осуществляется в $3$ этапа:

Для начала мы проверяем верность исходного утверждения в случае произвольного натурального значения $n$ (обычно проверка делается для единицы).
После этого мы проверяем верность при $n = k$ .
И далее доказываем справедливость утверждения в случае, если $n = k + 1$ .

Как применять метод математической индукции при решении неравенств и уравнений

Возьмем пример, о котором мы говорили ранее.

Пример 1

Докажите формулу $S_{n} = \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + . . . + \frac{1}{n (n + 1)} = \frac{n}{n + 1}$ .

Решение

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

Для начала проверяем, будет ли данное равенство справедливым при $n$ , равном единице. Получаем $S_{1} = \frac{1}{1 \cdot 2} = \frac{1}{1 + 1} = \frac{1}{2}$ . Здесь все верно.
Далее делаем предположение, что формула $S_{k} = \frac{k}{k + 1}$ верна.
В третьем шаге нам надо доказать, что $S_{k + 1} = \frac{k + 1}{(k + 1) + 1} = \frac{k + 1}{k + 2}$ , основываясь на справедливости предыдущего равенства.

Мы можем представить $k + 1$ в качестве суммы первых членов исходной последовательности и $k + 1$ :

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

Поскольку во втором действии мы получили, что $S_{k} = \frac{k}{k + 1}$ , то можно записать следующее:

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

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

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

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

Ответ: предположение о формуле $S_{n} = \frac{n}{n + 1}$ является верным.

Возьмем более сложную задачу с тригонометрическими функциями.

Пример 2

Приведите доказательство тождества $\cos 2 α \cdot \cos 4 α \cdot . . . \cdot \cos 2^{n} α = \frac{\sin 2^{n + 1} α}{2^{n} \sin 2 α}$ .

Решение

Как мы помним, первым шагом должна быть проверка верности равенства при $n$ , равном единице. Чтобы это выяснить, нам надо вспомнить основные тригонометрические формулы.

$\cos 2^{1} = \cos 2 α \frac{\sin 2^{1 + 1} α}{2^{1} \sin 2 α} = \frac{\sin 4 α}{2 \sin 2 α} = \frac{2 \sin 2 α \cdot \cos 2 α}{2 \sin 2 α} = \cos 2 α$

Следовательно, при $n$ , равном единице, тождество будет верным.

Теперь предположим, что его справедливость сохранится при $n = k$ , т.е. будет верно, что $\cos 2 α \cdot \cos 4 α \cdot . . . \cdot \cos 2^{k} α = \frac{\sin 2^{k + 1} α}{2^{k} \sin 2 α}$ .

Доказываем равенство $\cos 2 α \cdot \cos 4 α \cdot . . . \cdot \cos 2^{k + 1} α = \frac{\sin 2^{k + 2} α}{2^{k + 1} \sin 2 α}$ для случая, когда $n = k + 1$ , взяв за основу предыдущее предположение.

Согласно тригонометрической формуле,

$\sin 2^{k + 1} α \cdot \cos 2^{k + 1} α = = \frac{1}{2} (\sin (2^{k + 1} α + 2^{k + 1} α) + \sin (2^{k + 1} α - 2^{k + 1} α)) = = \frac{1}{2} (\sin (2 \cdot 2^{k + 1} α) + \sin 0) = \frac{1}{2} \sin 2^{k + 2} α$

Следовательно,

$\cos 2 α \cdot \cos 4 α \cdot . . . \cdot \cos 2^{k + 1} α = = (\cos 2 α \cdot \cos 4 α \cdot . . . \cdot \cos 2^{k} α) \cdot \cos 2^{k + 1} α = = \frac{\sin 2^{k + 1} α}{2^{k} \sin 2 α} \cdot \cos 2^{k + 1} α = \frac{1}{2} \cdot \frac{\sin 2^{k + 1} α}{2^{k} \sin 2 α} = \frac{\sin 2^{k + 2} α}{2^{k + 1} \sin 2 α}$

Ответ: На этом тождество можно считать доказанным. Мы успешно применили для этого метод математической индукции. Точно так же мы можем доказать справедливость формулы бинома Ньютона.

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