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

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

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

Пусть имеется некое утверждение $P(n)$, зависящее от натурального числа $n$. Это утверждение будет справедливо для любого натурального числа n, если:

1. $P(n)$ справедливо для $n = 1$;
2. Из того, что это утверждение справедливо для произвольного натурального $n = k$, следует, что оно будет справедливо и при $n = k + 1$.

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

Алгоритм применения метода математической индукции:

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

Рассмотрим работу метода на примерах.

Доказать, что сумма кубов трёх последовательных натуральных чисел кратна 9.

Доказательство:

1. $n = 1;$

$1^{3} + 2^{3} + 3^{3} = 1 + 8 + 27 = 36$.

36 – кратно 9, значит утверждение справедливо при $n = 1.$

2. Предположим, что утверждение верно и для $n = k$, то есть:

$k^{3} + \left( k + 1 \right)^{3} + \left( k + 2 \right)^{3} = 9p$, $p\$– некое натуральное число.

3. Докажем, что утверждение справедливо для $n = k + 1$:

$\left( k + 1 \right)^{3} + \left( k + 2 \right)^{3} + \left( k + 3 \right)^{3} = \left( k + 1 \right)^{3} + \left( k + 2 \right)^{3} + k^{3} + 9k^{2} + 27k + 27$

$\left( k^{3} + \left( k + 1 \right)^{3} + \left( k + 2 \right)^{3} \right) + 9k^{2} + 27k + 27$

$\left( k^{3} + \left( k + 1 \right)^{3} + \left( k + 2 \right)^{3} \right) + 9\left( k + 27 \right) + 27$

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

Доказать, что справедливо неравенство $2^{n} \geq n^{2} + n + 2$ для любого натурального $n \geq 5$.

Доказательство:

1. $n = 5;$

$2^{5} \geq 5^{2} + 5 + 2$

$32 \geq 25 + 5 + 2$

$32 \geq 32$ - верно

2. Предположим, что утверждение верно и для $n = k \geq 5$, то есть:

$2^{k} \geq k^{2} + k + 2$

$2^{k} - k^{2} - k - 2 \geq 0$

3. Докажем, что утверждение справедливо для $n = k + 1$:

$2^{k + 1} \geq \left( k + 1 \right)^{2} + \left( k + 1 \right) + 2$

$2^{k} \cdot 2 - k^{2} - 2k - 1 - k - 3 \geq 0$

$\left( 2^{k} - k^{2} - k - 2 \right) + 2^{k} - 2k - 2 \geq 0$

$2^{k} - k^{2} - k - 2 \geq 0$по предположению из пункта 2. Значит, докажем, что $2^{k} - 2k - 2 \geq 0$ при $k \geq 5$. Для этого воспользуемся методом математической индукции еще раз.

4. $k = 5;$

$2^{5} - 2 \cdot 5 - 2 \geq 0$

$32 - 10 - 2 \geq 0$

$20 \geq 0$ - верно

5. Предположим, что утверждение верно и для $k = m$, то есть:

$2^{m} - 2 \cdot m - 2 \geq 0$

6. Докажем, что утверждение справедливо для $k = m + 1$:

$2^{m + 1} - 2 \cdot \left( m + 1 \right) - 2 \geq 0$

$2^{m} \cdot 2 - 2m - 2 - 2 \geq 0$

$2^{m} + \left( 2^{m} - 2m - 2 \right) - 2 \geq 0$

$2^{m} - 2m - 2 \geq 0$ из предположения в пункте 5.

$2^{m} - 2 \geq 0$, т.к. $m \geq 5$, а значит и $2^{m} + \left( 2^{m} - 2m - 2 \right) - 2 \geq 0$, что и требовалось доказать.