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

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

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

Если первый человек в очереди — женщина, и за каждой женщиной стоит женщина, то все в очереди — женщины.

Рассуждение, заключенное в этом шуточном примере, часто встречается в самых разных областях математики и носит название принципа математической индукции. Более серьезная формулировка этого принципа такова:

Имеется последовательность утверждений. Если первое утверждение верно, и за каждым верным утверждением следует верное, то все утверждения в последовательности верны.

Пример 1. Пусть нужно доказать формулу $1+2+3+.....+n= \frac {n(n+1)}{2}$ .

Эта формула содержит целую последовательность утверждений:

1) $\ 1= \frac {1\cdot 2}{2}$ ;

2) $\ 1+2= \frac {2\cdot 3}{2}$ ;

3) $\ 1+2 + 3= \frac {3\cdot 4}{2}$ ;

4) $\ 1+2 + 3 + 4 = \frac {4\cdot 5}{2}$ ;

$\ ............................$

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

Пусть утверждение k) верно, то есть равенство $\ 1+2 + 3 + 4 + ....+k= \frac {k\cdot (k+1)}{2}$ справедливо.

Теперь прибавим к обеим частям равенства число $\ (k+1)$ . Получим

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

Но это как раз и есть утверждение $k+1)$ , которое следует за утверждением $k)$ .

Мы доказали, таким образом, что за каждым верным утверждением следует верное. В силу принципа математической индукции, наша формула верна при любом $k$ .

Эту же задачу можно решить и без использования метода математической индукции. обозначим сумму, которую мы хотим найти, через $\ u_n$ . Напишем два равенства

$\ u_n = 1+ 2 + 3 + ....+ (n-2) + (n-1) + n,$

$\ u_n = n + (n-1) + (n-2) + .....+ 3 + 2 + 1$

(в нижней строке написана та же сумма, что и в первой, но записанная в обратном порядке). Если сложим почленно строки, то получим

$\ 2u_n = \underbrace {(n+1)+(n+1) + \cdots+(n+1) + (n+1)}_{n} = n(n+1)$

$\ u_n = \frac {n(n+1)}{2}$ ,

и наше равенство доказано.

Приведем еще одну формулировку принципа математической индукции, немного отличную от первой.

Пусть имеется какое-нибудь предположение, или, как еще говорят, гипотеза, и мы хотим проверить справедливость этой гипотезы для всех натуральных $n$ .

Допустим, что удалось доказать такие два утверждения:

а) Наша гипотеза справедлива при $n=1$ .

б) Из того, что эта гипотеза верна при $n=k$ , где $k$ — произвольное натуральное число, следует, что она верна и при $n = k+1$ .

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

Утверждение б) носит условный характер. В нем не утверждается, что гипотеза верна для $n = k+1$ . Оно состоит лишь в том, что если наша гипотеза верна, для $n=k$ , то она верна и для $n = k+1$ .

Мы будем называть б) индуктивным предположением.

Пример. Докажем, что для любого натурального $n$ число $n^5 -n$ делится на $5$ .

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

а) При $n=1$ выражение $n^5 -n$ равно нулю и, значит, делится на $5$ .

б) Пусть $k$ — произвольное натуральное число. Покажем, что если при $n=k$ число $n^5 -n$ делится на $5$ , то $(k+1)^5 -(k+1)$ тоже делится на $5$ .

Используя равенство

$\ (k+1)^5 = k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1$ ,

представим число $(k+1)^5 - (k+1)$ в виде

$\ (k+1)^5 - (k+1) = (k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1) - (k+1) = (k^5 - k) + 5(k^4 + 2k^3 + 2k^2 + k)$ .

Мы представили число $(k+1)^5 - (k+1)$ в виде суммы двух слагаемых. Первое их них, $(k^5 - k)$ , делится на 5 по нашему предположению. Второе слагаемое $5(k^4 + 2k^3 + 2k^2 + k)$ , также делится на 5. Сумма двух чисел делится на 5, так как каждое слагаемое делится на 5, т.е. $(k+1)^5 -(k+1)$ делится на 5.

Итак, утверждения а) и б) доказаны. Значит, по принципу математической индукции число $n^5 -n$ делится на 5 при всех натуральных $n$ .

Существуют другие формулировки принципа математической индукции, эквивалентные данным нами. Вот одна из них:

Если:

а) некоторое утверждение верно при $n = 1$ ;

б) из того, что оно верно для всех $n \leq {k}$ , следует, что оно верно и для $n=k+1$ , то это утверждение верно для всех $n$ .

Отличие этой формулировки от предыдущей состоит в следующем.

В пункте б) мы требуем, чтобы наше утверждение было справедливо для всех $n \leq {k}$ , а не только для $n=k$ .

Легко сообразить, что обе формулировки принципа математической индукции эквивалентны в том смысле, что всякая теорема, которую можно доказать, применяя метод индукции в одной форме, может быть доказана и с помощью другой его формы.

Заметим также, что доказательство утверждения а) нужно, так сказать, лишь для «затравки». Если вместо него доказать утверждение

а’) о том, что наша гипотеза справедлива, скажем, для $n=8$ , а пункт б) оставить неизменным, то из утверждений а’) и б) будет следовать, что наша гипотеза верна для всех натуральных $n$ , начиная с восьми.

Метод математической индукции позволит нам более основательно познакомиться с арифметической и геометрической прогрессией, выводом многих формул. Также метод математической индукции часто встречается при решении олимпиадных задач.

5 комментариев для “Метод математической индукции”

Виктор:

в 06:43

Любовь, день добрый! Заглянул на огонек! Улучшения налицо, но есть что то еще… Пишите на почту.

Ответить
Марина Седова:

в 18:11

Любовь, добрый день. У Вас информативный сайт. У меня сайт также связан с некоторым объемом учебных материалов, и в связи с этим возникает проблема антиплагиата по общепринятым формулировкам. Как Вы с этим справляетесь?

Ответить
1. Любовь Николаевна:
  
  в 09:44
  
  Здравствуйте Марина! Наверное, ничего с этим не поделать. Так и будет. Определения ничем не заменить. А также много терминов.
  
  Ответить
Дина:

в 10:09

Любовь! На вашем сайте я оказалась чисто по меркантильным соображениям, надо было по плану сделать 20 комментариев , думала тема не моя, о чем я буду писать. Но , удивительно, статья так меня зацепила, что непременно буду заходить к Вам в гости, т.е. на сайт! А говорят математика сухая наука!

Ответить
1. Любовь Николаевна:
  
  в 04:52
  
  Спасибо, Дина! Успехов вам!
  
  Ответить