== Метод математической индукции== Этот метод применяется для доказательства утверждений, зависящих от параметра, принимающего натуральные значения; целью ставится доказать справедливость утверждения при всех значениях параметра. !!П!! **Пример.** Доказать справедливость формулы $$ 1+2+\dots+n=\frac{n(n+1)}{2} $$ при всех натуральных $ n_{} $. При каждом частном значении $ n_{} $ формулу можно //проверить//, но как совершить "переход к бесконечности" --- сделать вывод о справедливости формулы для всего бесконечного набора значений $ n_{} $? Для этого и используется метод математической индукции, который заключается в следующем: пусть имеется некоторое утверждение A , зависящее от параметра $ n_{} $, принимающего значения из $ \mathbb N $. Будем обозначать это утверждение А $ (n) $. 1. Проверяем справедливость утверждения А $ (1) $ (этот пункт называется **базисом индукции**). 2. Выдвигаем предположение о справедливости утверждения А $ (k) $ при $ k_{}>1 $ (**индукционное предположение**). 3. На основании индукционного предположения доказываем утверждение А $ (k+1) $ (**индукционное заключение**). Если это удается осуществить, то делаем вывод, что утверждение А $ (n) $ справедливо для всех натуральных чисел $ n_{} $. Проиллюстрируем работу метода на примере формулы суммы первых $ n_{} $ натуральных чисел. При $ n_{}=1 $ она, очевидно, верна. Пусть справедлива формула $$1+2+\dots+k=\frac{k(k+1)}{2} \ . $$ Тогда на ее основании выводим $$1+2+\dots+k+(k+1)=\frac{k(k+1)}{2}+(k+1)=\frac{(k+1)(k+2)}{2} \ , $$ т.е. формула остается справедливой и при $ n=k+1 $. Следовательно она справедлива при всех $ n \in \mathbb N $. Традиционно считается, что метод математической индукции изобретен Паскалем. И действительно, Паскаль использовал этот метод для доказательства формулы ((:binomial бинома Ньютона)). Однако более углубленное исследование вопроса о приоритете указывает ((#istochniki [1])) на Франческо Мавролико (Maurolico Francesco, латинизированный вариант фамилии --- Maurolycus, 1494--1575), монаха-бенедектинца из греческой семьи, эмигрировавшей на Сицилию от турецкого нашествия. Биография ☞ ((https://mathshistory.st-andrews.ac.uk/Biographies/Maurolico/ ЗДЕСЬ)). Автор благодарит К.В.Постнова за предоставленную информацию. !!?!! Доказать справедливость формул $$1^3+2^3+\dots+n^3=(1+2+\dots+n)^2 \ ; $$ $$ 1 \cdot 1!+2\cdot 2!+3\cdot 3!+\dots+n\cdot n!=(n+1)! -1 \ $$ при $ n \in \mathbb N $. Метод математической индукции --- мощное, но не всесильное средство доказательства. Известны примеры __истинных__ утверждений А $ (n) $ , справедливость которых не может быть установлена этим методом. !!П!! **Пример.** Доказать неравенство $$ \frac{1}{2} \cdot \frac{3}{4} \times \dots \times \frac{2n-1}{2n}< \frac{1}{\sqrt{n}} \ npu \ n \in \mathbb N \ . $$ **Решение.** Справедливость для $ n=1_{} $ очевидна. Предположим, что оно верно для некоторого $ n> 1 $, нужно показать справедливость неравенства $$ \frac{1}{2} \cdot \frac{3}{4} \times \dots \times \frac{2n-1}{2n} \cdot \frac{2n+1}{2n+2}< \frac{1}{\sqrt{n+1}} \ . $$ Домножаем неравенство индукционного предположения на дробь $ (2n+1)/(2n+2) $, получаем: $$ \frac{1}{2} \cdot \frac{3}{4} \times \dots \times \frac{2n-1}{2n} \cdot \frac{2n+1}{2n+2}< \frac{2n+1}{2n+2} \frac{1}{\sqrt{n}} \ . $$ Для того, чтобы прийти к неравенству индукционного заключения, достаточно показать, что $$ \frac{2n+1}{2n+2} \frac{1}{\sqrt{n}} \le \frac{1}{\sqrt{n+1}} \ . $$ Это неравенство эквивалентно следующему: $$ (2n+1) \sqrt{n+1} \le 2(n+1) \sqrt{n} \ ; $$ возведение в квадрат приводит к: $$ (2n+1)^2(n+1) \le 4(n+1)^2 n \qquad \iff \qquad (n+1)((2n+1)^2- 4(n+1) n) \le 0 \ \iff $$ $$ \iff \qquad n+1 \le 0 \ . $$ Последнее, очевидно, неверно. Попробуем доказать методом математической индукции более сильное утверждение $$ \frac{1}{2} \cdot \frac{3}{4} \times \dots \times \frac{2n-1}{2n}< \frac{1}{\sqrt{n+1}} \ , $$ следствием которого будет доказываемое выше. Кажется, что мы должны прийти к тому же противоречию. Однако на этот раз метод осечки не дает. Для $ n=1_{} $ неравенство очевидно справедливо. Предположим, что оно справедливо для какого-то $ n>1 $. Домножим его на $ (2n+1)/(2n+2) $ и проверим выполнимость неравенства $$ \frac{2n+1}{2n+2} \frac{1}{\sqrt{n+1}} \le \frac{1}{\sqrt{n+2}} \ . $$ Имеем: $$ (2n+1) \sqrt{n+2} \le (2n+2) \sqrt{n+1} \qquad \iff \qquad (2n+1)^2 (n+2) \le (2n+2)^2 (n+1) \ \iff $$ $$ \iff 0 \le 3\,n+2 \ , $$ что справедливо. ♦ Итак, исходное неравенство справедливо, но доказать его методом математической индукции не удается, хотя более сильное утверждение --- удается! Такая ситуация называется **парадоксом изобретателя**, это название было придумано в XX веке венгерским математиком Д.Пойа[[Хотя сам парадокс был известен гораздо раньше.]]. Противоречие разрешается следующим соображением: если утверждение А $ (n) $ слабее утверждения B $ (n) $, то и индукционные предположения, которые применяются в ходе доказательства, также будут находиться в том же соотношении --- фактически мы получаем больший исходный ресурс для вывода индукционного заключения. Иногда, ввиду особенности утверждения А $ (n) $, утверждение А $ (1) $ не имеет смысла, тогда в качестве базиса индукции рассматривается утверждение А $ (2) $ . В дальнейшем подобные модификации метода математической индукции будем применять без излишних комментариев. ==Источники== [1].** Bussey W.H.** //The Origin of Mathematical Induction//. Amer. Math. Monthly, 1917, Vol. **24**, No 5, 199-207. Текст ☞ {{:basics:the_origin_of_mathematical_induction.pdf}} (pdf).