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

      По своему первоначальному смыслу слово “индукция” применяется к
рассуждениям, при помощи которых получают общие выводы, опи-раясь на ряд
частных утверждений. Простейшим методом рассуждений такого рода является
пол-ная индукция. Вот пример подобного рассужде-ния.
      Пусть требуется установить, что каждое натуральное чётное число n в
пределах 4< n < 20
представимо в виде суммы двух простых чисел. Для этого возьмём все такие
числа и выпишем соответствующие разложения:
            4=2+2; 6=3+3; 8=5+3; 10=7+3; 12=7+5;
            14=7+7; 16=11+5; 18=13+5; 20=13+7.
      Эти девять равенств показывают, что каждое
из интересующих нас чисел действительно пред-
ставляется в виде суммы двух простых слагаемых.
      Таким образом, полная индукция заключает-
ся в том, что общее утверждение доказывается по отдельности    в каждом из
конечного числа возмож-
ных случаев.
      Иногда общий результат удаётся предугадать после рассмотрения не
всех, а достаточно большо-
го числа частных случаев (так называемая непол-
ная индукция).
      Результат, полученный неполной индукцией, остается, однако, лишь
гипотезой, пока он не до-
казан точным математическим рассуждением, охватывающим все частные случаи.
Иными сло-
вами, неполная индукция в математике не счита-
ется законным методом строгого доказательства,
но является мощным методом открытия новых ис-тин.
      Пусть, например, требуется найти сумму пер-
вых n последовательных нечётных чисел. Рас-
смотрим частные случаи:
            1=1=12
            1+3=4=22
            1+3+5=9=32
            1+3+5+7=16=42
            1+3+5+7+9=25=52
      После рассмотрения этих нескольких частных случаев напрашивается
следующий общий вывод:
            1+3+5+…+(2n-1)=n2
т.е. сумма n первых последовательных нечётных чисел равна n2
      Разумеется, сделанное наблюдение ещё не мо-
жет служить доказательством справедливости при-
ведённой формулы.
      Полная индукция имеет в математике лишь ог-
раниченное применение. Многие интересные мате-
матические утверждения охватывают бесконечное число частных случаев, а
провести проверку для бесконечного числа случаев мы не в состоянии.
Неполная же индукция часто приводит к ошибоч-
ным результатам.
      Во многих случаях выход из такого рода за-
труднений заключается в обращении к особому ме-
тоду рассуждений, называемому методом матема-
тической индукции. Он заключается в следующем.
      Пусть нужно доказать справедливость некото-
рого утверждения для любого натурального числа
n (например нужно доказать, что сумма первых n нечётных чисел равна n2).
Непосредственная про-верка этого утверждения для каждого значения n
невозможна, поскольку множество натуральных чисел бесконечно. Чтобы
доказать это утвержде-ние, проверяют сначала его справедливость для n=1.
Затем доказывают, что при любом натураль-ном значении k из справедливости
рассматрива-емого утверждения при n=k вытекает его справед-ливость и при
n=k+1.
      Тогда утверждение считается доказанным для всех n. В самом деле,
утверждение справедливо при n=1. Но тогда оно справедливо и для следую-щего
числа n=1+1=2. Из справедливости утвержде-ния для n=2 вытекает его
справедливость для n=2+
+1=3. Отсюда следует справедливость утвержде-ния для n=4 и т.д. Ясно, что,
в конце концов, мы дойдём до любого натурального числа n. Значит,
утверждение верно для любого n.
      Обобщая сказанное, сформулируем следую-щий общий принцип.
      Принцип математической индукции.
Если предложение А(n), зависящее от натураль-ного числа n, истинно для n=1
и из того, что оно истинно для n=k (где k-любое натуральное число),
следует, что оно истинно и для следующего числа n=k+1, то предположение
А(n) истинно для любо-го натурального числа n.
      В ряде случаев бывает нужно доказать спра-ведливость некоторого
