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

Теоретическая сводка

Пусть $P\left( n \right)$ есть некоторое утверждение, зависящее от натурального аргумента $n \in \mathbb{N}$ . Доказать, что $P\left( n \right)$ верно для любого натурального числа, можно при помощи метода математической индукции. Последний заключается в следующем.

Если $P\left( 1 \right)$ верно (база индукции), а из истинности $P\left( k \right)$ следует истинность $P\left( k+1 \right)$ (индукционный переход), т. е.

(1) $\begin{equation*} P\left( k \right) \implies P\left( k+1 \right) ,\end{equation*}$

то исходное утверждение $P\left( n \right)$ справедливо для любого натурального аргумента $\forall n \in \mathbb{N}$ .

Следует заметить, что метод математической индукции может быть сужен (расширен) и на другие множества аргументов. Так, например, в качестве базы индукции можно взять не единицу, а любое другое натуральное число $p$ . При таком выборе доказанное утверждение будет справедливо для $\forall n \ge p$ .

Задачи и упражнения

Уровни сложности задач

простая задача

средняя задача

сложная задача

олимпиадная задача

Скачать все решения в .pdf формате

Задача простая (1)

Доказать формулу нахождения суммы арифметической прогрессии

$\sum_{i=1}^{n} i = 1 + 2 + \ldots + n = \frac{n\left( n+1 \right) }{2} .$

Проверьте выполнение базы индукции. Далее запишите доказываемую формулу для $k + 1$ , а затем, заменив первые $k$ слагаемых формулы на $\frac{k\left( k+1 \right) }{2}$ и алгебраически преобразовав полученное равенство, совершите индукционный переход.

Для начала проверим выполнение базы индукции

$\sum_{i=1}^{1} i = 1 = \frac{1\left( 1+1 \right) }{2} .$

Пусть теперь наше утверждение справедливо для некоторого $k$ , т. е.

$\sum_{i=1}^{k} i = 1 + 2 + \ldots + k = \frac{k\left( k+1 \right) }{2} .$

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

$\begin{align*} & 1 + 2 + \ldots + \left( k + 1 \right) = \\ &= \underbrace{1 + 2 + \ldots + k}_{\frac{k\left( k+1 \right) }{2}} + \left( k + 1 \right) = \\ &= \frac{k\left( k+1 \right) }{2} + \left( k + 1 \right) = \\ &= \left( k+1 \right) \left( \frac{k}{2} +1 \right) = \\ &= \frac{\left( k+1 \right) \left( k+2 \right) }{2} .\end{align*}$

Формула доказана.

Скачать решение в .pdf формате

Я нашёл ошибку!

Задача простая (2)

Доказать формулу

$\sum_{i=1}^{n} i^2 = 1^2 + 2^2 + \ldots + n^2 = \frac{n\left( n+1 \right) \left( 2n + 1 \right) }{6} .$

Проверьте выполнение базы индукции. Далее запишите доказываемую формулу для $k + 1$ , а затем, заменив первые $k$ слагаемых формулы на $\frac{k\left( k+1 \right) \left( 2k + 1 \right)}{6}$ и алгебраически преобразовав полученное равенство, совершите индукционный переход.

Будем использовать в дальнейшем форму записи с использованием символа суммы $\sum$ . Проверим базу индукции

$\sum_{i=1}^{1} i^2 = 1 = \frac{1 \left( 1 + 1 \right) \left( 2+1 \right) }{6} .$

Пусть теперь выполняется

$\sum_{i=1}^{k} i^2 = \frac{k\left( k+1 \right) \left( 2k + 1 \right) }{6} .$

Тогда нетрудно совершить индукционный переход

$\sum_{i = 1}^{k+1} i^2 = \sum_{i=1}^{k} i^2 + \left( k+1 \right) ^2 = \frac{k\left( k+1 \right) \left( 2k+1 \right) }{6} + \left( k+1 \right) ^2=$

$= \frac{\left( k+1 \right) }{6}\left[ k\left( 2k +1 \right) + 6\left( k+1 \right) \right] = \frac{\left( k+1 \right) \left( k+2 \right) \left( 2\left( k+1 \right) +1 \right) }{6} .$

Скачать решение в .pdf формате

Я нашёл ошибку!

Задача средняя (3)

Доказать неравенство Бернулли

$\left( 1 + x_1 \right) \left( 1 +x_2 \right) \ldots \left( 1 + x_n \right) \ge 1 + x_1 + x_2 + \ldots + x_n$

$\left( \prod_{i=1}^{n}\left( 1+x_i \right) \ge 1 + \sum_{i=1}^{n} x_i \right) ,$

где $x_i > -1$ , при чём все $x_i$ — одного знака.

Для совершения индукционного перехода необходимо домножить неравенство при $n=k$ на $\left( 1 + x_{k+1} \right)$ , а далее оценить правую часть неравенства снизу.

Выполнение базы индукции очевидно в силу тождества $1 + x_1 = 1 + x_1$ .

Пусть теперь выполняется неравенство для $n = k$

$\prod_{i=1}^{k}\left( 1+x_i \right) \ge 1 + \sum_{i=1}^{k} x_i .$

Домножим это неравенство на положительную (в силу усиловия $x_i > -1$ ) величину $1+x_{k+1}$

$\prod_{i=1}^{k+1}\left( 1+x_i \right) \ge \left(1 + \sum_{i=1}^{k} x_i\right) \left( 1 + x_{k+1} \right) .$

Оценим выражение в правой неравенства части снизу

$\begin{align*} &\left(1 + \sum_{i=1}^{k} x_i\right) \left( 1 + x_{k+1} \right) = \\ &= 1 + x_{k+1} + \sum_{i=1}^{k} x_i + x_{k+1}\left( \sum_{i=1}^{k} x_i \right) =\\ &= 1 + \sum_{i=1}^{k+1} x_i + \underbrace{x_{k+1}\left( \sum_{i=1}^{k} x_i \right)}_{>0} \ge 1 + \sum_{i=1}^{k+1} x_i .\end{align*}$

Произведение $x_{k+1}$ на сумму $\sum_{i=1}^{k} x_i$ положительна в силу того, что все $x_i$ по условию имеют один знак. Итак, совмещая два неравенства, окончательно совершаем индукционный переход