Принцип математической индукции.

Аксиома математической индукции является основой метода доказательства по индукции. Доказательство по индукции применимо, когда хотят доказать, что какой-нибудь одноместный предикат с натуральной свободной переменной (одноместное условие) истинен для всех натуральных чисел.

ТЕОРЕМА 1.1. Пусть — любой одноместный предикат на множестве N натуральных чисел, удовлетворяющий условиям: (а) А (0) истинно (0 удовлетворяет предикату ); (Р) для каждого из N, если истинно, то истинно Тогда истинно для любого натурального .

Доказательство. Пусть . В силу (а) и (Р) выполняются условия: (а) для любого из N, если то . По аксиоме VII отсюда следует, что Последнее равенство означает, что любое натуральное число удовлетворяет условию .

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

или в виде

Основные этапы доказательства по индукции: 1) доказывается, что 0 удовлетворяет условию ; 2) доказывается, что для всякого из следует Переменную я называют переменной, по которой производится индукция. Часть доказательства «верно, что называется началом индукции или базисом индукции. Вторая часть доказательства «для любого из следует называется индукционным шагом. Посылка называется индуктивным предположением.

Для доказательства утверждения

берут произвольное натуральное число, обозначают его какой-нибудь буквой, например k, и доказывают импликацию обычным путем: предполагают, что истинно (индуктивное предположение), и показывают, что тогда истинно