утверждения не для всех натуральных чисел, а лишь для n>p, где p-фикси-
рованное натуральное число. В этом случае прин-цип математической индукции
формулируется сле-дующим образом.
      Если предложение А(n) истинно при  n=p  и если А(k)(А(k+1) для любого
k>p, то предложе-ние А(n) истинно для любого n>p.
      Доказательство по методу математической ин-дукции проводиться
следующим образом. Сначала доказываемое утверждение проверяется для n=1,
т.е. устанавливается истинность высказывания А(1). Эту часть доказательства
называют базисом индукции. Затем следует часть доказательства, на-зываемая
индукционным шагом. В этой части до-казывают справедливость утверждения для
n=k+1 в предположении справедливости утверждения для n=k (предположение
индукции), т.е. доказывают, что А(k)(A(k+1).



                                 ПРИМЕР 1

      Доказать, что 1+3+5+…+(2n-1)=n2. 
            Решение: 1) Имеем n=1=12. Следовательно,
утверждение верно при n=1, т.е. А(1) истинно.
                         2) Докажем, что А(k)(A(k+1).
Пусть k-любое натуральное число и пусть утверж-дение справедливо для n=k,
т.е.
            1+3+5+…+(2k-1)=k2.
      Докажем, что тогда утверждение справедливо и для следующего
натурального числа n=k+1, т.е. что
            1+3+5+…+(2k+1)=(k+1)2.
      В самом деле,
            1+3+5+…+(2k-1)+(2k+1)=k2+2k+1=(k+1)2.
      Итак, А(k)(А(k+1). На основании принципа математической индукции
заключаем, что предпо-ложение А(n) истинно для любого n(N.


                                 ПРИМЕР 2

      Доказать, что
            1+х+х2+х3+…+хn=(хn+1-1)/(х-1), где х(1
            Решение: 1) При n=1 получаем
            1+х=(х2-1)/(х-1)=(х-1)(х+1)/(х-1)=х+1
следовательно, при n=1 формула верна; А(1) ис-тинно.
                          2) Пусть k-любое натуральное число и пусть
формула верна при n=k, т.е.
            1+х+х2+х3+…+хk=(хk+1-1)/(х-1).

      Докажем, что тогда выполняется равенство

      1+х+х2+х3+…+хk+xk+1=(xk+2-1)/(х-1).
В самом деле
1+х+х2+x3+…+хk+xk+1=(1+x+x2+x3+…+xk)+xk+1=
=(xk+1-1)/(x-1)+xk+1=(xk+2-1)/(x-1).
      Итак, А(k)(A(k+1). На основании принципа математической индукции
заключаем, что форму-ла верна для любого натурального числа n.


                            ПРИМЕР 3


      Доказать, что число диагоналей выпуклого

n-угольника равно n(n-3)/2.
            Решение: 1) При n=3 утверждение спра-
                  А3                 ведливо, ибо в треугольнике
                    ?3=3(3-3)/2=0 диагоналей;
                                                        А2     А(3)
истинно.
                                                           2) Предположим,
что во всяком
                                    выпуклом k-угольнике имеет-

                           А1      ся ?k=k(k-3)/2 диагоналей.



  Аk
      Докажем, что тогда в выпуклом

           Аk+1                            (k+1)-угольнике число диаго-
                                     налей ?k+1=(k+1)(k-2)/2.
      Пусть А1А2А3…AkAk+1-выпуклый (k+1)-уголь-ник. Проведём в нём
диагональ A1Ak. Чтобы под-считать общее число диагоналей этого (k+1)-уголь-
ника  нужно  подсчитать  число  диагоналей  в  k-угольнике A1A2…Ak,
прибавить к полученному числу k-2, т.е. число диагоналей (k+1)-угольника,
исходящих из вершины Аk+1, и, кроме того, следует
учесть диагональ А1Аk.
      Таким образом,
      ?k+1=?k+(k-2)+1=k(k-3)/2+k-1=(k+1)(k-2)/2.
            Итак, А(k)(A(k+1). Вследствие принципа математической индукции
утверждение верно для любого выпуклого n-угольника.


                                  ПРИМЕР 4

      Доказать, что при любом n справедливо утвер-ждение:
            12+22+32+…+n2=n(n+1)(2n+1)/6.
            Решение: 1) Пусть n=1, тогда
            Х1=12=1(1+1)(2+1)/6=1.
        Значит, при n=1 утверждение верно.
                          2) Предположим, что n=k
            Хk=k2=k(k+1)(2k+1)/6.
                          3) Рассмотрим данное утвержде-ние при n=k+1
            Xk+1=(k+1)(k+2)(2k+3)/6.
       Xk+1=12+22+32+…+k2+(k+1)2=k(k+1)(2k+1)/6+
