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

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

 Как видно из самого названия, индукция бывает не только в математике. Иногда называют «неполной индукцией» переход от частных примеров к общим закономерностям. Бывает индукция и в физике (катушки индуктивности, явление самоиндукции). Но  мы будем говорить только о математической (полной) индукции.

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

Вообразим очередь, где первой стоит женщина, за ней снова женщина, а за ней снова женщина. Верно ли, что все стоящие в очереди — женщины?

Конечно, верно! Раз первые три человека в очереди — женщины, то, скорее всего, это очередь за косметикой, или за чем-нибудь таким, в чём нуждаются и разбираются исключительно женщины, и мужчин в этой очереди нет.

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

Рассмотрим два утверждения:

Первый человек в очереди есть женщина.

За женщиной в очереди может стоять только женщина.

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

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

Пусть имеется последовательность утверждений  И пусть первое утверждение  верно, и мы умеем доказывать, что из верности утверждения следует верность . Тогда все утверждения в этой последовательности верны.

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

Заметим, что аксиому индукции можно заменить на аксиому существования минимума, и доказать аксиому индукции как теорему.

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

Пусть имеется последовательность утверждений  . И пусть мы умеем доказывать первое из них, а так же то, что из верности утверждений   следует верность  . Тогда все утверждения в этой последовательности верны.

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

Пусть m - натуральное число, m > 1 и P(n) - предложение, зависящее от n, n ≥ m. Если

1. P(m) справедливо;
2. P(n) будучи истинным предложением, влечет истинность предложения   P(n + 1) для любого натурального n, n ≥ m, тогда P(n) - истинное предложение для любого натурального n, n ≥ m.

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

Пример 1. Доказать следующие равенства

где n ∈ N.

Решение. a) При n = 1 равенство примет вид  1=1, следовательно, P(1) истинно. Предположим, что данное равенство справедливо, то есть, имеет место

.

Следует проверить (доказать), что P(n + 1), то есть

истинно. Поскольку (используется предположение индукции)

получим

то есть, P(n + 1) - истинное утверждение.

Таким образом, согласно методу математической индукции, исходное равенство справедливо для любого натурального n.

Замечание 2. Этот пример можно было решить и иначе. Действительно, сумма 1 + 2 + 3 + ... + n есть сумма первых n членов арифметической прогрессии с первым членом a1 = 1 и разностью d = 1. В силу известной формулы , получим

b) При n = 1 равенство примет вид: 2·1 - 1 = 12 или 1=1, то есть, P(1) истинно. Допустим, что имеет место равенство

1 + 3 + 5 + ... + (2n - 1) = n2

и докажем, что имеет место P(n + 1):

1 + 3 + 5 + ... + (2n - 1) + (2(n + 1) - 1) = (n + 1)2

или

1 + 3 + 5 + ... + (2n - 1) + (2n + 1) = (n + 1)2.

Используя предположение индукции, получим

1 + 3 + 5 + ... + (2n - 1) + (2n + 1) = n2 + (2n + 1) = (n + 1)2.

Таким образом, P(n + 1) истинно и, следовательно, требуемое равенство доказано.

Замечание 3. Этот пример можно решить (аналогично предыдущему) без использования метода математической индукции.

c) При n = 1 равенство истинно:  1=1. Допустим, что истинно равенство

и покажем, что

то есть истинность P(n) влечет истинность P(n + 1). Действительно,

и, так как 2n2 + 7n + 6 = (2n + 3)(n + 2), получим

и, следовательно, исходное равенство справедливо для любого натурального n.

d) При n = 1 равенство справедливо:  1=1. Допустим, что имеет место

и докажем, что

Действительно,

e) Утверждение P(1) справедливо:  2=2. Допустим, что равенство

справедливо, и докажем, что оно влечет равенство

Действительно,

Следовательно, исходное равенство имеет место для любого натурального n.

f) P(1) справедливо:  1/3 = 1/3. Пусть имеет место равенство P(n):

.

Покажем, что последнее равенство влечет следующее:

Действительно, учитывая, что P(n) имеет место, получим

Таким образом, равенство доказано.

g) При n = 1 имеем a + b = b + a и, следовательно, равенство справедливо.

Пусть формула бинома Ньютона справедлива при n = k, то есть,

Тогда

Используя равенство  получим

Принцип наименьшего числа. В любом непустом множестве натуральных чисел есть наименьшее.

 В пустом множестве нет ни одного элемента, так что для него принцип наименьшего числа нарушается.

Выведем принцип математической индукции из принципа наименьшего числа. Доказательство от противного.

 Предположим, что утверждение A(n) верно не при любых n. Рассмотрим множество тех чисел, для которых оно неверно. В нем есть наименьшее число N. Это число не равно 1, так как A(1) истинно. Но тогда A(N − 1) истинно по выбору N. Значит, и A(N) = A(N − 1 + 1) истинно. Пришли к противоречию.

 Обратно. Докажем принцип наименьшего числа индукцией. Пусть в множестве X ⊆ N нет наименьшего числа. В качестве утверждения A(n) возьмем такое: «все числа от 0 до n не принадлежат X». Ясно, что A(0) (так как меньше нуля чисел нет). С другой стороны, если A(n) истинно, то A(n+1) тоже истинно (иначе n+1 наименьшее в X). По принципу математической индукции A(n) истинно для всех n. Поэтому множество X пустое.

 Покажем как применять принцип наименьшего числа.

Пример 2. На плоскости проведено n прямых, n > 3, не все из которых проходят через одну точку. Они делят плоскость на области. Докажите, что среди этих областей есть треугольная (быть может, бесконечная).

Случай n = 3 анализируется непосредственно. Теперь от противного. Рассмотрим наименьшее N > 3, при котором есть конфигурация прямых без треугольных областей.

 При выбрасывании любой из N прямых получается либо набор прямых, проходящих через одну точку, либо конфигурация с треугольной областью. Первый случай встречается лишь один раз. Рассмотрим любую другую прямую l и треугольную область T, образованную оставшимися прямыми.

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

 Известное из школы доказательство иррациональности  также использует принцип наименьшего числа.

Литература:

1. Шень А.  Математическая индукция. | 5-е изд., стереотип. | М.: МЦНМО, 2016. | 32 с.: ил.
2. https://ru.wikibooks.org/wiki/
3. http://www.math.md/school/krujok/inductr/inductr.html
4. http://www.mi-ras.ru/~podolskii/files/lecture1.pdf