Принцип математической индукции заключается в следующем: 1

Пусть имеется какое-либо утверждение, зависящее от натурального числа n, являющееся истинным при начальном n = 1. 1 Если предположить справедливость утверждения для произвольного натурального номера n = k и из него получить истинность при натуральном n = k + 1, то данное утверждение верно для всех натуральных чисел n. 1

Доказательство с помощью метода математической индукции проводится в два этапа: 2

1. База индукции (базис индукции). 2 Проверяется истинность утверждения при n = 1 (или любом другом подходящем значении n). 2
2. Индуктивный переход (шаг индукции). 2 Считая, что справедливо утверждение P(k) при n = k, проверяется истинность утверждения P(k+1) при n = k+1. 2