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

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

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

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

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

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

Пример 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 комментариев для “Метод математической индукции”
  1. Любовь, день добрый! Заглянул на огонек! Улучшения налицо, но есть что то еще… Пишите на почту.

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

    1. Любовь Николаевна:

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

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

Добавить комментарий для Любовь Николаевна Отменить ответ

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.