БСЭ1/Математическая индукция

← Математико-эмпирическая школа

Математическая индукция Большая советская энциклопедия (1-е издание)

Математическая логика →

Словник: Маммилярия — Мера стоимости. Источник: т. XXXVIII (1938): Маммилярия — Мера стоимости, стлб. 405—406

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

$1^{2}+2^{2}+3^{2}+....+n^{2}={\frac {(2n+1)(n+1)n}{6}}$. (1)

Легко проверить непосредственным вычислением, что формула (1) справедлива при $n=1$; было бы нетрудно выполнить такую проверку и для любого другого числа (например 17), но дело идет о том, чтобы доказать ее правильность при любом $n$. Будем рассуждать так: пусть нам уже удалось установить, что формула (1) верна для некоторого определенного числа $N$, т. е. известно, что

$1^{2}+2^{2}+3^{2}+....+N^{2}={\frac {(2N+1)(N+1)N}{6}}$. (2)

Подставляя теперь в формулу (1) вместо $n$ число $N+1$, получим

$1^{2}+2^{2}+3^{2}+....+N^{2}+(N+1)^{2}=$ $={\frac {(2N+3)(N+2)(N+1)}{6}}$. (3)

Формула (3) пока еще не доказана, но, применяя к первым $N$ слагаемым левой части равенства формулу (2), к-рую мы считаем уже доказанной, замечаем, что для доказательства формулы (3) достаточно проверить справедливость равенства

${\frac {(2N+1)(N+1)N}{6}}+(N+1)^{2}=$ $={\frac {(2N+3)(N+2)(N+1)}{6}}$. (4)

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

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

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

Принцип М. и., сформулированный выше, служит, как мы видели, для доказательства математических теорем. Помимо этого, в математике употребляются еще т. н. индуктивные определения. Таково, напр., следующее определение итерированных ядер $K_{n}(x,y)$ ядра $K(x,y)$; полагаем:

                            1) $K_{1}(x,y)=K(x,y)$

                            2) $K_{n+1}(x,y)=\int \limits _{a}^{b}K_{n}(x,\xi )K(\xi ,y)\,d\xi$

Принято считать, что условия 1) и 2) однозначно определяют ядра $K_{n}(x,y)$ для всех натуральных чисел $n$. Доказательство того, что это действительно так, может быть основано на сформулированном выше принципе математической индукции.

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

А. Колмогоров.