Под методом математической индукции понимают следующий способ доказательства: если требуется доказать истинность утверждения $latex P(n), \forall n \in \mathbb{N},$ то сначала проверяют данное утверждение для некоторого натурально числа $latex n_0 $, обычно $latex n_0=1$, а потом допускают истинность выражения $latex P(k).$ Далее доказывают истинность утверждения $latex P(k+1).$
Упражнение:
Доказательство одноцветности всех лошадей — ошибочное доказательство, что все лошади одного цвета, придуманное венгерским математиком Пойа. Доказательство призвано продемонстрировать ошибки, возникающие при неправильном использовании метода математической индукции.
Доказываемое утверждение: все лошади одного цвета.
Доказательство:
Проведем доказательство по индукции.
База индукции:
Одна лошадь, очевидно, одного (одинакового) цвета.
Шаг индукции:
Пусть доказано, что любые $latex K $ лошадей всегда одного цвета. Рассмотрим $latex K+1 $ каких-то лошадей. Уберем одну лошадь. Оставшиеся $latex K $ лошадей одного цвета по предположению индукции. Возвратим убранную лошадь и уберем какую-то другую. Оставшиеся $latex K $ лошадей снова будут одного цвета. Значит, все $latex K+1 $ лошадей одного цвета.
Отсюда следует, что все лошади одного цвета. Утверждение доказано.
В чем ошибка?
Решение
Опровержение
Противоречие возникает из-за того, что шаг индукции не сообразуется с базой. Он верен лишь при $latex K \geq 2 $. При $latex K = 1 $ (база индукции) получаемые множества оставшихся лошадей не будут пересекаться, и утверждение о равенстве цветов всех лошадей сделать нельзя.
Пример:
$latex 1)$ Доказать равенство: $latex 1^{2}+2^{2}+3^{2}+\cdots+n^{2}=\frac{n(n+1)(2n+1)}{6}, n\in \mathbb{N}.$
$latex \square$ $latex 1)$ $latex 1^{2}=\frac{1(1+1)(2+1)}{6}=1.$
$latex 2)$ Пусть данное утверждение верно для $latex n=k:$ $latex 1^{2}+\cdots+k^{2}=\frac{k(k+1)(2k+1)}{6}.$
$latex 3)$ Докажем истинность утверждения для $latex n=k+1.$
$latex \overbrace{1^{2}+2^{2}+\cdots+k^{2}}^{\frac{k(k+1)(2k+1)}{6}}+(k+1)^{2}= $
$latex \frac{(k+1)(k+2)(2(k+1)+1)}{6} $
$latex \frac{k(k+1)(2k+1)}{6}+(k+1)^{2}= $
$latex \frac{(k+1)(k+2)(2k+3)}{6} $
$latex \frac{k(k+1)(2k+1)+6(k+1)^{2}}{6}= $
$latex \frac{(k+1)(k+2)(2k+3)}{6} $
$latex k(2k^{2}+k+2k+1)+6(k^{2}+2k+1)= $
$latex (k+1)(2k^{2}+3k+4k+6) $
$latex 2k^{3}+3k^{2}+k+6k^{2}+12k+6= $
$latex 2k^{3}+7k^{2}+6k+2k^{2}+7k+6 $
$latex 2k^{3}+9k^{2}+13k+6= $
$latex 2k^{3}+9k^{2}+13k+6.$ $latex \blacksquare$
$latex 2)$ Доказать, что для всех натуральных чисел $latex n$ справедливо неравенство $latex n \leq 2^{n}$.
$latex \square$ Для $latex n=1$ неравенство принимает вид $latex 1 \leq 2$, т.е. оно справедливо.
Предположим, требуемое неравенство имеет место при некотором $latex n=k$ и покажем, что оно же справедливо и для $latex n=k+1$.
Сложим предположение индукции $latex k \leq 2^{k}$ с неравенством $latex 1 \leq 2 \leq 2^{k}$. Находим $latex k+1 \leq 2^{k}+2^{k}=2^{k+1}$, что и требовалось доказать. $latex \blacksquare$
Тест "Метод математической индукции"
Тестовые вопросы по вышеизложенному материалу.
Таблица лучших: Тест "Метод математической индукции"
Место | Имя | Записано | Баллы | Результат |
---|---|---|---|---|
Таблица загружается |
Список литературы:
- Лысенко З.М. Конспект лекций по курсу математического анализа.
- В.И.Коляда, А.А.Кореновский «Курс лекций по мат.анализу, часть 1» (Одесса «Астропринт» , 2009г.), стр.4.