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

Форма математического доказательства

Математическая индукция может быть неформально проиллюстрирована ссылкой на последовательный эффект падения домино . ^{[1] [2]}

Математическая индукция — это метод доказательства того, что утверждение верно для любого натурального числа , то есть что все бесконечное число случаев   имеет место. Для этого сначала доказывается простой случай, а затем показывается, что если мы предположим, что утверждение истинно для данного случая, то и следующий случай также будет истинным. Неформальные метафоры помогают объяснить эту технику, например, падение домино или подъем по лестнице: ${\displaystyle P(n)}$ ${\displaystyle n}$ ${\displaystyle P(0),P(1),P(2),P(3),\dots }$

Математическая индукция доказывает, что мы можем подняться по лестнице так высоко, как нам хочется, доказывая, что мы можем подняться на нижнюю ступеньку (основание ) и что с каждой ступеньки мы можем подняться на следующую (ступеньку ) .

—  Конкретная математика , поля 3 страницы.

Доказательство по индукции состоит из двух случаев. Первый, базовый случай , доказывает утверждение без предположения о каких-либо знаниях других случаев. Второй случай, шаг индукции , доказывает, что если утверждение верно для любого данного случая , то оно должно быть справедливым и для следующего случая . Эти два шага доказывают, что утверждение справедливо для любого натурального числа . Базовый случай не обязательно начинается с , но часто и, возможно, с любого фиксированного натурального числа , устанавливающего истинность утверждения для всех натуральных чисел . ${\displaystyle n=0}$ ${\displaystyle n=k}$ ${\displaystyle n=k+1}$ ${\displaystyle n}$ ${\displaystyle n=0}$ ${\displaystyle n=1}$ ${\displaystyle n=N}$ ${\displaystyle n\geq N}$

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

Хотя название может указывать на иное, математическую индукцию не следует путать с индуктивными рассуждениями , используемыми в философии (см. «Проблема индукции» ). Математический метод исследует бесконечное множество случаев, чтобы доказать общее утверждение, но делает это с помощью конечной цепочки дедуктивных рассуждений , включающих переменную , которая может принимать бесконечно много значений. ^[4] ${\displaystyle n}$

История

В 370 г. до н.э. «Парменид» Платона , возможно, содержал следы раннего примера неявного индуктивного доказательства. ^[5]

Самое раннее неявное доказательство методом математической индукции было написано аль-Караджи около 1000 года нашей эры, который применил его к арифметическим последовательностям для доказательства биномиальной теоремы и свойств треугольника Паскаля . Хотя оригинальная работа была утеряна, позже на нее ссылался Аль-Самавал аль-Магриби в своем трактате аль-Бахир фил-джабр («Блестящие алгебра») примерно в 1150 году нашей эры. ^{[6] [7]}

Кац говорит в своей истории математики

Другая важная идея, предложенная аль-Караджи и продолженная ас-Самауалем и другими, заключалась в индуктивном аргументе для работы с определенными арифметическими последовательностями. Таким образом, аль-Караджи использовал такой аргумент, чтобы доказать результат о суммах целых кубов, уже известный Арьябхате [...] Аль-Караджи, однако, не сформулировал общего результата для произвольного n . Он сформулировал свою теорему для конкретного целого числа 10 [...] Его доказательство, тем не менее, было явно рассчитано на распространение на любое другое целое число. [...] Аргумент Аль-Караджи включает в себя, по сути, два основных компонента современного аргумента по индукции, а именно истинность утверждения для n = 1 (1 = 1 ³ ) и вывод истины для n = k из то же, что n = k - 1. Конечно, этот второй компонент не является явным, поскольку в некотором смысле аргумент аль-Караджи является обратным; то есть он начинает с n = 10 и опускается до 1, а не идет вверх. Тем не менее, его аргумент в аль-Фахри является самым ранним из сохранившихся доказательств формулы суммы для целых кубов . ^[8]

В Индии первые неявные доказательства методом математической индукции появляются в « циклическом методе » Бхаскары . ^[9]

Однако ни один из этих древних математиков не сформулировал в явном виде гипотезу индукции. Другой подобный случай (вопреки тому, что написал Вакка, как тщательно показал Фройденталь) ^[10] произошел с Франческо Мауролико в его Arithmeticorum libri duo (1575), который использовал эту технику, чтобы доказать, что сумма первых n нечетных целых чисел равна n ² .

Самое раннее строгое использование индукции было у Герсонида (1288–1344). ^{[11] [12]} Первая явная формулировка принципа индукции была дана Паскалем в его «Трактате о треугольной арифметике» (1665). Другой француз, Ферма , широко использовал схожий принцип: косвенное доказательство путем бесконечного спуска .

Гипотезу индукции также использовал швейцарец Якоб Бернулли , и с тех пор она стала широко известна. Современная формальная трактовка этого принципа появилась только в 19 веке, благодаря Джорджу Булю , ^[13] Огастесу Де Моргану , Чарльзу Сандерсу Пирсу , ^{[14] [15]} Джузеппе Пеано и Ричарду Дедекинду . ^[9]

Описание

