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

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

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

    [{1over 1cdot2cdot3}+{1over 2cdot3cdot4}+dots+{1over 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={1over 1cdot2cdot3}={1over 6}\[3mm] displaystyle z_1={1cdot(1+3)over 4cdot(1+1)cdot(1+2)}={1cdot4over 4cdot2cdot3}={1over 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+{1over (k+1)(k+2)(k+3)}=z_k+{1over (k+1)(k+2)(k+3)}=\[3mm] displaystyle ={k(k+3)over 4(k+1)(k+2)}+{1over (k+1)(k+2)(k+3)}={k(k+3)^2+4over 4(k+1)(k+2)(k+3)}=\[3mm] displaystyle ={k^3+9k+6k^2+4over 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+4over 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.

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

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

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

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

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

2.

    [begin{array}{l} displaystyle s_{k+1}-s_k={1over (k+1)^2},\[3mm] displaystyle z_{k+1}-z_k=2-{1over k+1}-left(2-{1over k}right) ={1over k}-{1over k+1}={1over 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!timesdotstimes(2n)!>[(n+1)!]^n при n>1.

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

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

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

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

    [sqrt{displaystyleunderbrace{4+sqrt{4+sqrt{4+dots+sqrt{4}}}}_{n}}<3]

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

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

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

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

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

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

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

    [a_{2^n}=Rsqrt{2-sqrt{displaystyleunderbrace{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^nover n+1}<{(2n)!over (n!)^2}.]

Ссылка на основную публикацию