"Обратная индукция" для простого алгебраического неравенства

[Shtirlic]

creative
Хорошо, что теперь вы понимаете.
А саму задачу вы поняли? И почему ваше решение идейно неверно (насчет технически возможно я погорячился, из вашего решения можно извлечь нужное)?
Просто эта задача была создана для понимания "обратной индукции", а вы отступились от нее. Т.е. для просто решения все верно, а с точки понимания инструмента нет (что было целью, поэтому ваше решение и вызвало вопросы у вас).

[creative]

Shtirlic в сообщении #353433 писал(а):

Хорошо, что теперь вы понимаете.
А саму задачу вы поняли? И почему ваше решение идейно неверно (насчет технически возможно я погорячился, из вашего решения можно извлечь нужное)?
Просто эта задача была создана для понимания "обратной индукции", а вы отступились от нее. Т.е. для просто решения все верно, а с точки понимания инструмента нет (что было целью, поэтому ваше решение и вызвало вопросы у вас).

Это очень хороший ответ на вопрос о том, почему в учебнике именно то решение, а не которое я привёл и почему моё решение существует.
Я подразумевал, что если дано упражнение, значит есть только единственное решение, а если получается другое решение, значит оно неправильное. Теперь я вижу, что могут существовать два решения, но правильным будет то, которое соответствует получено методом, понимание которого требуется от решающего это упражнение.

То есть полное решение (a) будет следующим:


$ P(n): x_1 ... x_n \leq \left(\frac {x_1 + ... + x_n} n \right) ^n$

$ P(n): x_1 ... x_n \leq \left(\frac {x_1 + ... + x_{n - 1}} n + \frac {x_1 + ... + x_{n - 1}} {n(n - 1)} \right) ^n$

$ P(n): x_1 ... x_n \leq \left(\frac {(n - 1)(x_1 + ... + x_{n - 1}) + x_1 + ... + x_{n - 1}} {n(n - 1)} \right) ^n$

$ P(n): x_1 ... x_n \leq \left(\frac {n(x_1 + ... + x_{n - 1}} {n(n - 1)} \right) ^n$

$ P(n): x_1 ... x_n \leq \left(\frac {x_1 + ... + x_{n - 1}} {n - 1} \right) ^n$

$ P(n): x_1 ... x_{n - 1} \frac {x_1 + ... + x_{n - 1} }{n - 1} \leq \left(\frac {x_1 + ... + x_{n - 1}} {n - 1} \right) ^n$

$ P(n): x_1 ... x_{n - 1} \leq \left(\frac {x_1 + ... + x_{n - 1}} {n - 1} \right) ^{n - 1}$

$ P(n) \Rightarrow P(n - 1) $

[Shtirlic]

creative
Теперь решение полностью верно. Просто математика, наука точная, и надо обращать очень особое внимание на формулировку задачи.
Технически можно многое вывернуть под правильное решение, но фактичести не сделать того, что хотел автор (но это тоже надо уметь=)).
Полностью я это понял только недавно, на 4-м курсе университета.
Хотя про мат. индукцию мне все вбили на втором курсе. Есть очень хороший сафизм на эту тему (сафизм - утверждение казущееся верным, но не являющимся таковым), после которого я все и понял.
Есть желание, я его приведу.

[creative]

Shtirlic в сообщении #353442 писал(а):

creative
Теперь решение полностью верно. Просто математика, наука точная, и надо обращать очень особое внимание на формулировку задачи.
Технически можно многое вывернуть под правильное решение, но фактичести не сделать того, что хотел автор (но это тоже надо уметь=)).
Полностью я это понял только недавно, на 4-м курсе университета.
Хотя про мат. индукцию мне все вбили на втором курсе. Есть очень хороший сафизм на эту тему (сафизм - утверждение казущееся верным, но не являющимся таковым), после которого я все и понял.
Есть желание, я его приведу.