Самая простая и распространенная форма математической индукции предполагает, что утверждение, включающее натуральное число n (то есть целое число n ≥ 0 или 1), справедливо для всех значений n . Доказательство состоит из двух шагов:

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

Гипотеза на этапе индукции о том, что утверждение справедливо для определенного n , называется гипотезой индукции или индуктивной гипотезой . Чтобы доказать шаг индукции, принимается гипотеза индукции для n , а затем используется это предположение, чтобы доказать, что утверждение справедливо для n + 1 .

Авторы, которые предпочитают определять натуральные числа начиная с 0, используют это значение в базовом случае; те, кто определяет натуральные числа начиная с 1, используют это значение.

Примеры

Сумма последовательных натуральных чисел

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

$${\displaystyle P(n)\!:\ \ 0+1+2+\cdots +n={\frac {n(n+1)}{2}}.}$$

Это формула общей формулы суммы натуральных чисел, меньших или равных данному числу; на самом деле бесконечная последовательность утверждений: , , и т. д. ${\displaystyle 0={\tfrac {(0)(0+1)}{2}}}$ ${\displaystyle 0+1={\tfrac {(1)(1+1)}{2}}}$ ${\displaystyle 0+1+2={\tfrac {(2)(2+1)}{2}}}$

Предложение. Для каждого, ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle 0+1+2+\cdots +n={\tfrac {n(n+1)}{2}}.}$

Доказательство. Пусть P ( n ) — утверждение. Мы приведем доказательство индукцией по n . ${\displaystyle 0+1+2+\cdots +n={\tfrac {n(n+1)}{2}}.}$

Базовый случай: покажите, что утверждение справедливо для наименьшего натурального числа n = 0 .

P (0) явно верно: ${\displaystyle 0={\tfrac {0(0+1)}{2}}\,.}$

Шаг индукции: покажите, что для любого k ≥ 0 , если P ( k ) выполняется, то P ( k + 1) также выполняется.

Предположим, что индукционное предположение гласит, что для конкретного k выполняется единственный случай n = k , что означает, что P ( k ) верно:

$${\displaystyle 0+1+\cdots +k={\frac {k(k+1)}{2}}.}$$

$${\displaystyle (0+1+2+\cdots +k)+(k+1)={\frac {k(k+1)}{2}}+(k+1).}$$

Алгебраически правая часть упрощается как:

$${\displaystyle {\begin{aligned}{\frac {k(k+1)}{2}}+(k+1)&={\frac {k(k+1)+2(k+1)}{2}}\\&={\frac {(k+1)(k+2)}{2}}\\&={\frac {(k+1)((k+1)+1)}{2}}.\end{aligned}}}$$

Приравнивая крайние левую и правую части, получаем, что:

$${\displaystyle 0+1+2+\cdots +k+(k+1)={\frac {(k+1)((k+1)+1)}{2}}.}$$

P ( k +1)

Вывод: поскольку и базовый случай, и шаг индукции оказались верными, с помощью математической индукции утверждение P ( n ) справедливо для любого натурального числа n . КЭД

Тригонометрическое неравенство

Индукция часто используется для доказательства неравенств . В качестве примера докажем, что для любого действительного и натурального числа . ${\displaystyle \left|\sin nx\right|\leq n\left|\sin x\right|}$ ${\displaystyle x}$ ${\displaystyle n}$

На первый взгляд может показаться, что более общую версию для любых действительных чисел можно доказать без индукции; но случай показывает, что это может быть ложным для нецелых значений . Это предполагает, что мы рассмотрим это утверждение специально для натуральных значений , а индукция является наиболее удобным инструментом. ${\displaystyle \left|\sin nx\right|\leq n\left|\sin x\right|}$ ${\displaystyle n,x}$ ${\textstyle n={\frac {1}{2}},\,x=\pi }$ ${\displaystyle n}$ ${\displaystyle n}$

Предложение. Для любогои,. ${\displaystyle x\in \mathbb {R} }$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle \left|\sin nx\right|\leq n\left|\sin x\right|}$

Доказательство. Зафиксируйте произвольное действительное число и пусть будет утверждением . Наводим на . ${\displaystyle x}$ ${\displaystyle P(n)}$ ${\displaystyle \left|\sin nx\right|\leq n\left|\sin x\right|}$ ${\displaystyle n}$

Базовый вариант: расчет проверяет . ${\displaystyle \left|\sin 0x\right|=0\leq 0=0\left|\sin x\right|}$ ${\displaystyle P(0)}$

Шаг индукции: мы показываем импликацию для любого натурального числа . Предположим гипотезу индукции: для данного значения верен единственный случай . Используя формулу сложения углов и неравенство треугольника , выводим: ${\displaystyle P(k)\implies P(k+1)}$ ${\displaystyle k}$ ${\displaystyle n=k\geq 0}$ ${\displaystyle P(k)}$

