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

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

Пусть имеется некое утверждение \(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\), что и требовалось доказать.