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

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

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

\displaystyle {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}<br />
\displaystyle<br />
s_1={1\over 1\cdot2\cdot3}={1\over 6}\\[3mm]<br />
\displaystyle<br />
z_1={1\cdot(1+3)\over 4\cdot(1+1)\cdot(1+2)}={1\cdot4\over<br />
4\cdot2\cdot3}={1\over 6}.<br />
\end{array}

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

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

\begin{array}{l}<br />
\displaystyle<br />
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]<br />
\displaystyle<br />
s_{k+1}=s_k+{1\over (k+1)(k+2)(k+3)}=z_k+{1\over (k+1)(k+2)(k+3)}=\\[3mm]<br />
\displaystyle<br />
={k(k+3)\over 4(k+1)(k+2)}+{1\over (k+1)(k+2)(k+3)}={k(k+3)^2+4\over<br />
4(k+1)(k+2)(k+3)}=\\[3mm]<br />
\displaystyle<br />
={k^3+9k+6k^2+4\over 4(k+1)(k+2)(k+3)}\\[3mm]<br />
\displaystyle<br />
z_{k+1}={(k+1)^2(k+4)\over 4(k+1)(k+2)(k+3)}={k^3+6k^2+9k+4\over<br />
4(k+1)(k+2)(k+3)}\\[3mm]<br />
s_{k+1}=z_{k+1}.<br />
\end{array}

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

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

T_1,T_2,\dots,T_n,\dots

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

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

\displaystyle<br />
{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}<br />
\displaystyle<br />
s_2=1+{1\over 4}={5\over 4}\\[3mm]<br />
\displaystyle<br />
z_2=2-{1\over 2}={3\over 2}<br />
\end{array}\right|\Longrightarrow s_2<z_2

2.

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

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

\displaystyle {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

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

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

\displaystyle {1^2\over 1\cdot3}+{2^2\over<br />
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}<br />
1&&&&&&\\<br />
2&3&4&&&&\\<br />
3&4&5&6&7&&\\<br />
4&5&6&7&8&9&10\\<br />
\dots&&&&&&<br />
\end{array}

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

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

<br />
P=(1+2)(3+4+5)(6+7+8+9)\ldots,<br />

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

\displaystyle<br />
{(n!)^3(n+1)^2(n+2)\over 2^{n+1}}.<br />

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

\displaystyle<br />
{(n-1)n(n+1)(3n+2)\over 24}.<br />

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

\displaystyle<br />
{4^n\over n+1}<{(2n)!\over (n!)^2}.<br />

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

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

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

  2. 2 CS:

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

    [Ответить]

    aigerim Reply:

    (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

    [Ответить]

  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 воспользуйтесь последней теоремой (там, где деление).

    [Ответить]

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

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

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

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

    [Ответить]

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

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

    [Ответить]

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

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

    [Ответить]

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

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

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

    [Ответить]

  8. 9 Федор:

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

    [Ответить]

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

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

    [Ответить]

    Нурсулу Reply:

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

    [Ответить]

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

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

    [Ответить]

    Тимур Reply:

    Добрый день.
    В 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:

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

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

    [Ответить]

  9. 10 Федор:

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

    [Ответить]

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

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

    [Ответить]

  10. 11 Федор:

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

    [Ответить]

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

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

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

    [Ответить]

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

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

    [Ответить]

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

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

    [Ответить]

  12. 13 Дмитрий:

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

    [Ответить]

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

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

    [Ответить]

  13. 14 сердар:

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

    [Ответить]

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

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

    [Ответить]

  14. 15 антон:

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

    [Ответить]

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

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

    [Ответить]

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

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

    [Ответить]

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

    Видимо, так: -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),
    что верно. Это все.

    [Ответить]

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

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

    [Ответить]

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

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

    [Ответить]

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

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

    [Ответить]

    Меня больше не терзают сомнения Reply:

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

    [Ответить]

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

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