Метод математической индукции

Метод математической индукции

Метод математической индукции — это метод доказательства теорем об истинности некоторых утверждений-формул над целочисленной переменной: формула или схема формул сперва доказывается при некотором начальном значении этой переменной, затем ставится гипотеза-предположение об истинности формулы для произвольного целочисленного значения, а затем доказывается, что из данного предположения возможно вывести доказательство формулы над следующим значением — то есть, тем, что в ряду целых чисел следует за данным в предположении. Это доказывает истинность формулы при всех целочисленных значениях переменной, начиная с проверенного.

Обычно переменная i принимает значения из множества натуральных чисел, в таком случае для доказательства формулы для любого натурального i достаточно доказать формулу для i = 1 и доказать, что если формула верна для i = n, то она верна и для n + 1.

Своего рода инверсия метода математической индукции — это метод бесконечного спуска, которым доказывается отрицание некоего утверждения о целых числах. Обобщения метода математической индукции: трансфинитная индукция, структурная индукция и более общая над ними нётерова индукция. Обратная индукция — вычислительный принцип поиска решений задач.

Алгоритм

Входные данные: n₀; S_n = f(n).

1. Проверяем формулу S_n = f(n) при n = n₀.
   Если формула не верна при n = n₀, то формула не доказана и конец работы.
2. Предполагаем, что формула S_n = f(n) верна при n = k ≥ n₀.
3. Доказываем формулу S_n = f(n) для n = k + 1.
   Если формула S_n = f(n) верна при n = k + 1, то формула доказана для всех n = k ≥ n₀, иначе формула не доказана.

Примеры

Пример 1

Доказать формулу $\sum \limits _{i=1}^{n}i^{2}={\frac {n(n+1)(2n+1)}{6}}$ .

Введем обозначения:

$S_{n}=\sum \limits _{i=1}^{n}i^{2}=1^{2}+2^{2}+\ldots +n^{2}$ ,

$f(n)={\frac {n(n+1)(2n+1)}{6}}$ .

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

1. Проверяем формулу $S_{n}=f(n)$ при $n=1$ .

${\begin{cases}n=1\\S_{n}=\sum \limits _{i=1}^{n}i^{2}\\f(n)={\frac {n(n+1)(2n+1)}{6}}\end{cases}}\Rightarrow {\begin{cases}S_{1}=\sum \limits _{i=1}^{1}i^{2}=1^{2}=1\\f(1)={\frac {1\cdot (1+1)\cdot (2\cdot 1+1)}{6}}={\frac {1\cdot 2\cdot 3}{6}}=1\end{cases}}\Rightarrow$

$S_{1}=f(1)\Rightarrow {\begin{cases}n=1\\S_{n}=f(n)\end{cases}}$ , то есть формула верна при $n=1$

2.Предполагаем, что формула $S_{n}=f(n)$ верна при $n=k$ , то есть $\sum \limits _{i=1}^{k}i^{2}={\frac {k(k+1)(2k+1)}{6}}$ .

3.Доказываем формулу $S_{n}=f(n)$ для $n=k+1$ .

$S_{k+1}=\sum \limits _{i=1}^{k+1}i^{2}=\sum \limits _{i=1}^{k}i^{2}+(k+1)^{2}={\frac {k(k+1)(2k+1)}{6}}+(k+1)^{2}=$

$={\frac {k(k+1)(2k+1)+6(k+1)^{2}}{6}}={\frac {(k+1)\left[k(2k+1)+6(k+1)\right]}{6}}=$

$={\frac {(k+1)\left[(2k^{2}+k)+(6k+6)\right]}{6}}={\frac {(k+1)(2k^{2}+7k+6)}{6}}=$

$={\frac {(k+1)(k+2)(2k+3)}{6}}$

$f(k+1)={\frac {\left(k+1\right)\left((k+1)+1\right)\left(2(k+1)+1\right)}{6}}={\frac {(k+1)(k+2)(2k+3)}{6}}\Rightarrow$

$\Rightarrow S_{k+1}=f(k+1)\Rightarrow {\begin{cases}n=k+1\\S_{n}=f(n)\end{cases}}$ , то есть формула верна при $n=k+1$ .

Формула доказана, ч.т.д.

Пример 2

Доказать формулу $\sum \limits _{i=1}^{n}i^{3}={\frac {n^{2}(n+1)^{2}}{4}}$ .

Введем обозначения:

$S_{n}=\sum \limits _{i=1}^{n}i^{3}=1^{3}+2^{3}+\ldots +n^{3}$ .

$f(n)={\frac {n^{2}(n+1)^{2}}{4}}$ .

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

1. Проверяем формулу $S_{n}=f(n)$ при $n=1$ .