$${\displaystyle {\begin{aligned}\left|\sin(k+1)x\right|&=\left|\sin kx\cos x+\sin x\cos kx\right|&&{\text{(angle addition)}}\\&\leq \left|\sin kx\cos x\right|+\left|\sin x\,\cos kx\right|&&{\text{(triangle inequality)}}\\&=\left|\sin kx\right|\left|\cos x\right|+\left|\sin x\right|\left|\cos kx\right|\\&\leq \left|\sin kx\right|+\left|\sin x\right|&&(\left|\cos t\right|\leq 1)\\&\leq k\left|\sin x\right|+\left|\sin x\right|&&{\text{(induction hypothesis}})\\&=(k+1)\left|\sin x\right|.\end{aligned}}}$$

Неравенство между крайними левыми и правыми величинами показывает, что оно верно, что завершает шаг индукции. ${\displaystyle P(k+1)}$

Вывод: предложение справедливо для всех натуральных чисел QED. ${\displaystyle P(n)}$ ${\displaystyle n.}$ 

Варианты

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

Базовый вариант, отличный от 0 или 1

Если кто-то желает доказать утверждение не для всех натуральных чисел, а только для всех чисел n, больших или равных определенному числу b , то доказательство по индукции состоит из следующего:

1. Покажем, что утверждение справедливо, когда n = b .
2. Показывая, что если утверждение справедливо для произвольного числа n ≥ b , то то же самое утверждение справедливо и для n + 1 .

Это можно использовать, например, чтобы показать, что 2 ⁿ ≥ n + 5 для n ≥ 3 .

Таким образом можно доказать, что некоторое утверждение P ( n ) справедливо для всех n ≥ 1 или даже для всех n ≥ −5 . Эта форма математической индукции на самом деле является частным случаем предыдущей формы, потому что, если доказываемое утверждение представляет собой P ( n ) , то доказательство его с помощью этих двух правил эквивалентно доказательству P ( n + b ) для всех натуральных чисел n с индукционный базовый случай 0 . ^[16]

Пример: формирование долларовых сумм монетами

Предположим, что имеется бесконечный запас монет номиналом 4 и 5 долларов. С помощью индукции можно доказать, что любая целая сумма долларов, большая или равная 12, может быть образована комбинацией таких монет. Пусть S ( k ) обозначает утверждение « k долларов можно образовать из комбинации 4- и 5-долларовых монет». Доказательство того, что S ( k ) верно для всех k ≥ 12 , может быть получено индукцией по k следующим образом:

Базовый случай: показать, что S ( k ) выполняется для k = 12 , просто: возьмите три монеты по 4 доллара.

Шаг индукции: учитывая, что S ( k ) выполняется для некоторого значения k ≥ 12 ( гипотеза индукции ), докажите, что S ( k + 1) тоже выполняется. Предположим, что S ( k ) верно для некоторого произвольного k ≥ 12 . Если существует решение для k долларов, которое включает хотя бы одну монету достоинством 4 доллара, замените ее монетой достоинством 5 долларов, чтобы получить k + 1 доллар. В противном случае, если используются только монеты номиналом 5 долларов, k должно быть кратно 5 и, следовательно, не менее 15; но тогда мы можем заменить три монеты по 5 долларов на четыре монеты по 4 доллара, чтобы получить k + 1 доллар. В каждом случае S ( k + 1) верно.

Следовательно, по принципу индукции S ( k ) выполняется для всех k ≥ 12 , и доказательство завершено.

В этом примере, хотя S ( k ) также справедливо для , приведенное выше доказательство не может быть изменено для замены минимальной суммы в 12 долларов на любое меньшее значение m . Для m = 11 базовый случай фактически неверен; при m = 10 второй случай на этапе индукции (замена трех монет размером 5 на четыре монеты номиналом 4 доллара) не сработает; не говоря уже о еще более низких m . ${\textstyle k\in \{4,5,8,9,10\}}$

Индукция на более чем одном счетчике

Иногда желательно доказать утверждение, включающее два натуральных числа, n и m , путем итерации процесса индукции. То есть доказываются базовый случай и шаг индукции для n , и в каждом из них доказываются базовый случай и шаг индукции для m . См., например, доказательство коммутативности , сопровождающее сложение натуральных чисел . Возможны также более сложные аргументы, включающие три и более счетчиков.

Бесконечный спуск

Метод бесконечного спуска — это разновидность математической индукции, которую использовал Пьер де Ферма . Он используется, чтобы показать, что некоторое утверждение Q ( n ) неверно для всех натуральных чисел n . Его традиционная форма состоит в том, чтобы показать, что если Q ( n ) верно для некоторого натурального числа n , то оно справедливо и для некоторого строго меньшего натурального числа m . Поскольку не существует бесконечных убывающих последовательностей натуральных чисел, такая ситуация была бы невозможной, тем самым показывая ( от противного ), что Q ( n ) не может быть истинным для любого n .

В справедливости этого метода можно убедиться, исходя из обычного принципа математической индукции. Используя математическую индукцию для утверждения P ( n ) , определенного как « Q ( m ) , неверно для всех натуральных чисел m, меньших или равных n », из этого следует, что P ( n ) выполняется для всех n , что означает, что Q ( n ) неверно для любого натурального числа n .

Ограниченная математическая индукция

Если кто-то хочет доказать, что свойство P справедливо для всех натуральных чисел, меньших или равных n , достаточно доказать, что P удовлетворяет следующим условиям: ^[17]

