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

Рассмотрим на примере, как работает метод.

Задача. Доказать, что для всех натуральных n справедливо равенство

    \[{1\over 1\cdot2\cdot3}+{1\over 2\cdot3\cdot4}+\dots+{1\over n(n+1)(n+2)}= {n(n+3)\over 4(n+1)(n+2)}.\]

Решение. Обозначим через s_n левую часть равенства, а через z_n — его правую часть.

1) Докажем сначала, что s_1=z_1.

Доказательство.

    \[\begin{array}{l} \displaystyle s_1={1\over 1\cdot2\cdot3}={1\over 6}\\[3mm] \displaystyle z_1={1\cdot(1+3)\over 4\cdot(1+1)\cdot(1+2)}={1\cdot4\over 4\cdot2\cdot3}={1\over 6}. \end{array}\]

2) Дано: s_k=z_k. Нужно доказать: s_{k+1}=z_{k+1}.

Доказательство.

    \[\begin{array}{l} \displaystyle z_k={k(k+3)\over 4(k+1)(k+2)}; z_{k+1}={(k+1)(k+4)\over 4(k+2)(k+3)}\\[3mm] \displaystyle s_{k+1}=s_k+{1\over (k+1)(k+2)(k+3)}=z_k+{1\over (k+1)(k+2)(k+3)}=\\[3mm] \displaystyle ={k(k+3)\over 4(k+1)(k+2)}+{1\over (k+1)(k+2)(k+3)}={k(k+3)^2+4\over 4(k+1)(k+2)(k+3)}=\\[3mm] \displaystyle ={k^3+9k+6k^2+4\over 4(k+1)(k+2)(k+3)}\\[3mm] \displaystyle z_{k+1}={(k+1)^2(k+4)\over 4(k+1)(k+2)(k+3)}={k^3+6k^2+9k+4\over 4(k+1)(k+2)(k+3)}\\[3mm] s_{k+1}=z_{k+1}. \end{array}\]

Тем самым, утверждение доказано для любого n, поскольку из его истинности для n=1 следует, что оно истинно для n=2, из его истинности при n=2 следует его истинность для n=3 и т.д.

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

    \[T_1,T_2,\dots,T_n,\ldots\]

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

1. T_1 — верное утверждение.

2. Если для какого-либо натурального k верно утверждение T_k, то верно и утверждение T_{k+1}.

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

Теорема. Если последовательности (s_n) и (z_n) таковы, что s_1=z_1, и для любого натурального k

    \[s_{k+1}-s_k=z_{k+1}-z_k,\]

то для всех натуральных n выполняется равенство s_n=z_n.

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

Теорема. Если последовательности (s_n) и (z_n) таковы, что s_1>z_1, и для любого натурального k

    \[s_{k+1}-s_k>z_{k+1}-z_k,\]

то для всех натуральных n выполняется неравенство s_n>z_n.

Пример. Доказать, что для всех натуральных n\ge2

    \[{1\over 1^2}+{1\over 2^2}+{1\over 3^2}+\dots+{1\over n^2}<2-{1\over n}.\]

Доказательство.
1. s_2<z_2

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

    \[\left.\begin{array}{l} \displaystyle s_2=1+{1\over 4}={5\over 4}\\[3mm] \displaystyle z_2=2-{1\over 2}={3\over 2} \end{array}\right|\Longrightarrow s_2<z_2\]

2.

    \[\begin{array}{l} \displaystyle s_{k+1}-s_k={1\over (k+1)^2},\\[3mm] \displaystyle z_{k+1}-z_k=2-{1\over k+1}-\left(2-{1\over k}\right) ={1\over k}-{1\over k+1}={1\over k(k+1)},\\[3mm] s_{k+1}-s_k<z_{k+1}-z_k. \end{array}\]

Теорема. Если последовательности (s_n) и (z_n) с положительными членами таковы, что s_1>z_1, и для любого натурального k

    \[{s_{k+1}\over s_k}>{z_{k+1}\over z_k},\]

то для всех натуральных n выполняется неравенство s_n>z_n.

Задачи. Доказать

1. \displaystyle 1^2+2^2+\dots+n^2={n(n+1)(2n+1)\over 6}.

