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

 

Заметим, что аксиому индукции можно заменить на [[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>\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 = k</math>. Докажем, что тогда оно верно и для <math>n = k + 1</math>. Итак, пусть перед нами <math>k + 1</math> человек.

Здесь будет написано доказательство эквивалентности принципа математической индукции, принципа полной математической индукции и аксиомы существования минимума.

 

{{Готовность|75%}}