1. P имеет место для 0,
2. Для любого натурального числа x меньше n , если P выполняется для x , то P выполняется для x + 1.

Префиксная индукция

Наиболее распространенная форма доказательства методом математической индукции требует доказательства на этапе индукции, что

$${\displaystyle \forall k\,(P(k)\to P(k+1))}$$

после чего принцип индукции «автоматизирует» n применений этого шага для перехода от P (0) к P ( n ) . Это можно назвать «индукцией предшественника», потому что каждый шаг доказывает что-то о числе на основе чего-то о предшественнике этого числа.

Интересным вариантом вычислительной сложности является «префиксная индукция», при которой на этапе индукции доказывается следующее утверждение:

$${\displaystyle \forall k\,(P(k)\to P(2k)\land P(2k+1))}$$

$${\displaystyle \forall k\,\left(P\!\left(\left\lfloor {\frac {k}{2}}\right\rfloor \right)\to P(k)\right)}$$

Затем принцип индукции «автоматизирует» log ₂  n применений этого вывода для перехода от P (0) к P ( n ) . Фактически, это называется «префиксной индукцией», потому что каждый шаг доказывает что-то о числе на основе чего-то о «префиксе» этого числа, сформированном путем усечения младшего бита его двоичного представления . Это также можно рассматривать как применение традиционной индукции по длине этого двоичного представления.

Если традиционная индукция предшественников интерпретируется в вычислительном отношении как цикл из n шагов, то индукция по префиксу будет соответствовать циклу из n шагов. По этой причине доказательства, использующие префиксную индукцию, «более конструктивны», чем доказательства, использующие индукцию предшественников.

Индукция предшественника может тривиально моделировать префиксную индукцию по тому же утверждению. Префиксная индукция может имитировать индукцию предшественника, но только за счет усложнения синтаксиса утверждения (добавление ограниченного квантора универсальности ), поэтому интересные результаты, связывающие префиксную индукцию с вычислениями за полиномиальное время , зависят от полного исключения неограниченных кванторов и ограничения чередования. ограниченных универсальных и экзистенциальных кванторов, разрешенных в этом утверждении. ^[18]

Можно пойти еще дальше: нужно доказать

$${\displaystyle \forall k\,\left(P\!\left(\left\lfloor {\sqrt {k}}\right\rfloor \right)\to P(k)\right)}$$

log log nP (0)P ( n )^{[ нужна цитата ]}

Полная (сильная) индукция

Другой вариант, называемый полной индукцией , курсом индукции значений или сильной индукцией (в отличие от которого базовую форму индукции иногда называют слабой индукцией ), упрощает доказательство шага индукции с помощью более сильной гипотезы: доказывается утверждение под предположение, которое справедливо для всех натуральных чисел меньше ; напротив, базовая форма предполагает только . Название «сильная индукция» не означает, что этот метод может доказать больше, чем «слабая индукция», а просто относится к более сильной гипотезе, используемой на этапе индукции. ${\displaystyle P(m+1)}$ ${\displaystyle P(n)}$ ${\displaystyle n}$ ${\displaystyle m+1}$ ${\displaystyle P(m)}$

Фактически, можно показать, что эти два метода фактически эквивалентны, как объяснено ниже. В этой форме полной индукции все еще необходимо доказать базовый случай, и может быть даже необходимо доказать дополнительные базовые случаи, например, перед применением общего аргумента, как в приведенном ниже примере числа Фибоначчи . ${\displaystyle P(0)}$ ${\displaystyle P(1)}$ ${\displaystyle F_{n}}$

Хотя только что описанная форма требует доказательства базового случая, в этом нет необходимости, если можно доказать (при условии, что для всех нижних ) для всех . Это частный случай трансфинитной индукции, описанный ниже, хотя он больше не эквивалентен обычной индукции. В этой форме базовый случай включается в состав случая , где доказано без каких-либо других предположений; этот случай, возможно, придется рассматривать отдельно, но иногда тот же аргумент применяется для и , что делает доказательство более простым и элегантным. Однако в этом методе очень важно гарантировать, что доказательство не предполагает неявно, что , например, говоря «выберите произвольное » или предполагая, что набор из m элементов имеет элемент. ${\displaystyle P(m)}$ ${\displaystyle P(n)}$ ${\displaystyle n}$ ${\displaystyle m\geq 0}$ ${\displaystyle m=0}$ ${\displaystyle P(0)}$ ${\displaystyle P(n)}$ ${\displaystyle m=0}$ ${\displaystyle m>0}$ ${\displaystyle P(m)}$ ${\displaystyle m>0}$ ${\displaystyle n<m}$

Эквивалентность с обычной индукцией

Полная индукция эквивалентна обычной математической индукции, описанной выше, в том смысле, что доказательство одним методом может быть преобразовано в доказательство другим методом. Предположим, что имеется доказательство методом полной индукции. Затем это доказательство можно преобразовать в обычное индукционное доказательство, приняв более сильную индуктивную гипотезу. Пусть утверждение « справедливо для всех таких, что » — это становится индуктивной гипотезой для обычной индукции. Затем мы можем показать и только для предположения и показать, что подразумевает . ^[19] ${\displaystyle P(n)}$ ${\displaystyle Q(n)}$ ${\displaystyle P(m)}$ ${\displaystyle m}$ ${\displaystyle 0\leq m\leq n}$ ${\displaystyle Q(0)}$ ${\displaystyle Q(n+1)}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle Q(n)}$ ${\displaystyle Q(n)}$ ${\displaystyle P(n)}$

