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

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

Пусть 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)

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

    \[ \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 по условию имеют один знак. Итак, совмещая два неравенства, окончательно совершаем индукционный переход

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

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

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

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

Доказать равенство

    \[ 1 + 2 + 2^2 + \ldots + 2^{n-1} = \sum_{i=0}^{n-1} 2^{i} = 2^{n}- 1 \]

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

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

    \[ \sum_{i=0}^{0} 2^{i} = 1 = 2^{1}-1 .\]

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

    \[ 1 + 2 + 2^2 + \ldots + 2^{k-1} = \sum_{i=0}^{k-1} 2^{i} = 2^{k}- 1 \]

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

    \begin{align*} & \underbrace{1 + 2 + 2^2+ \ldots + 2^{k-1}}_{2^{k}-1}+ 2^{k}= \\ &= 2 \cdot 2^{k} -1 = 2^{k+1}-1 .\end{align*}

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

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

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

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

Доказать равенство

    \[ 1^{3}+ 2^{3}+\ldots+n^{3} = \left( 1 + 2 + \ldots + n \right) ^2 ,\]

    \[ \left( \sum_{i=1}^{n} i^{3} = \left( \sum_{i=1}^{i} i \right)^2 \right) .\]

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

    \[ 1 + 2 + \ldots + n = \frac{n + 1}{2} \cdot n .\]

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

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

    \[ 1^{3}+ 2^{3}+\ldots+k^{3} = \left( 1 + 2 + \ldots + k \right) ^2 .\]

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

    \begin{align*} & \underbrace{1^{3} + 2^{3} + \ldots + k^{3}}_{\left( 1 + 2 + \ldots + k \right) ^{2}}+ \left( k+1 \right) ^{3}= \\ &= \left( 1 + 2 + \ldots + k \right) ^2 + \left( k+1 \right)^{3}= \\ &= \left( \frac{1 + k}{2}\cdot k \right)^2 + \left( k+1 \right)^{3}= \\ &= \left( k+1 \right)^2 \cdot \left( \frac{k^2}{4} + k + 1 \right)= \\ &= \left( k+1 \right) ^2 \cdot \left( \frac{k}{2} +1 \right)^2 = \\ &= \left[ \frac{\left( k+1 \right) + 1}{2} \cdot \left( k+1 \right) \right] ^2 = \\ &= \left( 1 + 2 + \ldots + k + \left( k+1 \right) \right)^2 .\end{align*}

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

    \[ 1 + 2 + \ldots + n = \frac{n + 1}{2} \cdot n .\]

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

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

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

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

    \[ \sum_{i=0}^{n-1} b_1\cdot q^{i} = b_1 + b_1 \cdot q^{1} + b_1 \cdot q^{2} + \ldots + b_1 \cdot q^{n-1} = b_1 \frac{q^{n}-1}{q - 1} .\]

Проверьте выполнение базы индукции. Далее запишите доказываемую формулу для k + 1, а затем, заменив первые k слагаемых формулы на b_1 \frac{q^{n}-1}{q-1} и алгебраически преобразовав полученное равенство, совершите индукционный переход.

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

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

    \[ b_1 + b_1 \cdot q^{1} + b_1 \cdot q^{2} + \ldots + b_1 \cdot q^{k-1} = b_1 \frac{q^{k}-1}{q - 1} .\]

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

    \begin{align*} & \underbrace{b_1 + b_1 \cdot q^{1} + b_1 \cdot q^{2} + \ldots + b_1 \cdot q^{k-1}}_{b_1 \frac{q^{k}-1}{q-1}} + b_1 \cdot q^{k} = \\ &= b_1 \cdot \left( \frac{q^{k}-1}{q-1} + q^{k} \right) = b_1 \cdot \frac{q^{k}-1 + q^{k+1}-q^{k}}{q-1}= \\ &= b_1 \frac{q^{k+1}-1}{q-1} .\end{align*}

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

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

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

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

Доказать неравенство

    \[ \frac{1}{2}\cdot \frac{3}{4} \cdot \ldots\cdot \frac{2n-1}{2n} < \frac{1}{\sqrt{2n + 1} } \]

    \[ \left( \prod_{i=1}^{n} \frac{2i-1}{2i} < \frac{1}{\sqrt{2n +1} }\right) .\]

Проверьте выполнение базы индукции и совершите индукционный переход, оценив сверху левую часть доказываемого неравенства при n = k+1.

Выполнение базы индукции очевидно в силу \frac{1}{2} < \frac{1}{\sqrt{3}}.

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

    \[ \frac{1}{2}\cdot \frac{3}{4} \cdot \ldots\cdot \frac{2k-1}{2k} < \frac{1}{\sqrt{2k + 1} } .\]

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

    \begin{align*} & \underbrace{\frac{1}{2}\cdot \frac{3}{4} \cdot \ldots\cdot \frac{2k-1}{2k}}_{ < \frac{1}{\sqrt{2k + 1}}} \cdot \frac{2k+1}{2k + 2} < \\ &< \frac{1}{\sqrt{2k+1} } \cdot \frac{2k+1}{2k+2} = \frac{\sqrt{2k + 1} }{2k+2} <\\ &< \frac{\sqrt{2k +1} }{2k+1} = \frac{1}{\sqrt{2k +1}} .\end{align*}

Неравенство доказано.

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

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

Введите запрос и нажмите enter для поиска

Прокрутить вверх