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

[Shtirlic]

creative
Как то вы намудрили. Используя a, $b$ докажем c методом мат индукции.

Рассмотрим выражение $P(2k)$
База:

k=1.

$P(2k)=P(2)$ - верно (это уже доказанно).

Индуктивное предположение:
n=k
Пусть для всех $z\leq 2k$ $P(z)$ - верно

Шаг индукции:
n=k+1.

$k+1\leq 2k$, следовательно из предположения $P(k+1)$ - верно. Тогда из $b$ верно $P(2k+2)$, а из $a$ верно $P(2k+1)$, следовательно $P(z)$ верно при всех $z\leq 2(k+1)$.
Ч.Т.Д.

[creative]

Shtirlic

Можно ещё проще доказать c:

$P(2)$ истинно по определению, согласно b истинны все $P(2^m)$ $\forall m \geq 1$, для любого $P(n)$, где $n \geq 2$, существует минимальное число $2^m$ большее $n$, таким образом согласно a из $P(2^m)$ следует $P(2^m - 1)$, а из $P(2^m - 1)$ следует $P(2^m - 2)$ и так далее до $P(n)$ $\Box$

Но в моём предыдущем посте содержаться важные для моего понимания индукции и импликации идеи. Если есть возможность, то хорошо было бы проверить выкладки в предыдущем посте.

[Shtirlic]

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

Shtirlic

Можно ещё проще доказать c:

$P(2)$ истинно по определению, согласно b истинны все $P(2^m)$ $\forall m \geq 1$, для любого $P(n)$, где $n \geq 2$, существует минимальное число $2^m$ большее $n$, таким образом согласно a из $P(2^m)$ следует $P(2^m - 1)$, а из $P(2^m - 1)$ следует $P(2^m - 2)$ и так далее до $P(n)$ $\Box$

Но в моём предыдущем посте содержаться важные для моего понимания индукции и импликации идеи. Если есть возможность, то хорошо было бы проверить выкладки в предыдущем посте.

Да, хорошее доказательство, и как раз иллюстрирует зачем нужна обратная индукция!=)
А теперь про ваше "по определению", вы понимаете что это значит? Мне это аж глаза режет, что в этом посте, что в предыдущем.

[creative]

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

Да, хорошее доказательство, и как раз иллюстрирует зачем нужна обратная индукция!=)
А теперь про ваше "по определению", вы понимаете что это значит? Мне это аж глаза режет, что в этом посте, что в предыдущем.

Да, я понимаю, что верность $P(2)$ не задана в определениях задачи, но оно напрямую вытекает из определения:

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

Правильней сказать, что истинность $P(2)$ является следствием определения (1), так как $(x_1 + x_2)^2 - 4x_1x_2 = (x_1 - x_2)^2 \geq 0$

Что на счёт выкладок тут ?

[Shtirlic]

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

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

Да, хорошее доказательство, и как раз иллюстрирует зачем нужна обратная индукция!=)
А теперь про ваше "по определению", вы понимаете что это значит? Мне это аж глаза режет, что в этом посте, что в предыдущем.

Да, я понимаю, что верность $P(2)$ не задана в определениях задачи, но оно напрямую вытекает из определения:

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

Правильней сказать, что истинность $P(2)$ является следствием определения (1), так как $(x_1 + x_2)^2 - 4x_1x_2 = (x_1 - x_2)^2 \geq 0$

Что на счёт выкладок тут ?

Тогда можно сказать, что и b верно по определению.

А насчет выкладок, я не совсем понял, что такое $R(n)$, поясните, пожалуйста, еще раз.

[creative]

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

Тогда можно сказать, что и b верно по определению.

Это неточное высказывание, такое же как и "$P(2)$ верно по определению". Если доказательство длинное, то в нём может быть ошибка и тогда в таком высказывании будет серьёзный баг. Относительно $P(2)$ я говорил только по двум причинам:

* выводится непосредственно из условия задачи
* не нашёл короткого предложения того, что $P(2)$ истинно

Надо было мне пронумеровать доказательство истинности $P(2)$, а потом сказать "$P(2)$ истинно из (0)".

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

А насчет выкладок, я не совсем понял, что такое $R(n)$, поясните, пожалуйста, еще раз.

