Главная
Новости
Строительство
Ремонт
Дизайн и интерьер




20.06.2021


19.06.2021


18.06.2021


17.06.2021


17.06.2021





Яндекс.Метрика

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

04.03.2021

Математическая индукция — метод математического доказательства, который используется, чтобы доказать истинность некоторого утверждения для всех натуральных чисел. Для этого сначала проверяется истинность утверждения с номером 1 {displaystyle 1} — база (базис) индукции, а затем доказывается, что если верно утверждение с номером n {displaystyle n} , то верно и следующее утверждение с номером n + 1 {displaystyle n+1} — шаг индукции, или индукционный переход.

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

Формулировка

Предположим, что требуется установить справедливость бесконечной последовательности утверждений, занумерованных натуральными числами: P 1 , P 2 , … , P n , P n + 1 , … {displaystyle P_{1},P_{2},ldots ,P_{n},P_{n+1},ldots } .

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

Принцип полной математической индукции

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

В этой вариации база индукции оказывается излишней, поскольку является тривиальным частным случаем индукционного перехода. Действительно, при n = 1 {displaystyle n=1} импликация ( ∀ i ∈ { 1 ; … ; n − 1 } ) P i ⟶ P n {displaystyle (forall iin {1;dots ;n-1})P_{i}longrightarrow P_{n}} эквивалентна P 1 {displaystyle P_{1}} . Однако зачастую доказывать индукционный переход для P 1 {displaystyle P_{1}} всё равно приходится отдельно, так что разумно бывает выделить эту его часть в качестве базы.

Принцип полной математической индукции эквивалентен аксиоме индукции в аксиомах Пеано.

Также он является прямым применением более сильной трансфинитной индукции.

История

Осознание метода математической индукции как отдельного важного метода восходит к Блезу Паскалю и Герсониду, хотя отдельные случаи применения встречаются ещё в античные времена у Прокла и Эвклида. Современное название метода было введено де Морганом в 1838 году.

Примеры

Задача. Доказать, что, каковы бы ни были натуральное n и вещественное q ≠ 1, выполняется равенство

1 + q + q 2 + ⋯ + q n = 1 − q n + 1 1 − q . {displaystyle 1+q+q^{2}+cdots +q^{n}={frac {1-q^{n+1}}{1-q}}.}

Доказательство. Индукция по n.

База, n = 1:

1 + q = ( 1 − q ) ( 1 + q ) 1 − q = 1 − q 1 + 1 1 − q . {displaystyle 1+q={frac {(1-q)(1+q)}{1-q}}={frac {1-q^{1+1}}{1-q}}.}

Переход: предположим, что

1 + q + ⋯ + q n = 1 − q n + 1 1 − q , {displaystyle 1+q+cdots +q^{n}={frac {1-q^{n+1}}{1-q}},}

тогда

1 + q + ⋯ + q n + q n + 1 = 1 − q n + 1 1 − q + q n + 1 = {displaystyle 1+q+cdots +q^{n}+q^{n+1}={frac {1-q^{n+1}}{1-q}}+q^{n+1}=} = 1 − q n + 1 + ( 1 − q ) q n + 1 1 − q = 1 − q n + 1 + q n + 1 − q ( n + 1 ) + 1 1 − q = 1 − q ( n + 1 ) + 1 1 − q {displaystyle ={frac {1-q^{n+1}+(1-q)q^{n+1}}{1-q}}={frac {1-q^{n+1}+q^{n+1}-q^{(n+1)+1}}{1-q}}={frac {1-q^{(n+1)+1}}{1-q}}} ,

что и требовалось доказать.

Комментарий: истинность утверждения P n {displaystyle P_{n}} в этом доказательстве — то же, что истинность равенства

1 + q + ⋯ + q n = 1 − q n + 1 1 − q . {displaystyle 1+q+cdots +q^{n}={frac {1-q^{n+1}}{1-q}}.}

Вариации и обобщения

  • Обратная индукция
  • Структурная индукция
  • Трансфинитная индукция