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 />

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

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

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

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

    19 Март 2011, 19:46

  2. CS:

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

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

  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

  4. CS:

    спасибо!:)

    26 Октябрь 2011, 22:36

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

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

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

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

Подписаться, не комментируя