С другой стороны, если бы доказательство было доказано посредством обычной индукции, оно фактически уже было бы доказательством методом полной индукции: доказывается в базовом случае, без каких-либо предположений, и доказывается на этапе индукции, на котором можно предположить все более ранние случаи, но нужно использовать только случай . ${\displaystyle P(n)}$ ${\displaystyle P(0)}$ ${\displaystyle P(n+1)}$ ${\displaystyle P(n)}$

Пример: числа Фибоначчи

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

$${\displaystyle F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\varphi -\psi }}}$$

– nчисло Фибоначчи(сечениекорни ${\displaystyle F_{n}}$ ${\textstyle \varphi ={\frac {1}{2}}(1+{\sqrt {5}})}$ ${\textstyle \psi ={\frac {1}{2}}(1-{\sqrt {5}})}$ ${\displaystyle x^{2}-x-1}$ ${\displaystyle F_{n+2}=F_{n+1}+F_{n}}$ ${\displaystyle n\in \mathbb {N} }$ ${\textstyle F_{n+2}}$ ${\textstyle F_{n+1}}$ ${\textstyle F_{n}}$ ${\displaystyle n=0}$ ${\textstyle n=1}$

Пример: простая факторизация

Другое доказательство методом полной индукции более тщательно использует гипотезу о том, что это утверждение справедливо для всех меньших . Рассмотрим утверждение о том, что «каждое натуральное число больше 1 является произведением (одного или нескольких) простых чисел », которое является частью « существования » фундаментальной теоремы арифметики . Для доказательства шага индукции гипотеза индукции состоит в том, что для данного утверждения утверждение справедливо для всех меньших . Если является простым, то оно заведомо является произведением простых чисел, а если нет, то по определению это произведение: , где ни один из множителей не равен 1; следовательно, ни один из них не равен , и поэтому оба больше 1 и меньше . Гипотеза индукции теперь применима к и , поэтому каждое из них является произведением простых чисел. Таким образом , это произведение произведений простых чисел и, следовательно, само произведение простых чисел. ${\displaystyle n}$ ${\displaystyle n>1}$ ${\displaystyle n>1}$ ${\displaystyle m}$ ${\displaystyle m=n_{1}n_{2}}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle n_{1}}$ ${\displaystyle n_{2}}$ ${\displaystyle m}$

Пример: пересмотр долларовых сумм

Мы попытаемся доказать тот же пример, что и выше, на этот раз с помощью сильной индукции . Заявление остается прежним:

$${\displaystyle S(n):\,\,n\geq 12\implies \,\exists \,a,b\in \mathbb {N} .\,\,n=4a+5b}$$

Однако будут небольшие различия в структуре и предположениях доказательства, начиная с расширенного базового случая.

Доказательство.

Базовый случай: покажите, что справедливо для . ${\displaystyle S(k)}$ ${\displaystyle k=12,13,14,15}$

$${\displaystyle {\begin{aligned}4\cdot 3+5\cdot 0=12\\4\cdot 2+5\cdot 1=13\\4\cdot 1+5\cdot 2=14\\4\cdot 0+5\cdot 3=15\end{aligned}}}$$

Базовый случай сохраняется.

Шаг индукции: Учитывая некоторые , предположим, что справедливо для всех с . Докажите, что это так. ${\displaystyle j>15}$ ${\displaystyle S(m)}$ ${\displaystyle m}$ ${\displaystyle 12\leq m<j}$ ${\displaystyle S(j)}$

Выбор и наблюдение показывают, что это верно, по индуктивной гипотезе. То есть сумма может быть образована некоторой комбинацией долларовых монет. Затем простое добавление долларовой монеты к этой комбинации дает сумму . То есть имеет место ^[20] КЭД ${\displaystyle m=j-4}$ ${\displaystyle 15<j\implies 12\leq j-4<j}$ ${\displaystyle S(j-4)}$ ${\displaystyle j-4}$ ${\displaystyle 4}$ ${\displaystyle 5}$ ${\displaystyle 4}$ ${\displaystyle j}$ ${\displaystyle S(j)}$

Индукция вперед-назад

Иногда удобнее сделать обратный вывод, доказав утверждение для , учитывая его справедливость для . Однако доказательства достоверности утверждения ни для одного числа недостаточно, чтобы установить базовый случай; вместо этого нужно доказать утверждение для бесконечного подмножества натуральных чисел. Например, Огюстен Луи Коши сначала использовал прямую (регулярную) индукцию, чтобы доказать неравенство средних арифметических и геометрических для всех степеней 2 , а затем использовал обратную индукцию, чтобы показать это для всех натуральных чисел. ^{[21] [22]} ${\displaystyle n-1}$ ${\displaystyle n}$

Пример ошибки на этапе индукции

