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

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$

$\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) | Трекбек

Комментариев: 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 просто нужно записать сумму всевозможных попарных произведений
$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
6 Вася Пупкин:

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

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

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

в левой части неравенства.

[Ответить]
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
Посмотрите пример с неравенством. Сначала проверьте базу индукции при
$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 Федор:

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

[Ответить]
Елизавета Александровна Калинина Reply:
Июль 31st, 2012 at 10:50
Поделите обе части неравенства на
$(n+1)!$

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

[Ответить]
31 Июль 2012, 0:32
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 Александр:

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

[Ответить]
Елизавета Александровна Калинина Reply:
Октябрь 17th, 2012 at 20:53
Александр, Вы правы, можно воспользоваться теоремой косинусов для выражения стороны многоугольника через
$R$

. После этого нужно воспользоваться форулой

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

.
База,
$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 Меня терзают смутные сомнения:

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

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

членов. При
$n=2$

слева получается
$S_1=1+1,S_2=1+2? S_1+S_2=5$

, справа тоже
$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 Наир:

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

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

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

Математика, которая мне нравится

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

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

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

2 CS:

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

4 CS:

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

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

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

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

9 Федор:

10 Федор:

11 Федор:

12 Александр:

13 Дмитрий:

14 сердар:

15 антон:

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

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

18 Наир:

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

Навигация по сайту

Разделы

Новые комментарии

Хороший книжный магазин

Подписка на обновления сайта

Твиттер