+(k+1)2=(k(k+1)(2k+1)+6(k+1)2)/6=(k+1)(k(2k+1)+
+6(k+1))/6=(k+1)(2k2+7k+6)/6=(k+1)(2(k+3/2)(k+
+2))/6=(k+1)(k+2)(2k+3)/6.
      Мы доказали справедливость равенства и при n=k+1, следовательно, в
силу метода математиче-ской индукции, утверждение верно для любого на-
турального n.



                                 ПРИМЕР 5

      Доказать, что для любого натурального n спра-ведливо равенство:
            13+23+33+…+n3=n2(n+1)2/4.
            Решение: 1) Пусть n=1.
      Тогда Х1=13=12(1+1)2/4=1.
Мы видим, что при n=1 утверждение верно.
                          2) Предположим, что равенство верно при n=k
            Xk=k2(k+1)2/4.
                          3) Докажем истинность этого ут-верждения для
n=k+1, т.е.
    Хk+1=(k+1)2(k+2)2/4.
Xk+1=13+23+…+k3+(k+1)3=k2(k+1)2/4+(k+1)3=(k2(k++1)2+4(k+1)3)/4=(k+1)2(k2+4k+
4)/4=(k+1)2(k+2)2/4.
      Из приведённого доказательства видно, что ут-верждение верно при