Шаг индукции необходимо доказать для всех значений n . Чтобы проиллюстрировать это, Джоэл Э. Коэн предложил следующий аргумент, целью которого является доказать с помощью математической индукции, что все лошади одного цвета : ^[23]

Базовый вариант: в наборе всего одна лошадь, только один окрас.

Шаг индукции: в качестве гипотезы индукции предположим, что в любой группе лошадей есть только одна масть. Теперь посмотрите на любую группу лошадей. Пронумеруйте их: . Рассмотрим множества и . Каждый представляет собой набор только лошадей, поэтому внутри каждого только один цвет. Но эти два набора пересекаются, поэтому среди всех лошадей должна быть только одна масть . ${\displaystyle n}$ ${\displaystyle n+1}$ ${\displaystyle 1,2,3,\dotsc ,n,n+1}$ ${\textstyle \left\{1,2,3,\dotsc ,n\right\}}$ ${\textstyle \left\{2,3,4,\dotsc ,n+1\right\}}$ ${\displaystyle n}$ ${\displaystyle n+1}$

Базовый случай тривиален, и шаг индукции верен во всех случаях . Однако аргумент, используемый на этапе индукции, неверен для , поскольку утверждение о том, что «два множества перекрываются», неверно для и . ${\displaystyle n=1}$ ${\displaystyle n>1}$ ${\displaystyle n+1=2}$ ${\textstyle \left\{1\right\}}$ ${\textstyle \left\{2\right\}}$

Формализация

В логике второго порядка « аксиому индукции» можно записать следующим образом:

$${\displaystyle \forall P\,{\Bigl (}P(0)\land \forall k{\bigl (}P(k)\to P(k+1){\bigr )}\to \forall n\,{\bigl (}P(n){\bigr )}{\Bigr )},}$$

P (·)knнатуральных чисел

Другими словами, базовый случай P (0) и шаг индукции (а именно, что из гипотезы индукции P ( k ) следует P ( k + 1) ) вместе подразумевают, что P ( n ) для любого натурального числа n . Аксиома индукции утверждает справедливость вывода о том, что P ( n ) выполняется для любого натурального числа n из базового случая и шага индукции.

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

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

1. 0 – натуральное число.
2. Функция-преемник s каждого натурального числа дает натуральное число ( s ( x ) = x + 1) .
3. Функция-преемник инъективна .
4. 0 не находится в диапазоне s .

В теории множеств ZFC первого порядка количественная оценка предикатов не допускается, но все же можно выразить индукцию путем количественной оценки множеств:

$${\displaystyle \forall A{\Bigl (}0\in A\land \forall k\in \mathbb {N} {\bigl (}k\in A\to (k+1)\in A{\bigr )}\to \mathbb {N} \subseteq A{\Bigr )}}$$

A

Трансфинитная индукция

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

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

1. Покажите для каждого порядкового числа n , что если P ( m ) выполняется для всех m < n , то P ( n ) также выполняется.

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

Доказательства методом трансфинитной индукции обычно различают три случая:

1. когда n — минимальный элемент, т.е. нет элемента меньше n ;
2. когда n имеет прямого предшественника, т.е. набор элементов, меньших n , имеет наибольший элемент;
3. когда n не имеет прямого предшественника, т. е. n является так называемым предельным порядковым номером .

Строго говоря, при трансфинитной индукции нет необходимости доказывать базовый случай, потому что это пустой частный случай утверждения, что если P истинно для всех n < m , то P истинно для m . Это абсурдно верно именно потому, что не существует значений n < m , которые могли бы служить контрпримерами. Таким образом, частные случаи являются частными случаями общего случая.

Связь с принципом упорядоченности

Принцип математической индукции обычно формулируется как аксиома натуральных чисел; см. аксиомы Пеано . Он строго сильнее принципа хорошего порядка в контексте других аксиом Пеано. Предположим следующее:

• Аксиома трихотомии : для любых натуральных чисел n и m n меньше или равно m тогда и только тогда, когда m не меньше n .
• Для любого натурального числа n n + 1 больше n .
• Для любого натурального числа n ни одно натуральное число не находится между n и n + 1 .
• Никакое натуральное число не меньше нуля.

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

Доказательство. Предположим, что существует непустое множество S натуральных чисел, не имеющее наименьшего элемента. Пусть P ( n ) — утверждение, что n не принадлежит S. Тогда P (0) истинно, поскольку если бы оно было ложным, то 0 был бы наименьшим элементом S . Более того, пусть n — натуральное число и предположим, что P ( m ) верно для всех натуральных чисел m меньше n + 1 . Тогда, если P ( n + 1) ложно, n + 1 находится в S и, таким образом, является минимальным элементом в S , противоречие. Таким образом, P ( n + 1) истинно. Следовательно, по принципу полной индукции P ( n ) выполняется для всех натуральных чисел n ; поэтому S пусто, противоречие. КЭД

« Числовая линия » для множества {(0, n ): n ∈ N } ∪ {(1, n ): n ∈ N } . Числа относятся ко второму компоненту пар; первое можно получить по цвету или местоположению.

