Глава 1. Элементы теории чисел § 1. Метод математической индукции

Глава 1. Элементы теории чисел

§ 1. Метод математической индукции

Пусть нужно доказать справедливость некоторого утверждения для любого натурального числа п (например, нужно доказать, что сумма первых п нечетных чисел равна n²). Непосредственная провер- ка этого утверждения для каждого значения п невозможна, поскольку множество натуральных чисел бесконечно. Чтобы доказать это ут-

верждение, проверяют сначала его справедливость для n 1 . Затем

доказывают, что из справедливости рассматриваемого утверждения

для n=k при любом k вытекает его справедливость для n То-

гда справедливость этого утверждения считается доказанной для всех значений п.

Описанный метод доказательства носит название метода ма- тематической индукции. Формулируется он в виде следующего прин- ципа.

А к с и о м а м а т е м а т и ч е с к о й и н д у к ц и и

а) утверждение справедливо для n 1;

б) из справедливости утверждения для n=k (при любом на- туральном значении k) вытекает его справедливость и для n

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

для n Эту часть доказательства называют базисом индукции. За-

тем следует часть доказательства, называемая индукционным шагом.

В этой части доказывают справедливость утверждения для n в

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

Приведем примеры доказательства методом математической ин- дукции.