§ 6. Метод математической индукции
В различных разделах современной математики широко используется метод доказательства, который называется методом математической индукции. Обычно доказательство этим методом проводится так. Если надо доказать, что некоторое утверждение
справедливо для всякого натурального числа
то доказывают
справедливость утверждения
для 1 и затем, предположив, что оно справедливо для произвольно выбранного натурального числа
доказывают справедливость его и для числа
После этого считают утверждение
справедливым для всякого натурального числа
То, что при выполнении указанных условий утверждение
действительно справедливо для всякого натурального числа
вытекает из аксиомы индукции, которую иначе еще называют принципом математической индукции: всякое множество натуральных чисел, содержащее 1, которое вместе со всяким его числом
содержит следующее число
совпадает с множеством всех натуральных чисел.
Действительно, пусть
множество тех натуральных чисел, для каждого из которых справедливо утверждение
Тогда 1 содержится в
так как для 1 утверждение
справедливо. Кроме того, из предположения, что
содержится в
вытекает, что и
содержится в
ибо если утверждение
справедливо для числа
то оно в силу доказательства справедливо и для числа
Поэтому в силу принципа математической индукции в
содержатся все натуральные числа, и, следовательно, утверждение
справедливо для всякого натурального числа