Значение МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ в Большой советской энциклопедии, БСЭ

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

индукция , весьма общий способ математических доказательств и определений. Индуктивные доказательства основаны на так называемом принципе М. и., являющемся одной из основных математических аксиом. Пусть, например, требуется доказать для любого натурального (целого положительного) числа n формулу:

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

При n 1 эта формула даёт 1 12 . Чтобы доказать правильность формулы при любом n , допускают, что её уже удалось доказать для некоторого определённого числа N , то есть предполагают, что

1 + 3 + 5 + ... + (2 N - 1) N2 .(2)

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

1 + 3 + 5 + ... + (2 N - 1) + (2 N + 1) N2 + (2 N + 1) ( N + 1)2.

Но тот же результат получится, если в формуле (1) заменить n на N + 1 .

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

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

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

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

1) u1 a ,

2) un+1 unq .

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

un aqn-1 .

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

Большая советская энциклопедия, БСЭ.