2. 1+2+2^2+\dots+2^{n-1}=2^n-1.

3. 2!\cdot4!\times\dots\times(2n)!>[(n+1)!]^n при n>1.

4. \displaystyle 1+{1\over \sqrt{2}}+{1\over \sqrt{3}}+\dots+{1\over \sqrt{n}}>\sqrt{n} при n\ge2.

5. Доказать, что сумма всевозможных произведений квадратов натуральных чисел, взятых по два (от 1 до n), равна

    \[\displaystyle {n(n^2-1)(4n^2-1)(5n+6)\over 360}.\]

6. Доказать, что для всех натуральных n

    \[\sqrt{\displaystyle\underbrace{4+\sqrt{4+\sqrt{4+\dots+\sqrt{4}}}}_{n}}<3\]

(четверок — n).

7. Доказать, что для всех натуральных n

    \[1^5+2^5+\dots+n^5={1\over 12}n^2(n+1)^2(2n^2+2n-1).\]

8. Доказать, что для всех натуральных n

    \[{1^2\over 1\cdot3}+{2^2\over 3\cdot5}+\dots+{n^2\over(2n-1)(2n+1)}={n(n+1)\over 2(2n+1)}.\]

9. Доказать, что для всех натуральных n \displaystyle2^{n-1}\cdot n!\le n^n.

10. Доказать, что сторона правильного вписанного в окружность 2^n-угольника выражается формулой

    \[a_{2^n}=R\sqrt{2-\sqrt{\displaystyle\underbrace{2+\sqrt{2+\dots+\sqrt{2}}}_{n-2}}},\]

где R — радиус этой окружности (двоек — n-2).

11. Доказать, что n прямых, пересекающихся в одной точке и лежащих в одной плоскости, делят эту плоскость на 2n частей.

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

13. Доказать, что если S_1,S_2,S_3,\dots,S_n — суммы n членов n геометрических прогрессий, у которых первые члены 1, а знаменатели соответственно равны 1,2,3,\dots,n, то

    \[S_1+S_2+2S_3+3S_4+\dots+(n-1)S_n=1^n+2^n+3^n+\dots+n^n.\]

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

    \[\begin{array}{lllllll} 1&&&&&&\\ 2&3&4&&&&\\ 3&4&5&6&7&&\\ 4&5&6&7&8&9&10\\ \dots&&&&&& \end{array}\]

равна квадрату нечетного числа.

15. Доказать, что произведение

    \[P=(1+2)(3+4+5)(6+7+8+9)\ldots,\]

состоящее из n сомножителей, равно

    \[{(n!)^3(n+1)^2(n+2)\over 2^{n+1}}.\]

16. Доказать, что сумма всевозможных парных произведений n натуральных чисел 1,2,\ldots,n равна

    \[{(n-1)n(n+1)(3n+2)\over 24}.\]

17. Доказать, что для любого натурального n>1

    \[{4^n\over n+1}<{(2n)!\over (n!)^2}.\]

Комментарии (RSS)  |  Трекбек