n=k+1, следовательно, равен-ство верно при любом натуральном n.


                            ПРИМЕР 6


      Доказать, что

    ((23+1)/(23-1))(((33+1)/(33-1))(…(((n3+1)/(n3-1))=
=3n(n+1)/2(n2+n+1), где n>2.
            Решение: 1) При n=2 тождество выглядит:      (23+1)/(23-
1)=(3(2(3)/2(22+2+1),
т.е. оно верно.
                        2) Предположим, что выражение верно при n=k
  (23+1)/(23-1)(…((k3+1)/(k3-1)=3k(k+1)/2(k2+k+1).
                          3) Докажем верность выражения при n=k+1.
      (((23+1)/(23-1))(…(((k3+1)/(k3-1)))((((k+1)3+
   +1)/((k+1)3-1))=(3k(k+1)/2(k2+k+1))(((k+2)((k+
   +1)2-(k+1)+1)/k((k+1)2+(k+1)+1))=3(k+1)(k+2)/2(
   (((k+1)2+(k+1)+1).
      Мы доказали справедливость равенства и при n=k+1, следовательно, в
силу метода математиче-ской индукции, утверждение верно для любого n>2


                            ПРИМЕР 7


      Доказать, что

            13-23+33-43+…+(2n-1)3-(2n)3=-n2(4n+3)
для любого натурального n.
            Решение: 1) Пусть n=1, тогда
            13-23=-13(4+3);       -7=-7.
                          2) Предположим, что n=k, тогда
            13-23+33-43+…+(2k-1)3-(2k)3=-k2(4k+3).
                          3) Докажем истинность этого ут-верждения при
n=k+1
(13-23+…+(2k-1)3-(2k)3)+(2k+1)3-(2k+2)3=-k2(4k+3)+
+(2k+1)3-(2k+2)3=-(k+1)3(4(k+1)+3).
            Доказана и справедливость равенства при n=k+1, следовательно
утверждение верно для лю-бого натурального n.



                            ПРИМЕР 8


      Доказать верность тождества

(12/1(3)+(22/3(5)+…+(n2/(2n-1)((2n+1))=
                                             =n(n+1)/2(2n+1)
для любого натурального n.
            Решение: 1) При n=1 тождество верно
      12/1(3=1(1+1)/2(2+1).
                          2) Предположим, что при n=k
(12/1(3)+…+(k2/(2k-1)((2k+1))=k(k+1)/2(2k+1).
                         3) Докажем, что тождество верно при n=k+1.
(12/1(3)+…+(k2/(2k-1)(2k+1))+(k+1)2/(2k+1)(2k+3)=
      =(k(k+1)/2(2k+1))+((k+1)2/(2k+1)(2k+3))=((k+
      +1)/(2k+1))(((k/2)+((k+1)/(2k+3)))=(k+1)(k+2)(
      ((2k+1)/2(2k+1)(2k+3)=(k+1)(k+2)/2(2(k+1)+1).
      Из приведённого доказательства видно, что ут-верждение верно при
любом натуральном n.


                            ПРИМЕР 9

      Доказать, что (11n+2+122n+1) делится на 133 без остатка.
            Решение: 1) Пусть n=1, тогда
      113+123=(11+12)(112-132+122)=23(133.
Но (23(133) делится на 133 без остатка, значит при n=1 утверждение верно;
А(1) истинно.
                        2) Предположим, что (11k+2+122k+1) делится на 133
без остатка.
                          3) Докажем, что в таком случае
(11k+3+122k+3) делится на 133 без остатка. В самом деле
11k+3+122л+3=11(11k+2+122(122k+1=11(11k+2+
+(11+133)(122k+1=11(11k+2+122k+1)+133(122k+1.
      Полученная сумма делится на 133 без остатка, так как первое её
слагаемое делится на 133 без ос-татка по предположению, а во втором одним
из множителей выступает 133. Итак, А(k)(А(k+1). В силу метода
математической индукции утвержде-ние доказано.


                           ПРИМЕР 10

      Доказать, что при любом n 7n-1 делится на 6 без остатка.
            Решение: 1) Пусть n=1, тогда Х1=71-1=6 де-лится на 6 без
остатка. Значит при n=1 утвержде-ние верно.
                         2) Предположим, что при n=k
      7k-1 делится на 6 без остатка.
                          3) Докажем, что утверждение справедливо для
n=k+1.
            Xk+1=7k+1-1=7(7k-7+6=7(7k-1)+6.
      Первое слагаемое делится на 6, поскольку 7k-1 делится на 6 по
предположению, а вторым слага-емым является 6. Значит 7n-1 кратно 6 при
любом натуральном n. В силу метода математической ин-дукции утверждение
доказано.



                            ПРИМЕР 11


      Доказать, что 33n-1+24n-3 при произвольном на-туральном n делится на
11.

            Решение: 1) Пусть n=1, тогда

      Х1=33-1+24-3=32+21=11 делится на 11 без остат-ка. Значит, при n=1
утверждение верно.
                          2) Предположим, что при n=k
      Xk=33k-1+24k-3 делится на 11 без остатка.
                          3) Докажем, что утверждение верно для n=k+1.
Xk+1=33(k+1)-1+24(k+1)-3=33k+2+24k+1=33(33k-1+24(24k-3=
=27(33k-1+16(24k-3=(16+11)(33k-1+16(24k-3=16(33k-1+
+11(33k-1+16(24k-3=16(33k-1+24k-3)+11(33k-1.
      Первое слагаемое делится на 11 без остатка, поскольку 33k-1+24k-3
делится на 11 по предположе-нию, второе делится на 11, потому что одним из
его множителей есть число 11. Значит и сумма де-лится на 11 без остатка при
любом натуральном n. В силу метода математической индукции утвер-ждение
доказано.


                            ПРИМЕР 12

      Доказать, что 112n-1 при произвольном нату-ральном n делится на 6 без
остатка.
            Решение: 1) Пусть n=1, тогда 112-1=120 делится на 6 без
остатка. Значит при n=1 утвержде-ние верно.

                          2) Предположим, что при n=k
      112k-1 делится на 6 без остатка.
                          3) Докажем, что утверждение верно при n=k+1
            112(k+1)-1=121(112k-1=120(112k+(112k-1).
      Оба слагаемых делятся на 6 без остатка: пер-вое содержит кратное 6-ти
число 120, а второе де-лится на 6 без остатка по предположению. Значит и
сумма делится на 6 без остатка. В силу метода математической индукции
утверждение доказано.


                            ПРИМЕР 13

      Доказать, что 33n+3-26n-27 при произвольном натуральном n делится на
262(676) без остатка.
            Решение: Предварительно докажем, что 33n+3-1 делится на 26 без
остатка.
                         1) При n=0
      33-1=26 делится на 26
                         2) Предположим, что при n=k
      33k+3-1 делится на 26
                         3) Докажем, что утверждение
верно при n=k+1.
33k+6-1=27(33k+3-1=26(33л+3+(33k+3-1) –делится на 26
            Теперь проведём доказательство утвер-ждения, сформулированного
в условии задачи.
                          1) Очевидно, что при n=1 утвер-ждение верно
            33+3-26-27=676
                          2) Предположим, что при n=k
выражение 33k+3-26k-27 делится на 262 без остатка.
                          3) Докажем, что утверждение верно при n=k+1
      33k+6-26(k+1)-27=26(33k+3-1)+(33k+3-26k-27).
      Оба слагаемых делятся на 262; первое делится на 262, потому что мы
доказали делимость на 26 выражения, стоящего в скобках, а второе делится по
предположению индукции. В силу метода мате-матической индукции утверждение
доказано.


                            ПРИМЕР 14

      Доказать, что если n>2 и х>0, то справедливо неравенство
                 (1+х)n>1+n(х.
            Решение: 1) При n=2 неравенство справед-ливо, так как
            (1+х)2=1+2х+х2>1+2х.
      Значит, А(2) истинно.
                          2) Докажем, что А(k)(A(k+1), если k> 2.
Предположим, что А(k) истинно, т.е., что справедливо неравенство
                 (1+х)k>1+k(x.         (3)
      Докажем, что тогда и А(k+1) истинно, т.е., что справедливо
неравенство
                 (1+x)k+1>1+(k+1)(x.
В самом деле, умножив обе части неравенства (3) на положительное число 1+х,
получим
                 (1+x)k+1>(1+k(x)(1+x).
      Рассмотрим правую часть последнего неравен-

ства; имеем
            (1+k(x)(1+x)=1+(k+1)(x+k(x2>1+(k+1)(x.
      В итоге получаем, что
                 (1+х)k+1>1+(k+1)(x.
      Итак, А(k)(A(k+1). На основании принципа математической индукции
можно утверждать, что неравенство Бернулли справедливо для любого
n> 2.


                            ПРИМЕР 15

      Доказать, что справедливо неравенство
      (1+a+a2)m> 1+m(a+(m(m+1)/2)(a2  при а> 0.
            Решение: 1) При m=1
      (1+а+а2)1> 1+а+(2/2)(а2    обе части равны.
                          2) Предположим, что при m=k
      (1+a+a2)k>1+k(a+(k(k+1)/2)(a2
                          3) Докажем, что при m=k+1 не-равенство верно
      (1+a+a2)k+1=(1+a+a2)(1+a+a2)k>(1+a+a2)(1+k(a+
     +(k(k+1)/2)(a2)=1+(k+1)(a+((k(k+1)/2)+k+1)(a2+
     +((k(k+1)/2)+k)(a3+(k(k+1)/2)(a4> 1+(k+1)(a+
     +((k+1)(k+2)/2)(a2.
      Мы доказали справедливость неравенства при m=k+1, следовательно, в
силу метода математиче-ской индукции, неравенство справедливо для лю-бого
натурального m.



                            ПРИМЕР 16


      Доказать, что при n>6 справедливо неравенство
                 3n>n(2n+1.
            Решение: Перепишем неравенство в виде
                 (3/2)n>2n.
                         1) При n=7 имеем
                 37/27=2187/128>14=2(7
      неравенство верно.
                         2) Предположим, что при n=k
                 (3/2)k>2k.
                          3) Докажем верность неравен-ства при n=k+1.
      3k+1/2k+1=(3k/2k)((3/2)>2k((3/2)=3k>2(k+1).
      Так как k>7, последнее неравенство очевидно.
В силу метода математической индукции неравен-ство справедливо для любого
натурального n.


                            ПРИМЕР 17

      Доказать, что при n>2 справедливо неравенство
            1+(1/22)+(1/32)+…+(1/n2)<1,7-(1/n).
            Решение: 1) При n=3 неравенство верно
      1+(1/22)+(1/32)=245/180<246/180=1,7-(1/3).
                        2) Предположим, что при n=k
           1+(1/22)+(1/32)+…+(1/k2)=1,7-(1/k).
                         3) Докажем справедливость не-
равенства при n=k+1
(1+(1/22)+…+(1/k2))+(1/(k+1)2)<1,7-(1/k)+(1/(k+1)2).
     Докажем, что 1,7-(1/k)+(1/(k+1)2)<1,7-(1/k+1)(
      ((1/(k+1)2)+(1/k+1)<1/k((k+2)/(k+1)2<1/k(
      (k(k+2)<(k+1)2(k2+2k
1  2  3  4  5  6