Метод математической индукции (ММИ) | Математика, которая мне нравится

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

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

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

$\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} \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=1 следует, что оно истинно для n=2 , из его истинности при n=2 следует его истинность для n=3 и т.д.

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

$T_1,T_2,\dots,T_n,\dots$

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

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

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

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

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

$s_{k+1}-s_k=z_{k+1}-z_k,$

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

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

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

$s_{k+1}-s_k>z_{k+1}-z_k,$

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

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

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

$\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 , и для любого натурального

$\displaystyle {s_{k+1}\over s_k}>{z_{k+1}\over z_k},$

то для всех натуральных выполняется неравенство 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 до ), равна

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

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

$\sqrt{\displaystyle\underbrace{4+\sqrt{4+\sqrt{4+\dots+\sqrt{4}}}}_{n}}<3$ (четверок — ).

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

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

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

$\displaystyle {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. Доказать, что для всех натуральных $\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}}},$ где — радиус этой окружности (двоек — n-2 ).

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

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

13. Доказать, что если $S_1,S_2,S_3,\dots,S_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, $

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

$\displaystyle {(n!)^3(n+1)^2(n+2)\over 2^{n+1}}. $

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

$\displaystyle {(n-1)n(n+1)(3n+2)\over 24}. $

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

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

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

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

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

[...] 1. Все лошади одной масти. (Доказательство индукцией по числу [...]
19 Март 2011, 19:46
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 Елизавета Александровна Калинина:

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

$1\cdot2+1\cdot3+1\cdot4+\ldots+1\cdot n+2\cdot3+2\cdot4+\ldots+2\cdot n+\ldots+$

.

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

[Ответить]
26 Октябрь 2011, 20:13
4 CS:

спасибо!:)

[Ответить]
26 Октябрь 2011, 22:36
5 Интересная последовательность | Математика, которая мне нравится:

[...] ее “ослиной’’ ) индукцией. Разумеется, только полная математическая индукция дает верный [...]
29 Апрель 2012, 0:04
6 Вася Пупкин:

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

[Ответить]
25 Май 2012, 19:13
7 Елизавета Александровна Калинина:

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

[Ответить]
25 Май 2012, 20:33
8 Вася Пупкин:

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

[Ответить]
Елизавета Александровна Калинина Reply:
Май 29th, 2012 at 12:49
Все нормально, спрашивайте )

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

[Ответить]
29 Май 2012, 11:10
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
Посмотрите пример с неравенством. Сначала проверьте базу индукции при , а потом рассмотрите разности левых частей при и при и разности правых частей. Далее нужно сравнить эти разности.

[Ответить]
Тимур 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
Тимур, не должно быть одновременно и , проверьте.

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

[Ответить]
30 Июль 2012, 19:06
10 Федор:

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

[Ответить]
Елизавета Александровна Калинина Reply:
Июль 31st, 2012 at 10:50
Поделите обе части неравенства на , а дальше сравните множители, оставшиеся слева и справа (их одинаковое количество).

[Ответить]
31 Июль 2012, 0:32
11 Федор:

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

[Ответить]
Елизавета Александровна Калинина Reply:
Сентябрь 4th, 2012 at 21:36
Давайте для примера возьмем . Тогда сумма попарных произведений квадратов натуральных чисел от до равна

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

[Ответить]
4 Сентябрь 2012, 16:52
12 Александр:

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

[Ответить]
Елизавета Александровна Калинина Reply:
Октябрь 17th, 2012 at 20:53
Александр, Вы правы, можно воспользоваться теоремой косинусов для выражения стороны многоугольника через . После этого нужно воспользоваться форулой
$2\cos\frac{\pi}{2^n}=\sqrt{2+2\cos\frac{\pi}{2^{n-1}}}$ , которая получается из формулы косинуса половинного аргумента.

[Ответить]
17 Октябрь 2012, 13:10
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 сердар:

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

[Ответить]
Елизавета Александровна Калинина Reply:
Декабрь 27th, 2012 at 23:43
Я бы доказывала делением. База очевидна, а дальше $3^{n+1}/3^n=3>1$ .

[Ответить]
27 Декабрь 2012, 21:59
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 Константин:

помогите с решением примера
-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$ .
База, : $-1=(-1)^1\cdot1$ — верно.
Теперь из равенства при вычтем это же равенство при :
$(-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 Меня терзают смутные сомнения:

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

[Ответить]
Елизавета Александровна Калинина Reply:
Апрель 16th, 2015 at 13:04
Мы у каждой из прогрессий суммируем первые членов. При слева получается , справа тоже .

[Ответить]
Елизавета Александровна Калинина Reply:
Апрель 16th, 2015 at 13:05
Мы у каждой из прогрессий суммируем первые членов. При слева получается , справа тоже .

[Ответить]
Меня больше не терзают сомнения Reply:
Апрель 18th, 2015 at 4:38
Спасибо за разъяснение. Интересная задача, но для меня оказалась трудной. Решил ее только применив готовую формулу суммирования геометрической прогрессии.

[Ответить]
16 Апрель 2015, 7:08
18 Наир:

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

[Ответить]
Елизавета Александровна Калинина Reply:
Январь 4th, 2017 at 19:45
У меня получилось 6/25.

[Ответить]
29 Декабрь 2016, 15:20