Комментариев: 35

  1. 1 Заметки о проблеме масти лошадей | Математика, которая мне нравится:

    [...] 1. Все лошади одной масти. (Доказательство индукцией по числу [...]

    19 Март 2011, 19:46

  2. 2 CS:

    как же решать 16 и 17:( или хотя бы уравнение в 16 составить..((

    [Ответить]

    aigerim Reply:
    Октябрь 27th, 2014 at 0:01

    (1+2+3+…+n)^2=1^2+2^2+…+n^2+2(1*2+1*3+…+2*3+2*4+….+(n-1)*n)
    n^2(n+1)^2/4=n(n+1)(2n+1)/6+2A
    A=n(n+1)(3n^2-n+1)/24=n(n+1)(n-1)(3n+2)/24

    [Ответить]

    26 Октябрь 2011, 19:55

  3. 3 Елизавета Александровна Калинина:

    В задаче 16 просто нужно записать сумму всевозможных попарных произведений n первых натуральных чисел:

        \[1\cdot2+1\cdot3+1\cdot4+\ldots+1\cdot n+2\cdot3+2\cdot4+\ldots+2\cdot n+\ldots+\]

    +(n-1)n .

    В задаче 17 воспользуйтесь последней теоремой (там, где деление).

    [Ответить]

    26 Октябрь 2011, 20:13

  5. 5 Интересная последовательность | Математика, которая мне нравится:

    [...] ее “ослиной’’ ) индукцией. Разумеется, только полная математическая индукция дает верный [...]

    29 Апрель 2012, 0:04

  6. 6 Вася Пупкин:

    В 6 примере, в скобках написано: (четверок – n) – что это значит?

    [Ответить]

    25 Май 2012, 19:13

  7. 7 Елизавета Александровна Калинина:

    Это сколько раз встречается число 4 в левой части неравенства.

    [Ответить]

    25 Май 2012, 20:33

  8. 8 Вася Пупкин:

    В третьем примере у меня получилось следующее неравенство: (2n+2)! > (n+1)!(n+2)^(n+1) – можно ли считать это доказательством? Прошу прощения, если надоел )

    [Ответить]

    Елизавета Александровна Калинина Reply:
    Май 29th, 2012 at 12:49

    Все нормально, спрашивайте )

    Неравенство нужно доказать.

    [Ответить]

    29 Май 2012, 11:10

  9. 9 Федор:

    в 4-й задаче дошел до 1/\sqrt{k+1}>\sqrt{k+1}-\sqrt{k}, дальше не знаю как доказывать.

    [Ответить]

    Елизавета Александровна Калинина Reply:
    Июль 30th, 2012 at 20:12

    Федор, теперь правую часть домножьте и поделите на \sqrt{k+1}+\sqrt{k} (тогда в числителе получится разность квадратов).

    [Ответить]

    Нурсулу Reply:
    Октябрь 21st, 2012 at 23:18

    А как будет до этого?Хотя бы подскажите как мне начинать?

    [Ответить]

    Елизавета Александровна Калинина Reply:
    Октябрь 22nd, 2012 at 10:28

    Посмотрите пример с неравенством. Сначала проверьте базу индукции при n=2, а потом рассмотрите разности левых частей при n=k+1 и при n=k и разности правых частей. Далее нужно сравнить эти разности.

    [Ответить]

    Тимур Reply:
    Июнь 17th, 2013 at 12:03

    Добрый день.
    В 4-ом я получил следующее (после умножения на {\sqrt{k+1}+\sqrt{k}} правой части):
    {1\over \sqrt{n+1}=(\sqrt{n+1}-\sqrt{n})\cdot (\sqrt{n+1}+\sqrt{n})\over \sqrt{k+1}+\sqrt{k}}
    Упростив данное уравнение, я, естественно, прихожу опять к началу: {1\over \sqrt{n+1}=\sqrt{k+1}-\sqrt{k}}. Промежуточным шагом является: {1\over \sqrt{n+1}=(2n+1)\over \sqrt{k+1}+\sqrt{k}}
    Что с этим можно сделать?

    И ещё один вопрос, немного не по теме: дробная степень выражается только через понятие корня?

    Спасибо.

    [Ответить]

    Елизавета Александровна Калинина Reply:
    Июнь 19th, 2013 at 22:38

    Тимур, не должно быть одновременно k и n, проверьте.

    Да, степень с рациональным показателем определяется через корень.

    [Ответить]

    30 Июль 2012, 19:06

  10. 10 Федор:

    кстати, в третьем преобразовал до того де неравенства, что и у Васи Пупкина, дальше ничего не придумал, пол дня на него ушло.

    [Ответить]

    Елизавета Александровна Калинина Reply:
    Июль 31st, 2012 at 10:50

    Поделите обе части неравенства на (n+1)!, а дальше сравните множители, оставшиеся слева и справа (их одинаковое количество).

    [Ответить]

    31 Июль 2012, 0:32

  11. 11 Федор:

    поясните пожалуйста условие 5й задачи

    [Ответить]

    Елизавета Александровна Калинина Reply:
    Сентябрь 4th, 2012 at 21:36

    Давайте для примера возьмем n=3. Тогда сумма попарных произведений квадратов натуральных чисел от 1 до 3 равна

        \[1^2\cdot2^2+1^2\cdot3^2+2^2\cdot3^2 .\]

    [Ответить]

    4 Сентябрь 2012, 16:52

  12. 12 Александр:

    никак не получается доказать индукционный переход (k=n+1) в 10й задаче, базу n=2,3 – доказал с помощбю теоремы косинусов, а дальше застрял

    [Ответить]

    Елизавета Александровна Калинина Reply:
    Октябрь 17th, 2012 at 20:53

    Александр, Вы правы, можно воспользоваться теоремой косинусов для выражения стороны многоугольника через R. После этого нужно воспользоваться формулой
    \displaystyle2\cos\frac{\pi}{2^n}=\sqrt{2+2\cos\frac{\pi}{2^{n-1}}}, которая получается из формулы косинуса половинного аргумента.

    [Ответить]

    17 Октябрь 2012, 13:10

  13. 13 Дмитрий:

    Исп. метод мат. индукции, доказать:
    1-2^2+3^2-4^2+…+(-1)^n-1*n^2=(-1)^n-1*(n(n+1))/2

    [Ответить]

    Елизавета Александровна Калинина Reply:
    Ноябрь 25th, 2012 at 17:58

    Дмитрий, в чем конкретно сложность?

    [Ответить]

    25 Ноябрь 2012, 16:33

  14. 14 сердар:

    а 3 степени n >n -этого как доказать ?

    [Ответить]

    Елизавета Александровна Калинина Reply:
    Декабрь 27th, 2012 at 23:43

    Я бы доказывала делением. База очевидна, а дальше 3^{n+1}/3^n=3>1.

    [Ответить]

    27 Декабрь 2012, 21:59

  15. 15 антон:

    Доказать методом математической индукции, что для любого натурального числа n справедливо утверждение:
    1*1!+2*2!+…+n*n!=(n+1)!-1

    [Ответить]

    Елизавета Александровна Калинина Reply:
    Январь 3rd, 2013 at 14:08

    Антон, вычитайте. Получается (n+1)\cdot(n+1)!=(n+2)!-(n+1)!, что очевидно верно.

    [Ответить]

    3 Январь 2013, 13:49

  16. 16 Константин:

    помогите с решением примера
    -1+3-5+…+(1)^n + (2n – 1) = (-1)^n n

    [Ответить]

    Елизавета Александровна Калинина Reply:
    Февраль 21st, 2014 at 13:51

    Видимо, так: -1+3-5+\ldots+(-1)^n(2n-1)=(-1)^nn.
    База, n=1: -1=(-1)^1\cdot1 — верно.
    Теперь из равенства при n=k+1 вычтем это же равенство при n=k:
    (-1)^{k+1}(2k+1)=(-1)^{k+1}(k+1)-(-1)^kk, т.е.
    (-1)^{k+1}(2k+1)=(-1)^{k+1}(2k+1),
    что верно. Это все.

    [Ответить]

    21 Февраль 2014, 12:17

  17. 17 Меня терзают смутные сомнения:

    по поводу задачи 13. При n=2, S1=1, S2=1+2. Слева S1+S2 получается 4 а справа 1+4=5. Елизавета Александровна, пожалуйста поясните условие.

    [Ответить]

    Елизавета Александровна Калинина Reply:
    Апрель 16th, 2015 at 13:05

    Мы у каждой из прогрессий суммируем первые n членов. При n=2 слева получается S_1=1+1,S_2=1+2, S_1+S_2=5, справа тоже 5.

    [Ответить]

    Меня больше не терзают сомнения Reply:
    Апрель 18th, 2015 at 4:38

    Спасибо за разъяснение. Интересная задача, но для меня оказалась трудной. Решил ее только применив готовую формулу суммирования геометрической прогрессии.

    [Ответить]

    16 Апрель 2015, 7:08

  18. 18 Наир:

    чему равна сумма ∑_∞^(n=1)n/6^n

    [Ответить]

    Елизавета Александровна Калинина Reply:
    Январь 4th, 2017 at 19:45

    У меня получилось 6/25.

    [Ответить]

    29 Декабрь 2016, 15:20

Оставьте свой отзыв

Добавить изображение