Доказательство истинности $P(2)$ обозначу как t

$(x_1 + x_2)^2 - 4x_1x_2 = (x_1 - x_2)^2 \geq 0$

Доказанные утверждениия можно кратко записать следующим образом

$true \rightarrow P(2)$ - это высказывание x и оно истинно согласно доказательству t
$P(2n) \rightarrow P(2n - 1)$ - это высказывание y и оно истинно согласно доказательству a
$P(n) \rightarrow P(2n)$ - это высказывание z и оно истинно согласно доказательству b

$P(m)$, где $m \in \mathbb{N}$ будет истинно только когда можно будет построить полную цепочку из высказываний x, y, z и в самом начале эта цепочка должна иметь x. Например для $P(9)$ одна из возможных цепочек будет выглядеть как:

$true \rightarrow P(2) \rightarrow P(4) \rightarrow P(3) \rightarrow P(6) \rightarrow P(5) \rightarrow P(10) \rightarrow P(9)$

То есть по сути доказательство $P(m)$ для любого $m \geq 2$ сводится к возможности сведения числа $m$ к $2$ используя рекуррентность (построенную из зависимостей в x, y, z):

$R(2) = 1$ (тут в отличии от предыдущего поста я убрал двойку, чтобы не путать, а поставил еденицу обозначающая значение true)
$R(2n - 1) = R(2n)$
$R(2n) = R(n)$

Остаётся доказать, что $R(m)$ существует для любого $m$. Далее я показываю, что замкнутая форма (константа $1$) равна для любого $m \geq 2$.

Например, для определённых высказываний относительно некого $L(n)$ могла бы быть построена следующая рекуррентность:

$F(2) = 1$
$F(n) = F(n \backslash 2)$ (тут $ \backslash $ означает деление нацело)

Тут очевидно, что $F(n)$ несуществует для некоторых $n$, потому что не все натуральные числа делятся пополам нацело. Соответственно не все $L(n)$ были бы истинны.

Если тут и есть ошибки, то мне кажется основная идея ценна для понимания.

[creative]

... Признаю, что мои рассуждения становятся неправильными в предыдущем сообщении с места:

Цитата:

... используя рекуррентность (построенную из зависимостей в x, y, z):

Правильней и лучше доказать, что алгоритм всегда завершит своё выполнение при любом $m > 2$:

$while (m \neq 2) \{$

$if\ (n\ mod\ 2 \neq 0)\ m = m + 1$
$if\ (n\ mod\ 2 = 0)\ m = m / 2$

$\}$

Инвариант цикла $(m + 1)\backslash 2 < m + 1$ (тут $\backslash$ означает деление нацело) гарантирует, что $m$ будет всегда уменьшаться.

Теперь осталось доказать, что уменьшаясь $m$ рано или поздно станет равным $2$. В этом цикле когда $m$ нечётно, оно увеличивается на еденицу, что гарантирует то, что будучи $> 2$, оно не проскочит двойку. А когда $m$ чётно, то оно делится пополам, но поскольку не существует чётных чисел больших двух удовлетворяющих условию $m \backslash 2 < 2$, то это гарантирует, что $m$ рано или поздно достигнет $2$ $\Box$

[Shtirlic]

creative
Кажется я понял, $R(n)$ бинарная функция, и мы доказываем что для всех n она принимает значение true. Вы решаете задачу как программист, да рассуждения верны, но я не знаю как бы такое доказательство воспринял классический математик. Как я понял, что мат. индукция и была придумана, чтобы строго описывать такие рассуждения. Хотя вы придумали алгоритм, который приводит к истинности. Я против этого способа ничего сказать не могу.

[Pashka]

Возможно, авторы тут косвенно имели ввиду метод наименьшего элемента! Который часто используется вместо доказательства индукцией! И часто им даже проще! Так вот там похожие рассуждения. Я просто поленился вникать в то, что у вас тут написано)
Метод наименьшего элемента обоснован теоремой о том, что в любом подмножестве натуральных чисел существует наименьший элемент. При этом данной теоремой мы можем заменить 4-ую аксиому Пеано, на которой и строится принцип мат. индукции и все последующие обобщения. Полученная система аксиом будет эквивалентной системе аксиом Пеано.
Вот так) Советую познакомится с методом!