${\begin{cases}n=1\\S_{n}=\sum \limits _{i=1}^{n}i^{3}\\f(n)={\frac {n^{2}(n+1)^{2}}{4}}\end{cases}}\Rightarrow {\begin{cases}S_{1}=\sum \limits _{i=1}^{1}i^{3}=1^{3}=1\\f(1)={\frac {1^{2}\cdot (1+1)^{2}}{4}}={\frac {1\cdot 2^{2}}{4}}=1\end{cases}}\Rightarrow$

$S_{1}=f(1)\Rightarrow {\begin{cases}n=1\\S_{n}=f(n)\end{cases}}$ , то есть формула верна при $n=1$

2.Предполагаем, что формула $S_{n}=f(n)$ верна при $n=k$ , то есть

$\sum \limits _{i=1}^{k}i^{3}={\frac {k^{2}(k+1)^{2}}{4}}$ .

3.Доказываем формулу $S_{n}=f(n)$ для $n=k+1$ .

$S_{k+1}=\sum \limits _{i=1}^{k+1}i^{3}=\sum \limits _{i=1}^{k}i^{3}+(k+1)^{3}={\frac {k^{2}(k+1)^{2}}{4}}+(k+1)^{3}={\frac {k^{2}(k+1)^{2}+4(k+1)^{3}}{4}}=$

$={\frac {(k+1)^{2}\left[k^{2}+4(k+1)\right]}{4}}={\frac {(k+1)^{2}(k^{2}+4k+4)}{4}}={\frac {(k+1)^{2}(k+2)^{2}}{4}}$

$f(k+1)={\frac {(k+1)^{2}\left[(k+1)+1\right]^{2}}{4}}={\frac {(k+1)^{2}(k+2)^{2}}{4}}\Rightarrow$

$\Rightarrow S_{k+1}=f(k+1)\Rightarrow {\begin{cases}n=k+1\\S_{n}=f(n)\end{cases}}$ , то есть формула верна при $n=k+1$ .

Формула доказана, ч.т.д.

Другие примеры

1. ММИ для суммы арифметической прогрессии;
2. ММИ для суммы геометрической прогрессии;
3. ММИ для суммы n натуральных чисел;
4. ММИ для суммы квадратов n натуральных чисел;
5. ММИ для суммы кубов n натуральных чисел;
6. ММИ для суммы обратных произведений текущего и последующего чисел;
7. ММИ для суммы обратных произведений текущего и последующего нечётных чисел;
8. ММИ для суммы обратных сумм корней текущего и предыдущего чисел;
9. ММИ для суммы обратных сумм корней текущего и последующего чисел;
10. ММИ для суммы обратных неполных квадратов сумм кубических корней текущего и предыдущего чисел;
11. ММИ для суммы обратных неполных квадратов сумм кубических корней текущего и последующего чисел;
12. ММИ для суммы обратных произведений сумм корней второй и четвёртой степеней текущего и предыдущего чисел;
13. ММИ для суммы обратных произведений сумм корней второй и четвёртой степеней текущего и последующего чисел;
14. ММИ для суммы отношений числа и 2 в степени этого числа для n натуральных чисел;
15. ММИ для суммы логарифмов отношений последующего и текущего чисел;
16. ММИ для суммы синусов кратных углов;
17. ММИ для суммы косинусов кратных углов;
18. ММИ для неравенства Бернулли;
19. ММИ для неравенства Гюйгенса;
20. ММИ для неравенства Коробова;
21. ММИ для неравенства Коши;
22. ММИ для неравенства Коши-Буняковского;
23. ММИ для неравенства произведения единиц с дробями;
24. ММИ для неравенства средневзвешенных;
25. ММИ для неравенства суммы кубов возрастающих чисел;
26. ММИ для неравенства Фань Цзы;
27. ММИ для обобщённого неравенства Чебышёва для одномонотонных последовательностей;
28. ММИ для обобщённого неравенства Чебышёва для разномонотонных последовательностей;
29. ММИ для транснеравенства одномонотонных последовательностей;
30. ММИ для транснеравенства разномонотонных последовательностей;
31. ММИ Якобсталя для неравенства Коши.

• В примерах даётся корректное применение метода математической индукции в доказательствах.

Разное

Некорректное применение метода математической индукции может вести к логическим парадоксам — см., например, Доказательство одноцветности всех лошадей (автор — Дьёрдь Пойа).

См. также Парадокс кучи.

Другие методы:

1. Метод математической индукции:
   1. индукция вверх 1;
   2. индукция вверх 2;
   3. индукция вверх 3;
   4. индукция вверх и вниз 1;
   5. индукция вверх и вниз 2;
   6. индукция вверх и вниз 3;
   7. индукция вверх и вниз 4.
2. Метод Штурма:
   1. метод Штурма с сохранением суммы 1;
   2. метод Штурма с сохранением суммы 2;
   3. метод Штурма с сохранением произведения 1;
   4. метод Штурма с сохранением произведения 2.