Большая советская энциклопедия:
Математическая индукция
Весьма общий способ математических доказательств и определений. Индуктивные доказательства основаны на так называемом принципе М. и., являющемся одной из основных математических аксиом. Пусть, например, требуется доказать для любого натурального (целого положительного) числа n формулу:
1 + 3 + 5 + ... + (2n — 1) = n2 (1)
При n = 1 эта формула даёт 1 = 12. Чтобы доказать правильность формулы при любом n, допускают, что её уже удалось доказать для некоторого определённого числа N, то есть предполагают, что
1 + 3 + 5 + ... + (2N — 1) = N2. (2)
Далее, опираясь на сделанное допущение, пытаются доказать правильность формулы (1) для числа на единицу большего, то есть для n = N + 1. В данном случае достаточно присоединить к сумме в левой части равенства (2) ещё одно слагаемое: (2N + 1); тогда и правая часть равенства должна увеличиться на (2N +1) и, следовательно,
1 + 3 + 5 + ... + (2N — 1) + (2N + 1) = N2 + (2N + 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.
Математическая энциклопедия:
Метод доказательства математич. утверждений, основанный на принципе математической индукции: утверждение (х), зависящее от натурального параметра х, считается доказанным, если доказано А(1) и для любого натурального пиз предположения, что верно (п), выведено, что верно также А(n+1). Доказательство утверждения А(1) составляет первый шаг (или базис) индукции, а доказательство А(n+1)в предположении, что верно (п), наз. индукционным переходом. При этом хназ. параметром индукции, а предположение (п).при доказательстве А(n+1) наз. индуктивным предположением. Принцип М. и. является также основанием для индуктивных определений. Простейшим примером такого определения является определение свойства: "быть словом длины n в данном алфавите Базис индукции: каждая буква алфавита (*) есть слово длины 1. Индукционный переход: если Е — слово длины п, то каждое слово Еai, где есть слово длины n+1. Индукция может начинаться с нулевого шага. Часто бывает так, что А(1) и А(n+1) доказываются аналогичными рассуждениями. В таких случаях удобно пользоваться следующей эквивалентной формой принципа М. и. Если для всякого пиз предположения: (х).верно при любом натуральном x<n — следует, что (х).верно также при х=п, то утверждение (х).верно при любом натуральном х. В такой форме принцип М. и. может быть применен для доказательства утверждений (х), в к-рых параметр хпробегает то пли иное множество, вполне упорядоченное по нек-рому трансфинитному типу (трансфинитная индукция). В качестве простых примеров трансфинитной индукции отметим индукцию по параметру, пробегающему множество всех слов в данном алфавите, упорядоченное лексикографически, и индукцию по построению формул в данном логико-математич. исчислении. Иногда для доказательства нек-рого утверждения А(n) индукцией по пприходится одновременно с (п).доказывать индукцией по пряд других утверждений, без к-рых индукцию для (п).не удается провести. В формальной арифметике можно указать такие утверждения (п), для к-рых в рамках рассматриваемого исчисления индукция не может быть проведена без добавления новых вспомогательных утверждений, зависящих от п(см. [3]). В таких случаях мы имеем дело с доказательством ряда утверждений совместной математической индукцией. Все эти утверждения формально можно объединить в одну конъюнкцию, однако практически такое объединение только усложнило бы рассмотрение, т. к. при этом исчезла бы возможность неформальных осмысленных ссылок на определенные индуктивные предположения. В нек-рых конкретных математич. исследованиях число понятий и утверждений, определяемых и доказываемых сложной совместной индукцией, исчисляется трехзначной цифрой (см. [4]). В этом случае ввиду наличия в индуктивном доказательстве большого числа перекрестных ссылок на индуктивные предположения, для содержательного (неформального) понимания любого (даже самого простого) определения или утверждения при данном достаточно большом значении параметра индукции читатель должен быть знаком с содержанием всех вводимых совместной индукцией понятий и многих свойств этих понятий для меньших значений параметра индукции. По-видимому, единственным корректным с логич. точки зрения выходом из возникающего здесь логич. круга является аксиоматич. изложение всей рассматриваемой системы понятий. Таким образом, большое число понятий, определяемых совместной индукцией, приводит к необходимости применения аксиоматического метода в индуктивном определении и доказательстве. Это — наглядный пример необходимости аксиоматич. метода для решения конкретных математич. задач, а не только вопросов, относящихся к основаниям математики. Лит.:[1] Гильберт Д., Б е р н а й с П., Основания математики. Логические исчисления и формализация арифметики, пер. с нем., М., 1979; [2] К л и н и С. К., Введение в метаматематику, пер. с англ., М., 1957; [3] Ц и н м а н Л. Л., "Матем. сб.", 1968, т. 77, №1, с. 71-104; [4] Адян С. И., Проблема Бернсайда и тождества в группах, М., 1975. С. И. Адян.
Научно-технический словарь:
МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ, метод, доказывающий, что математическое утверждение верно для любого положительного целого числа п, если выполняются два условия: 1) оно верно для основной величины, например, 1, и 2) если оно верно для значения k, то верно и для k+1. Если условия (1) и (2) выполняются, тогда это утверждение верно для любого положительного целого числа п. Формула для сумм первых натуральных чисел — результат, который можно доказать только при помощи математической индукции. Такая методика убедительно доказывает, что результат верен для бесконечного множества значений.
© «СловоТолк.Ру» — толковые и энциклопедические словари, 2007-2020