Приведите, будет очень хорошо, учитывая то, что Вы дали очень ясное объяснение предыдущим вещам (хотя и другие пользователи ответили тоже хорошо).

[Null]

Сафизм это лейсбийская любовь.

[Shtirlic]

creative в сообщении #353445 писал(а):

Shtirlic в сообщении #353442 писал(а):

creative
Теперь решение полностью верно. Просто математика, наука точная, и надо обращать очень особое внимание на формулировку задачи.
Технически можно многое вывернуть под правильное решение, но фактичести не сделать того, что хотел автор (но это тоже надо уметь=)).
Полностью я это понял только недавно, на 4-м курсе университета.
Хотя про мат. индукцию мне все вбили на втором курсе. Есть очень хороший сафизм на эту тему (сафизм - утверждение казущееся верным, но не являющимся таковым), после которого я все и понял.
Есть желание, я его приведу.

Приведите, будет очень хорошо, учитывая то, что Вы дали очень ясное объяснение предыдущим вещам (хотя и другие пользователи ответили тоже хорошо).

Без вопросов верно.

И так сафизм. Трудно будет объяснить текстом, но я попробую.

софизм:

Докажем, что у всех девушек на земле цвет волос один и тот же.

База индукции.
n=1.
Берем одну девушку, у нее явно один цвет волос=> база верна.

Пусть для n=k утверждение верно. - предположение.
Докажем утверждение для n=k+1.

Здесь поясню точнее методику, из предположения, если я соберу k девушек в одном месте, то цвет волос у них будет один и тот же (пусть это будет стадион).

И так на стадионе k девушек, у всех один цвет волос по предположению.
Есть k+1-ая девушка. Я выгоняю одну девушку со стадиона, и беру эту k+1-ую девушку на стадион.
По предположению, на стадионе опять все девушке одного цвета волос.
И так, новая девушка одного цвета со всеми и девушка, которую выгнали одного цвета с оставшимися, следовательно все девушки одного цвета, т.е. все k+1 девушка одного цвета.
Из верности для k следует верность k+1.
Следовательно верно для всех девушек.

-- Сб сен 18, 2010 02:42:53 --

Null
Я думаю, вы не будете спорить, что человек разбирается в чем либо, только тогда, когда может найти в этом ошибку.

[creative]

Shtirlic

Да, мне знаком этот софизм. Это упражнение 1.1 из той же книги (внешняя ссылка на скачивание книги с файлообменника, по ссылке удалось скачать книгу, надеюсь с данным текстом модераторы не удалят моё сообщение), только там не девушки, а лошади

В упражнении 1.1 понятней написано, чем в википедии.

[Shtirlic]

creative
Интапритаций много. Я слышал и про лошай и про кошек.
Когда я был на первом курсе (жил в общаге), ко мне часто с ним приходили студенты, но мои предположения всегда были неверны. А когда на втором курсе нашей группе задали эту задачу и отвергли все мои доводы (моя специальность самая математическая в моем университете), на той же паре я ее и решил. Этот софизм раскрывает многое о математике. Главный вывод, предполагай и придумывай, что хочешь. Главное сумей это строго доказать.

[creative]

Выкладываю остальную часть упражнения.

Цитата:

b. Покажите, что $P(n)$ и $P(2)$ влекут $P(2n)$.

Решение (на самом деле я сам не решил, а посмотрел ответ, но даже ответ мне не был понятен , на основе ответа я искал решение):

Представляем $P(n)$ разным набором переменных:

$x_1...x_n \leq \left( \frac{x_1 + ... + x_n}{n} \right)^n$

$x_{n + 1}...x_{2n} \leq \left( \frac{x_{n + 1} + ... + x_{2n}}{n} \right)^n$ - так как в части b нужно забыть про взаимосвязи между разными $x_k \forall k \in \mathbb{N}$, здесь это просто разные переменные

Произведение двух неравенств:

