Математическая индукция
|
Математическая индукция — метод математического доказательства, который используется, чтобы доказать истинность некоторого утверждения для всех натуральных чисел. Для этого сначала проверяется истинность утверждения с номером 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}}.}Вариации и обобщения
|
