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

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

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

Обычно переменная 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

Доказать формулу Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \sum\limits_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}} .

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle S_n=\sum\limits_{i=1}^n i^2=1^2+2^2 +\ldots+n^2} ,

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle f(n)=\frac{n(n+1)(2n+1)}{6}} .

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

1. Проверяем формулу Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle S_n=f(n)} при Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n=1} .

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \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}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle S_1=f(1)\Rightarrow\begin{cases}n=1\\S_n=f(n)\end{cases}} , то есть формула верна при Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n=1}

2.Предполагаем, что формула Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle S_n=f(n)} верна при Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n=k} , то есть Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \sum\limits_{i=1}^k i^2=\frac{k(k+1)(2k+1)}{6}} .

3.Доказываем формулу Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle S_n=f(n)} для Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n=k+1} .

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 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=}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle =\frac{k(k+1)(2k+1)+6(k+1)^2}{6}=\frac{(k+1)\left[k(2k+1)+6(k+1)\right]}{6}=}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle =\frac{(k+1)\left[(2k^2+k)+(6k+6)\right]}{6}=\frac{(k+1)(2k^2+7k+6)}{6}=}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle =\frac{(k+1)(k+2)(2k+3)}{6}}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 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}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \Rightarrow S_{k+1}=f(k+1)\Rightarrow\begin{cases}n=k+1\\ S_n=f(n)\end{cases}} , то есть формула верна при Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n=k+1} .

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

Пример 2

Доказать формулу Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \sum\limits_{i=1}^n i^3=\frac{n^2(n+1)^2}{4}} .

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle S_n =\sum\limits_{i=1}^n i^3=1^3+2^3+\ldots+n^3} .

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle f(n)=\frac{n^2(n+1)^2}{4}} .

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

1. Проверяем формулу Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle S_n=f(n)} при Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n=1} .

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \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}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle S_1=f(1)\Rightarrow\begin{cases}n=1\\ S_n=f(n)\end{cases}} , то есть формула верна при Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n=1}

2.Предполагаем, что формула Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle S_n=f(n)} верна при Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n=k} , то есть

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \sum\limits_{i=1}^k i^3=\frac{k^2(k+1)^2}{4}} .

3.Доказываем формулу Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle S_n=f(n)} для Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n=k+1} .

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 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}=}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle =\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}}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle f(k+1)=\frac{(k+1)^2\left[(k+1)+1\right]^2}{4}=\frac{(k+1)^2(k+2)^2}{4}\Rightarrow}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \Rightarrow S_{k+1}=f(k+1)\Rightarrow\begin{cases}n=k+1\\S_n=f(n)\end{cases}} , то есть формула верна при Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 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.