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

Под методом математической индукции понимают следующий способ доказательства: если требуется доказать истинность утверждения $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$

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

Тестовые вопросы по вышеизложенному материалу.

Таблица лучших: Тест "Метод математической индукции"

максимум из 3 баллов
Место Имя Записано Баллы Результат
Таблица загружается
Нет данных

Список литературы:

  • Лысенко З.М. Конспект лекций по курсу математического анализа.
  • В.И.Коляда, А.А.Кореновский «Курс лекций по мат.анализу, часть 1» (Одесса «Астропринт» , 2009г.), стр.4.

 

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *