Нехай А – множина натуральних чисел, яка має такі властивості:
1.
2. Якщо натуральне число k належить до А, то й наcтупне число належить до А.
Тоді до А належать всі натуральні числа.
Принцип математичної індукції (основна форма)
Якщо деяке твердження Т правильне для числа 1 і якщо із припущення, що воно правильне для натурального числа k, випливає його правильність і для наступного числа , то твердження Т правильне для будь-якого натурального числа n.
Доведення.
Дійсно, нехай А – множина всіх натуральних чисел, для кожного із яких твердження Т правильне. За умовою теореми , і якщо , то і наступне число . Отже, згідно аксіоми індукції множина А збігається з множиною всіх натуральних чисел. Таким чином, твердження Т виконується для будь-якого натурального числа.¨
Отже, щоб довести справедливість якогось твердження для довільного натурального числа п методом математичної індукції, треба:
1) довести, що це твердження справедливе для п=1;
2) припустивши справедливість даного твердження для n=k, довести його справедливість для
Іноді розглядуване твердження не має змісту, або неправильне при п=1, але стає справедливим при , або взагалі при . В цьому випадку використовується інша форма принципу математичної індукції.