С другой стороны, множество , показанное на рисунке, вполне упорядочено ^{[24] :35lf} по лексикографическому порядку . Более того, за исключением аксиомы индукции, он удовлетворяет всем аксиомам Пеано, где константа Пеано 0 интерпретируется как пара (0, 0), а функция- преемник Пеано определяется на парах по формуле succ( x , n ) = ( x , n + 1) для всех и . В качестве примера нарушения аксиомы индукции определите предикат P ( x , n ) как ( x , n ) = (0, 0) или ( x , n ) = succ( y , m ) для некоторых и . Тогда базовый случай P (0, 0) тривиально верен, как и шаг индукции: если P ( x , n ) , то P (succ( x , n ) ) . Однако P не верно для всех пар в наборе. ${\displaystyle \{(0,n):n\in \mathbb {N} \}\cup \{(1,n):n\in \mathbb {N} \}}$ ${\displaystyle x\in \{0,1\}}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle y\in \{0,1\}}$ ${\displaystyle m\in \mathbb {N} }$

Аксиомы Пеано с принципом индукции однозначно моделируют натуральные числа. Замена принципа индукции принципом хорошего порядка позволяет создавать более экзотические модели, удовлетворяющие всем аксиомам. ^[24]

^{В ряде книг [24]} и источниках ошибочно напечатано , что принцип хорошего порядка эквивалентен аксиоме индукции. В контексте других аксиом Пеано это не так, но в контексте других аксиом они эквивалентны; ^{В [24]} в частности, принцип хорошего порядка подразумевает аксиому индукции в контексте первых двух перечисленных выше аксиом и

• Каждое натуральное число равно либо 0, либо n + 1 для некоторого натурального числа n .

Распространенной ошибкой во многих ошибочных доказательствах является предположение, что n - 1 - уникальное и четко определенное натуральное число - свойство, которое не подразумевается другими аксиомами Пеано. ^[24]

Смотрите также

• Комбинаторное доказательство
• Индукционные головоломки
• Доказательство исчерпанием
• Рекурсия
• Рекурсия (информатика)
• Структурная индукция
• Трансфинитная индукция

Примечания

1. Мэтт ДеВос, математическая индукция, Университет Саймона Фрейзера
2. Херардо кон Диас, Математическая индукция. Архивировано 2 мая 2013 г. в Wayback Machine , Гарвардский университет.
3. Андерсон, Роберт Б. (1979). Доказательство правильности программ . Нью-Йорк: Джон Уайли и сыновья. п. 1. ISBN 978-0471033950.
4. Субер, Питер. «Математическая индукция». Эрлхемский колледж. Архивировано из оригинала 24 мая 2011 года . Проверено 26 марта 2011 г.
5. Ачерби 2000.
6. Рашед 1994, стр. 62–84.
7. Математические знания и взаимодействие практик «Самое раннее неявное доказательство методом математической индукции было дано около 1000 г. в работе персидского математика Аль-Караджи»
8. Кац (1998), с. 255
9. Каджори (1918), с. 197: «Процесс рассуждения, называемый «математической индукцией», имел несколько независимых источников. Оно восходит к швейцарцу Якобу (Джеймсу) Бернулли, французам Б. Паскалю и П. Ферма, итальянцу Ф. Мауролику. [...] Прочитав немного между строк, можно найти следы математической индукции еще раньше, в трудах индусов и греков, как, например, в «циклическом методе» Бхаскары и в доказательстве Евклида. что число простых чисел бесконечно».
10. Рашед 1994, с. 62.
11. Симонсон 2000.
12. Рабинович 1970.
13. «Иногда требуется доказать теорему, которая будет истинной всякий раз, когда определенная величина n , в которую она входит, будет целым или целым числом, и метод доказательства обычно бывает следующего типа. 1-е . Верность теоремы доказана когда n = 1. Во -вторых . Доказано, что если теорема верна, когда n — заданное целое число, она будет верной, если n — следующее большее целое число. Следовательно, теорема верна универсально.… Этот вид аргументов может быть называется продолжающимся соритом » (Бул, ок. 1849 г., « Элементарный трактат по логике, а не математике», стр. 40–41, перепечатано в Grattan-Guinness, Ivor and Bornet, Gérard (1997), Джордж Буль: Избранные рукописи по логике и ее философии , Birkhäuser Verlag, Берлин, ISBN 3-7643-5456-9 ) 
14. Пирс 1881.
15. Шилдс 1997.
16. Тед Сандстром, Математическое рассуждение , с. 190, Пирсон, 2006, ISBN 978-0131877184. 
17. Смуллян, Раймонд (2014). Руководство для начинающих по математической логике . Дувр. п. 41. ИСБН 0486492370.
18. Басс, Сэмюэл (1986). Ограниченная арифметика . Неаполь: Библиополис.
19. «Доказательство: сильная индукция эквивалентна слабой индукции» . Cornell University . Проверено 4 мая 2023 г.
20. . Шафии, Нилуфар. «Сильная индукция и хороший порядок» (PDF) . Йоркский университет . Проверено 28 мая 2023 г.
21. "Индукция вперед-назад | Блестящая математическая и научная вики" . блестящий.орг . Проверено 23 октября 2019 г.
22. Коши, Огюстен-Луи (1821). Cours d'analyse de l'École Royale Polytechnique, première party, Analysis Algébrique, Архивировано 14 октября 2017 года в Wayback Machine Paris. Доказательство неравенства средних арифметических и средних геометрических можно найти на стр. 457 и далее.
23. Коэн, Джоэл Э. (1961). «О природе математического доказательства». Опус .. Перепечатано в книге «Случайная прогулка по науке» (редактор Р.Л. Вебер), Crane, Russak & Co., 1973.
24. Оман, Ларс-Дэниел (6 мая 2019 г.). «Эквивалентны ли индукция и хороший порядок?». Математический интеллект . 41 (3): 33–40. дои : 10.1007/s00283-019-09898-4 .

