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

Метод математической индукции — это мощный инструмент, который используется для доказательства утверждений, касающихся всех натуральных чисел. Давайте разберем его на примере.

Формулировка утверждения.

Предположим, нам нужно доказать утверждение 𝑃(𝑛) для всех натуральных чисел 𝑛. Например, рассмотрим утверждение:

𝑃(𝑛):1+2+3+…+𝑛=𝑛(𝑛+1)/2

Это утверждение говорит, что сумма первых 𝑛 натуральных чисел равна 𝑛(𝑛+1)/2.

База индукции.

Сначала проверим, что утверждение верно для начального значения 𝑛, обычно 𝑛=1.

Для 𝑛=1:

1=1(1+1)/2

1=2/2

1=1

Утверждение верно для 𝑛=1.

Индукционное предположение.

Теперь предположим, что утверждение верно для некоторого натурального числа 𝑘. То есть, предположим, что:

1+2+3+…+𝑘=𝑘(𝑘+1)/2

Это называется индукционным предположением.

Индукционный шаг.

Нужно доказать, что если утверждение верно для 𝑛=𝑘, то оно верно и для 𝑛=𝑘+1. Рассмотрим сумму первых 𝑘+1 чисел:

1+2+3+…+𝑘+(𝑘+1)

По индукционному предположению, мы знаем, что:

1+2+3+…+𝑘=𝑘(𝑘+1)/2

Тогда:

1+2+3+…+𝑘+(𝑘+1)=𝑘(𝑘+1)/2+(𝑘+1)

Приведем к общему знаменателю:

𝑘(𝑘+1)/2+2(𝑘+1)/2=(𝑘(𝑘+1)+2(𝑘+1))/2

Вынесем (𝑘+1) за скобки:

(𝑘+1)(𝑘+2)/2

Таким образом, мы получили:

1+2+3+…+𝑘+(𝑘+1)=(𝑘+1)((𝑘+1)+1)/2

Это и есть утверждение для 𝑛=𝑘+1

Мы доказали, что если утверждение верно для 𝑛=𝑘, то оно верно и для 𝑛=𝑘+1. Поскольку мы уже проверили, что утверждение верно для 𝑛=1 (база индукции), по принципу математической индукции утверждение верно для всех натуральных чисел 𝑛. Таким образом, мы доказали, что:

1+2+3+…+𝑛=𝑛(𝑛+1)/2

для всех натуральных чисел 𝑛.

Метод математической индукции состоит из двух основных шагов:

1. База индукции. Проверка утверждения для начального значения (обычно 𝑛=1

).

2. Индукционный шаг. Доказательство того, что если утверждение верно для 𝑛=𝑘, то оно верно и для 𝑛=𝑘+1.

Если оба шага выполнены, то утверждение верно для всех натуральных чисел 𝑛.