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

В основе метода математической индукции лежит следующий принцип.

Некоторое утверждение верно при любом натуральном n, если;

1) оно верно при n = 1

и

2) из справедливости, этого утверждения при каком-либо произвольном значении n = k (k >1 ) следует, что оно верно и при n = k + 1.

Действительно, при n = 1 утверждение верно в силу 1). Далее, 2 = 1 + 1, а потому в силу 2) утверждение верно при n = 2; 3 = 2+1, поэтому в силу 2) утверждение верно и при n = 3. Вообще, любое натуральное число n может быть получено из 1 путем последовательного прибавления к нему единицы n - 1 раз. При каждом таком прибавлении мы получаем натуральное число, для которого рассматриваемое утверждение верно. Поэтому оно верно и для натурального числа n.

Метод доказательства, основанный на использовании этого принципа, называется методом математической индукции.

Рассмотрим несколько примеров.

Пример 1. Найти сумму

$$ S_n=\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4} \cdots +\frac{1}{n(n+1)} $$

Сначала найдем суммы одного, двух, трех и четырех слагаемых. Имеем:

$$ S_1 =\frac{1}{1\cdot 2}=\frac{1}{2}; \\ S_2 =\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}=\frac{1}{2}+\frac{1}{6}=\frac{2}{3}; \\ S_3 =\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4}=\frac{2}{3}+\frac{1}{12}=\frac{3}{4}; \\ S_4=\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4}+\frac{1}{4\cdot 5}=\frac{3}{4}+\frac{1}{20}=\frac{4}{5}$$

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

$$ S_n=\frac{n}{n+1} $$

Для проверки этой гипотезы воспользуемся методом математической индукции.

1) При n = 1 гипотеза верна, так как \( S_1 =\frac{1}{1\cdot 2}=\frac{1}{2} \)

2) Предположим, что гипотеза верна при n = k то есть

$$ S_k=\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4} \cdots +\frac{1}{k(k+1)}=\frac{k}{k+1} $$

Докажем, что тогда гипотеза должна быть верной и при n = k + 1, то есть

$$ S_{k+1}=\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\cdots +\frac{1}{k(k+1)}+\frac{1}{(k+1)(k+2)}=\frac{k+1}{k+2} $$ Действительно $$ S_{k+1}=S_k+\frac{1}{(k+1)(k+2)} $$ Но по предположению \( S_k=\frac{k}{k+1}\), поэтому $$ S_{k+1}=\frac{k}{k+1}+\frac{1}{(k+1)(k+2)} =\\= \frac{k^2+2k+1}{(k+1)(k+2)}=\frac{(k+1)^2}{(k+1)(k+2)}=\frac{k+1}{k+2} $$

Таким образом, исходя из предположения, что гипотеза \(S_n=\frac{n}{n+1}\), верна при n = k , мы доказали, что она верна и при n = к + 1. Поэтому формула

$$ S_n=\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4} \cdots +\frac{1}{n(n+1)}+\frac{n}{n+1} $$

верна при любом натуральном n.

Пример 2. Доказать, что n-й член арифметической прогрессии равен

a_n = a₁+ (n - 1)d, (1)

где a₁ - первый член, a d - разность этой прогрессии.

Этот пример отличается от предыдущего тем, что строить гипотезу здесь не надо, она дана. Нужно только доказать, что эта гипотеза верна.

Доказательство будем вести методом математической индукции.

1) При n = 1 формула (1) имеет вид:

a₁ = a₁

так что при n = 1 эта формула верна.

2) Предположим, что она верна при n = k, то есть

a_k = a₁+ (k - 1)d,

и покажем, что в таком случае она должна быть верной и при n = k + 1, то есть

a_k+1 = a₁+ kd.

Действительно,

a_k+1 = a_k + d = [a₁+ (k - 1)d] + d = a₁+ kd,

что и требовалось доказать.

Оба условия принципа математической индукции выполняются, и потому формула (1) верна для любого натурального числа n.

Пример 3. Доказать тождество

(cos α + i sin α)ⁿ = cos nα + i sin nα. (2)

1) При n = 1 обе части формулы (2) принимают один и тот же вид, cos α + i sin α, так что при n = 1 эта формула верна.

2) Пусть она верна при n = k, то есть

(cos α + i sin α)^k = cos kα + i sin kα.

Тогда

(cos α + i sin α)^k+1 = (cos α + i sin α)^k • (cos α + i sin α) =

= (cos kα + i sin kα) (cos α + i sin α) =

= (cos kα cos α - sin kα sin α) + i (cos kα sin α + sin kα cos α) =

= cos (kα + α) + i sin (kα + α) = cos (k + l)α + i sin (k + l)α.

Но это означает, что формула (2) верна и при n = k + 1.

Оба условия принципа математической индукции выполняются, и потому формула (2) верна при любом натуральном n.

Пример 4. Доказать, что при любом натуральном n*

* Если х =/= 0; случай, когда х = 0, требует, строго говоря, специального рассмотрения.

(х^п)’ = nх^п-1 (3)

1) При n = 1 формула (3) принимает вид: х’ = 1.

Это соотношение, как было доказано в главе X, верно. Значит, при n = 1 формула (3) верна.

2) Предположим, что она верна при n = k, то есть (х^k)’ = kх^k-1, и, исходя из этого, докажем, что она должна быть верна и при n = k + 1, то есть (х^k+1)’ = (k +1)х^k . Действительно, представляя х^k+1 в виде х^k • х и используя правило дифференцирования произведения, получаем:

(х^k+1)’ = (х^k • х)’ = (х^k)’ х + х^k • (х)’.

Но по предположению (х^k)’ = kх^k-1, к тому же х’= 1. Поэтому

(х^k+1)’ = kх^k-1 • х + х^k •1 = (k + 1) х^k.

Итак, оба условия принципа математической индукции выполняются, и потому формула (3) верна при любом натуральном n.