Рекомендации

Введение

• Франклин, Дж .; Дауд, А. (2011). Доказательство по математике: Введение. Сидней: Книги Кью. ISBN 978-0-646-54509-7.(Гл. 8.)
• «Математическая индукция». Энциклопедия математики . ЭМС Пресс . 2001 [1994].
• Гермес, Ганс (1973). Введение в математическую логику . Hochschultext. Лондон: Спрингер. ISBN 978-3540058199. ISSN  1431-4657. МР  0345788.
• Кнут, Дональд Э. (1997). Искусство компьютерного программирования, Том 1: Фундаментальные алгоритмы (3-е изд.). Аддисон-Уэсли. ISBN 978-0-201-89683-1.(Раздел 1.2.1: Математическая индукция, стр. 11–21.)
• Колмогоров Андрей Н. ; Фомин, Сергей В. (1975). Вводный реальный анализ. Сильверман, Р.А. (пер., ред.). Нью-Йорк: Дувр. ISBN 978-0-486-61226-3.(Раздел 3.8: Трансфинитная индукция, стр. 28–29.)

История

• Ачерби, Фабио (август 2000 г.). «Платон: Парменид 149a7-c3. Доказательство путем полной индукции?». Архив истории точных наук . 55 (1): 57–76. дои : 10.1007/s004070000020. JSTOR  41134098. S2CID  123045154.
• Басси, штат Вашингтон (1917). «Происхождение математической индукции». Американский математический ежемесячник . 24 (5): 199–207. дои : 10.2307/2974308. JSTOR  2974308.
• Каджори, Флориан (1918). «Происхождение названия «Математическая индукция»". The American Mathematical Monthly . 25 (5): 197–201. doi : 10.2307/2972638. JSTOR  2972638.
• Фаулер, Д. (1994). «Могли ли греки использовать математическую индукцию? Использовали ли они ее?». Физика . 31 : 253–265.
• Фрейденталь, Ганс (1953). «Zur Geschichte der vollständigen Induction». Международные архивы истории наук . 6 : 17–37.
• Кац, Виктор Дж. (1998). История математики: Введение . Аддисон-Уэсли . ISBN 0-321-01618-1.
• Пирс, Чарльз Сандерс (1881). «О логике числа». Американский журнал математики . 4 (1–4): 85–95. дои : 10.2307/2369151. JSTOR  2369151. MR  1507856.Перепечатано (CP 3.252–288), (W 4:299–309).
• Рабинович, Нахум Л. (1970). «Раввин Леви Бен Гершон и истоки математической индукции». Архив истории точных наук . 6 (3): 237–248. дои : 10.1007/BF00327237. MR  1554128. S2CID  119948133.
• Рашид, Рошди (1972). «Математическая индукция: аль-Караджи, ас-Самаваль». Архив истории точных наук (на французском языке). 9 (1): 1–21. дои : 10.1007/BF00348537. MR  1554160. S2CID  124040444.
• Рашид, Р. (1994). «Математическая индукция: аль-Караджи и аль-Самаваль». Развитие арабской математики: между арифметикой и алгеброй. Бостонские исследования в области философии науки. Том. 156. Springer Science & Business Media. ISBN 9780792325659.
• Шилдс, Пол (1997). «Аксиоматизация арифметики Пирса». В Хаузере, Натан; Робертс, Дон Д.; Эвра, Джеймс Ван (ред.). Исследования по логике Чарльза С. Пирса . Издательство Университета Индианы. стр. 43–52. ISBN 0-253-33020-3. МР  1720827.
• Симонсон, Чарльз Г. (зима 2000 г.). «Математика Леви бен Гершона, Ралбага» (PDF) . Бехол Дерахеха Даеху . Издательство Университета Бар-Илан. 10 :5–21.
• Унгуру, С. (1991). «Греческая математика и математическая индукция». Физика . 28 : 273–289.
• Унгуру, С. (1994). «Детская охота после индукции». Физика . 31 : 267–272.
• Вакка, Г. (1909). «Мавролик, первый открыватель принципа математической индукции». Бюллетень Американского математического общества . 16 (2): 70–73. дои : 10.1090/S0002-9904-1909-01860-9 . МР  1558845.
• Ядегари, Мохаммад (1978). «Использование математической индукции Абу Камилем Шуджой ибн Асламом (850–930)». Исида . 69 (2): 259–262. дои : 10.1086/352009. JSTOR  230435. S2CID  144112534.