МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ

МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ весьма
общий способ математич. доказательств и определений. Индуктивные доказательства
основаны на т. н. принципе М. и., являющемся одной из основных математич.
аксиом. Пусть, напр., требуется доказать для любого натурального (целого
положительного) числа п формулу:

1+3 + 5 + ...+(2и-1) = и². (1)
При п = 1 эта формула даёт 1 = 1². Чтобы доказать правильность
формулы при любом п, допускают, что её уже удалось доказать для
нек-рого определённого числа N, т. е. предполагают, что

1+3 + 5+....+(2N-1) = №. (2) Далее, опираясь
на сделанное допущение, пытаются доказать правильность формулы (1) для
числа на единицу большего, т. е. для п = N +
1. В данном
случае достаточно присоединить к сумме в левой части равенства (2) ещё
одно слагаемое: (2N +1); тогда и правая часть равенства должна увеличиться
на (2N + 1) и, следовательно,

1+3 + 5 + ....+(2ЛГ-1) + (2N+1) = = N²+(2N+1)
= (N +1)². Но тот же результат получится, если в формуле (1)
заменить п на N + 1. Итак, из справедливости формулы (1)
при п - N вытекает (каково бы ни было
N)
её правильность
и при п = N + 1. Но при п =
1 формула (1) верна, следовательно,
она верна также и при п = 2 = = 1 + 1, 3 = 2+1, 4 = 3+1, 5 = 4 +
1 и т. д. Так как последовательным прибавлением единицы можно получить
(начиная с единицы) любое натуральное число, то формула (1) действительно
верна при любом натуральном числе п.
Как ни очевидна заключительная
часть приведённого рассуждения, она опирается на нек-рую аксиому, не сводимую
только к общим законам логики, но выражающую одно из основных свойств натуральных
чисел. Общая формулировка этой аксиомы такова.

Принцип М. и. Пусть: 1) число единица обладает
свойством А; 2) из того, что к.-л. натуральное число и обладает
свойством А, вытекает, что и число п + 1 обладает свойством
А.
При
таких условиях любое натуральное число обладает свойством
А.

В разобранном выше примере свойство А
числа
п
выражается так: "для числа п справедливо равенство (1)". Если
принцип М. и. принят в качестве аксиомы, то каждое отд. доказательство,
опирающееся на этот принцип, следует рассматривать как чисто дедуктивное.
При доказательстве [напр., формулы (1)], основанном на этом принципе, не
происходит заключения от частного к общему, т. к. одна из посылок (сам
принцип М. и.) по меньшей мере столь же обща, как и заключение.

Принцип М. и., сформулированный выше, служит,
как было показано, для доказательства математич. теорем. Помимо этого,
в математике употребляются ещё т. н. индуктивные определения. Таково, напр.,
следующее определение членов игеометрич. прогрессии
с первым членом а и знаменателем q: 1) ua, 2) u

Условия 1) и 2) однозначно определяют члены
прогрессии идля всех натуральных чисел
п.
Доказательство
того, что это действительно так, может быть основано на принципе М. и.;
в данном случае можно, однако, непосредственно получить выражение ичерез
п
: и= aq^n-1.

Принцип М. и. можно заменить равносильными
ему предложениями, напр, таким: если подмножество М множества всех
натуральных чисел N содержит 1 и вместе с любым своим элементом
т
содержит
и т+1, то М = N.