$x_1...x_nx_{n + 1}...x_{2n} \leq \left( \frac{x_1 + ... + x_n}{n} \right)^n \left( \frac{x_{n + 1} + ... + x_{2n}}{n} \right)^n$
$x_1...x_nx_{n + 1}...x_{2n} \leq \left( \frac{x_1 + ... + x_n}{n} \frac{x_{n + 1} + ... + x_{2n}}{n} \right)^n$ (1)

Так как в $P(2): x_1x_2 \leq \left( \frac{x_1 + x_2}{2} \right)^2$ переменные $x_1$ и $x_2$ по сути любые переменные, то заменяем $x_1$ на $(x_1 + ... + x_n)/n$, а $x_2$ на $(x_{n + 1} + ... + x_{2n})/n$:

$(\frac{x_1 + ... + x_n}{n})(\frac{x_{n + 1} + ... + x_{2n}}{n}) \leq \left( \frac{x_1 + ... + x_{2n}}{2n} \right)^2$ (2)

Заменяем содержимое внутри скобок в правой части неравенства (1), правой частью неравенства (2):

$x_1...x_{2n} \leq \left( \frac{x_1 + ... + x_{2n}}{2n} \right)^{2n}$

Это неравенство соответствует $P(2n)$ $\Box$

Цитата:

c. Объясните, почему отсюда следует справедливость $P(n)$ при всех $n$.

Если $n$ нечётное, то согласно части a $P(n)$ следует из $P(n + 1)$, а $n + 1$ в таком случае будет чётным, а это значит, что $P(n + 1)$ является следствием $P(\frac{n + 1}{2})$. Продолжая этот процесс мы получаем $P(2)$, которое в свою очередь справедливо, так как $(x_1 + x_2)^2 - 4x_1x_2 = (x_1 - x_2)^2 \geq 0$ (как и описано в описании упражнения, см. в начале) (тут не рассматриваются комплексные числа) $\Box$

Есть ли ошибка в моих рассуждениях?

[Shtirlic]

creative
Если формула для $x_k$ из части a. не применимо к $c.$, то и $P(n+1)\rightarrow P(n)$ использовать нельзя. И доказывать c. старайтесь строго, метадом мат индуции, такие рассуждения часто зарезают.
Остальное очень похоже на правду.

[creative]

Shtirlic в сообщении #354719 писал(а):

Если формула для $x_k$ из части a. не применимо к $c.$, то и $P(n+1)\rightarrow$ использовать нельзя.

Вот полностью само упражнение:

Цитата:

Иногда возможно использование "обратной индукции", т.е. доказательства от $n$ к $n-1$, а не наоборот! К примеру, рассмотрим утверждение

$ P(n): x_1 ... x_n \leq \left(\frac {x_1 + ... + x_n} n \right) ^n , $ если $x_1 , ... , x_n \geq 0.$

Оно справедливо для $n = 2$, так как $(x_1 + x_2)^2 - 4x_1x_2 = (x_1 - x_2)^2 \geq 0$

a: Полагая $x_n = (x_1 + ... + x_{n - 1})/(n - 1),$ докажите, что $P(n)$ влечет $P(n - 1)$ при всяком $n > 1$.
b. Покажите, что $P(n)$ и $P(2)$ влекут $P(2n)$.
c. Объясните, почему отсюда следует справедливость $P(n)$ при всех $n$.

c тут я перевожу как:

c. Объясните, почему из a и b следует справедливость $P(n)$ при всех $n$.

Ответ на c согласуется с ответом в книге, значит эта интерпретация предложения в c верна.

[Shtirlic]

creative
Возможно, но решение все же должно быть строгим, а не набором мыслей, хоть и верным.

[creative]

Shtirlic в сообщении #354730 писал(а):

Возможно, но решение все же должно быть строгим, а не набором мыслей, хоть и верным.

Полностью согласен, но что нехватает для строгости в моей выкладке b и c?

[Null]

