Знакомство с методом математической индукции: различия между версиями

м
clean up, removed: Категория:Математика с помощью AWB
(Написана явная глупость про отсутствие базы в какой-либо форме индукции)
м (clean up, removed: Категория:Математика с помощью AWB)
 
Заметим, что аксиому индукции можно заменить на [[m:ru:Аксиома существования минимума|аксиому существования минимума]], и доказать аксиому индукции как теорему.
 
 
Также в скобках заметим, что существует принцип полной математической индукции. Вот его строгая формулировка:
 
Принцип полной математической индукции также может быть доказан при помощи математической индукции. Верно и обратное: принцип математической индукции можно доказать, предполагая принцип полной математической индукции. Так что в аксиомах Пеано можно выбрать в качестве одной из аксиом как аксиому существования минимума, как принцип полной математической индукции, так и принцип математической индукции. Какое из этих трёх утверждений брать за теорему, а какую за аксиомы — дело вкуса. Доказательство эквивалентности этих утверждений смотри в [[#Приложение B|приложении B]]
 
 
=== Ханойские башни ===
# '''[ШАГ]''' В этом предположении доказываем утверждение для случая <math>n = K + 1</math>.
# '''[ВЫВОД]''' Утверждение верно для всех случаев, то есть для всех <math>n</math>.
 
 
Решение задач по данной схеме и называется методом математической
параллельны, и никакие три не пересекаются в одной точке,
пересекаются ровно в <math>\frac{n(n-1)}{2}</math> точках.
 
 
Решение:
 
Подсказка <ref>При проведении следующей прямой инвертируйте одну из полуплоскостей.</ref>.
 
 
 
==== Сумма углов <math>n</math>-угольника. ====
 
<math>1^2 + 2^2 + 3^2 + \dots + k^2 + (k + 1)^2 = \frac{(k + 1)(k + \frac32)(k + 2)}{3}</math>.
 
 
<math>1^2 + 2^2 + 3^2 + \dots + k^2 + (k + 1)^2 = (1^2 + 2^2 + 3^2 + \dots + k^2) + (k + 1)^2 =</math>
 
БАЗА. Нужно доказать, что для <math>k = 1</math>, если степень многочлена <math>B(1)</math> больше или равняется <math>4</math>, то степень многочлена <math>B(2) - B(1)</math> больше или равняется <math>3</math>. Это утверждение является верным, так как предположение (если…) не выполняется, степень многочлена <math>B(1)</math> ''не'' больше или равняется <math>4</math> (оно равняется 1, так как после подстановки скаляра (числа) в полином он превращается в скаляр (число)). А если предположение неверно, то [[w:Импликация|импликация]] верна.
 
 
ПРЕДПОЛОЖЕНИЕ. Если степень многочлена <math>B(k)</math> больше или равняется <math>4</math>, то степень многочлена <math>B(k + 1) - B(k)</math> больше или равняется <math>3</math>.
 
По условию, степень многочлена <math>-B(k + 2)</math> и степень многочлена <math>B(k)</math> больше или равняется <math>4</math>. Согласно ММИ степень многочлена <math>B(k + 1)-B(k)</math> больше или равняется <math>3</math>. Возьмём такое <math>s</math>, что коэффициент при <math>x^s</math> в многочлене <math>B(k + 1) - B(k)</math>, обозначим его за <math>bk^s</math>, будет не равен нулю. Так как степень многочлена <math>B(k + 1) - B(k)</math> больше или равнятеся <math>3</math>, то существует такое <math>s \geqslant 3</math>, что коэффициент при <math>k^s</math> <math>b \neq 0</math>.
 
 
Давайте посмотрим на коэффициенты при <math>k^s</math> во всём выражении (*) (как было сказано в идее доказательства, этот коэффициент должен быть не равен нулю). Обозначим коэффициент при <math>k^s</math> в <math>B(k)</math> за <math>ak^s</math>. Тогда коэффициент при <math>k^s</math> в <math>-B(k + 2)</math> будет <math>-a(k + 2)^s</math>. Как было сказано выше, <math>b \neq 0</math>.
 
=== Неравенство Коши ([[w:Неравенство между средним арифметическим и средним геометрическим|неравенство между средним арифметическим и средним геометрическим)]] ===
 
 
Доказать, что
 
Попутно можно заметить, что никакие числа у нас теперь «не торчат». Если бы мы могли применить ММИ, то получили бы выражение <math>\sqrt[3]{\frac{(x_1 + x_2)}{2}\frac{(x_3 + x_4)}{2}\frac{(x_5 + x_6)}{2}}</math>. И тут мы можем применить снова неравенство Коши для <math>n = 1</math> и получить <math>\sqrt[3]{\sqrt[2]{(x_1 \cdot x_2)}\sqrt[2]{(x_3 \cdot x_4)}\sqrt[2]{(x_5 \cdot x_6)}} = \sqrt[6]{x_1 \cdot x_2 \cdot x_3 \cdot x_4 \cdot x_5 \cdot x_6}</math>, и утверждение доказано. Вполне возможно, что мы натолкнулись на плодотворную идею. Для чётного <math>n = 2s</math> мы можем разбить числитель на <math>s</math> разных пар и «поднять» из знаменателя <math>2</math>, то есть если наши пары будут выглядеть как <math>\frac{(x_i + x_{i + 1})}{2}</math>. Однако, число в знаменателе должно подходить к применению ММИ.
 
 
Значит <math>n</math> должно быть чётным, и при том «настолько» чётным, чтобы мы могли применить к нему индукцию (чтобы <math>\frac{n}{2}</math> было тоже чётным). Может быть достаточно взять <math>n = 4s</math>? Попробуем:
<math>=\frac{\frac{x_1 + x_2}{2}\frac{x_3 + x_4}{2}\frac{x_5 + x_6}{2}\frac{x_7 + x_8}{2}\frac{x_9 + x_10}{2}\frac{x_11 + x_12}{2} }{6}</math>.
 
И для применения ММИ <math>6</math> должно делиться на <math>4</math>. Если устранить это препятствие, то всё получится:
 
<math>\sqrt[3]{\frac{x_1 + x_2}{2}\frac{x_3 + x_4}{2}\frac{x_5 + x_6}{2}\frac{x_7 + x_8}{2}\frac{x_9 + x_{10}}{2}\frac{x_{11} + x_{12}}{2}} =</math>
делится на <math>9</math>, и мы заключаем, что утверждение
верно для любого <math>n</math>.
 
 
=== Задача про делимость <math>3^{2n + 2} + 8n - 9</math> и <math>4^n + 15n - 1</math> ===
'''Утверждение 1.''' У всех людей глаза одинакового цвета.
 
'''Доказательство.''' Докажем, что в компании из <math>n</math> людей у всех глаза одинакового цвета. При <math>n = 1</math> утверждение очевидно.
 
Предположим, что оно верно при <math>n = k</math>. Докажем, что тогда оно верно и для <math>n = k + 1</math>. Итак, пусть перед нами <math>k + 1</math> человек.
Здесь будет написано доказательство эквивалентности принципа математической индукции, принципа полной математической индукции и аксиомы существования минимума.
 
[[Категория:Математика]]
[[Категория:Алгоритмы]]
{{Готовность|75%}}
 
{{Темы|Математика}}
 
[[Категория:МатематикаАлгоритмы]]
531

правка