В вашей выкладке не хватает 2 вещей: случай четного n не рассмотрен, ну и надо бы обосновать почему вы в итоге придете к 2.

Так же найдите место где вы пользовались $x_i\ge0$

[creative]

Null в сообщении #354751 писал(а):

В вашей выкладке не хватает 2 вещей: случай четного n не рассмотрен, ну и надо бы обосновать почему вы в итоге придете к 2.

Полное доказательство части с:

$P(2)$ истинно по определению $P(n)$, в части a доказано, что $P(n) \Rightarrow P(n - 1)$, в части b доказано, что $P(2) \wedge P(n) \Rightarrow P(2n)$, тогда доказательство истинности $P(n)$ для определённого $n$ сводится к следующему

В случае нечётного $n$ неравенство $P(n)$ держится на истинности неравенства $P(n + 1)$, где $n + 1$ является чётным, а $P(n + 1)$ в свою очередь держится на истинности $P(\frac{n + 1}{2})$. В случае чётного $n$ неравенство $P(n)$ держится на истинности неравенства $P(\frac{n}{2})$. Таким образом доказательство истинности $P(n)$ сводится к нисходящей рекурсии в корне которой должно получится $P(2)$, истинность которого установлена по определению.

Можно определить рекуррентность $R(n)$ для $\forall n \in \mathbb{N}$, которая в виде равенства между разными $R(n)$ отображает взаимосвязи следований между разными $P(n)$, то есть

$true \rightarrow P(2)$ - высказывание истинно ($:= true$) согласно определению
$P(2n) \rightarrow P(2n - 1)$ - высказывание истинно согласно доказательству части a
$P(n) \rightarrow P(2n)$ - высказывание истинно согласно доказательству части b

Доказательство истинности $P(n)$ при любом $n$ сводится к решению рекуррентности

$R(2) = 2$
$R(2n - 1) = R(2n)$
$R(2n) = R(n)$

Частный случай для первых $n$

$ \begin{center} \begin{tabular}{ | c | c | c | c | c | c | c | c | c } \hline n & 2 & 3 & 4 & 5 & 6 & 7 & 8 & ... \\ \hline R(n) & 2 & 2 & 2 & 2 & 2 & 2 & 2 & ... \\ \hline \end{tabular} \end{center} $

Индуктивное предположение $R(n) = 2$ $\forall n \in \mathbb{N}$ верно, так как рекуррентность решается при подстановке двойки в рекуррентные выражения.

Вопрос:

Всё ли правильно в рассуждениях описанных выше? Я написал развёрнуто, так как чувствую, что что-то ускользает из ясного понимания принципа математической индукции и операции импликации (хотя я очень старался соблюсти таблицу истинности для $\rightarrow$).

Null в сообщении #354751 писал(а):

Так же найдите место где вы пользовались $x_i\ge0$

Если убрать условие $x_1...x_n \geq 0$ из первоначальной постановки задачи, то при условии, что $x_i \in \mathbb{R}$ \forall i \in \mathbb{N}$ следующее преобразование из доказательства части a

$ P(n): x_1 ... x_{n - 1} \frac {x_1 + ... + x_{n - 1} }{n - 1} \leq \left(\frac {x_1 + ... + x_{n - 1}} {n - 1} \right) ^n$ (1)

$ P(n): x_1 ... x_{n - 1} \leq \left(\frac {x_1 + ... + x_{n - 1}} {n - 1} \right) ^{n - 1}$ (2)

не может выполнятся если $x_n = \frac {x_1 + ... + x_{n - 1} }{n - 1} < 0$, так как тогда при делении обоих частей неравенства (1) на $x_n$ вместо неравенства (2) получим:

$x_1 ... x_{n - 1} \geq \left(\frac {x_1 + ... + x_{n - 1}} {n - 1} \right) ^{n - 1}$

Вопрос:

Ни упустил я ещё чего-то? Как вообще определить, что в доказательстве нет упущений и оно полное?