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

[creative]

Ниже дословно процитирована часть упражнения 1.9 из книги "Конкретная математика" (2-е издание, исправленное):

Цитата:

Иногда возможно использование "обратной индукции", т.е. доказательства от $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$.

Дословный ответ на часть a упражнения 1.9:

Цитата:

(a) Утверждение $P(n - 1)$ мы получаем из неравенства

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

Есть вопрос:

Если следовать определению $x_n$ из a при $\forall n > 1$, то получается следующая замкнутая формула для $x_n$ при $\forall n > 1$:

$x_1$ - база индукции.

Рекуррентное выражение по определению из a

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

Частные случаи

$x_2 = \frac {x_1} {1} = x_1$
$x_3 = \frac {x_1 + x_2} 2 = x_1$
$x_4 = \frac {x_1 + x_2 + x_3} 3 = x_1$

Предположение о замкнутом выражении для $x_n$ при $\forall n > 1$

$x_{n} = x_1$

Доказательство предположения

$x_{n + 1} = x_n + \frac {(n -1)x_n - (x_1 + ... + x_{n - 1})} {n(n - 1)} $

Из предположения, что $x_2, ..., x_n = x_1$ следует

$x_{n + 1} = x_1 + \frac {(n - 1)x_1 - (n - 1)x_1} {n(n - 1)} = x_1 + \frac {x_1 - x_1} {n} = x_1$ $\Box$

Тогда получается что

$P(n): x_1^n \leq \left( \frac {nx_1} n \right) ^n$

Из из этого следует

$P(n): x_1^n = x_1^n$ при $\forall n$

Если все мои утверждения верны, то вообще нет смысла выводить $P(n - 1)$ из $P(n)$ и тем более такой формулой, которая дана в ответе на упражнение 1.9 (a), который приведён выше.

Учитывая тот факт, что Дональда Кнут, Роналд Грэхем, Орен Паташник очевидно умнее меня, то значит что я ошибаюсь в выкладках приведённых выше.

В связи с этим вопрос: где я ошибся?

[Shtirlic]

creative
Я сильно не всматривался, но похоже у вас все правильно (хотя в доказательстве предположения я мало чего понял, но я и не пытался=)). Просто здесь подразумевалось другое решение. В выражении $P(n)$, заменяем $x(n)$ по формуле из a, преобразовываем, получаем неравенство из ответа, далее сокращаем, вот вам и выражение $P(n-1)$.

[Sonic86]

Нужно заметить, что при такой обратной индукции следует доказывать не только $P(n) \Rightarrow P(n-1)$, но даже и $P(n) \Leftrightarrow P(n-1)$, а иначе будет фигня, но доказать $P(n) \Leftrightarrow P(n-1)$ в общем случае сложнее чем $P(n) \Leftarrow P(n-1)$.

[creative]

Shtirlic, Sonic86

Даже если моё решение правильное, а предложенное в книге решение является вторым решением, то всё равно возникает вопрос с неравенством предложенным в ответе:

Цитата:

(a) Утверждение $P(n - 1)$ мы получаем из неравенства

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

Тут представлена попытка выразить $P(n - 1)$ через $P(n)$ и из этого выражения следует:

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

Что соответствует $P(n - 1)$ и всё правильно.

Я не понял откуда взялась правая часть неравенства:

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

То есть эта часть не исскуственно же подогнана с потолка!

[Shtirlic]

Sonic86 в сообщении #353364 писал(а):

Нужно заметить, что при такой обратной индукции следует доказывать не только $P(n) \Rightarrow P(n-1)$, но даже и $P(n) \Leftrightarrow P(n-1)$, а иначе будет фигня, но доказать $P(n) \Leftrightarrow P(n-1)$ в общем случае сложнее чем $P(n) \Leftarrow P(n-1)$.

Может не все так категорично, временами это может быть и полезно, когда знаешь верхнюю границу $n$. Да и притом если можешь доказать $P(n-1) \Rightarrow P(n)$, то я не вижу смысла доказывать $P(n) \Leftrightarrow P(n-1)$.

-- Пт сен 17, 2010 22:29:19 --

creative
Конечно не подгонка, я же говорил, заменяем $x_n$ по формуле, преобразовываем и получаем эту правую часть.
А ваше решение технически неверно, вы доказали верность неравенства, но не то, что $P(n)$ влечет $P(n-1)$.

[creative]

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

Конечно не подгонка, я же говорил, заменяем $x_n$ по формуле, преобразовываем и получаем эту правую часть.

Я всё таки туплю, всё получается:

$ 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) = P(n - 1) $

Только $P(n)$ не влечет $P(n - 1)$, а равен ему, а в книге написано влечет. Как-то не очень очевидно.

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

А ваше решение технически неверно, вы доказали верность неравенства, но не то, что $P(n)$ влечет $P(n - 1)$.

Но я же доказал не только верность неравенства, но и то, что имеет место не нестрогое неравенство, а строгое равенство для всех $n$, а это однозначно говорит о том, что $P(n) = P(n - 1)$. Тогда почему технически неверно? (я не спорю, а хочу понять, почему в учебнике другое менее очевидное решение, а не то, которое привёл я, которое однозначно показывает результат).

[Shtirlic]

creative
Все верно кроме последнего. Неравенство не может быть равно неравенству. Правильно:
$P(n) \Rightarrow P(n-1)$

[creative]

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

Все верно кроме последнего. Неравенство не может быть равно неравенству. Правильно:
$P(n) \Rightarrow P(n-1)$

Не понимаю, я же доказал, что не $\leq$, а $=$. А значит $P(n) = P(n - 1)$. Почему нет? Ведь они абсолютно равны.

И ещё один вопрос, почему тут нужно использовать "обратную индукцию", а не стандартную (т.е. доказать, что $P(n + 1)$ следует за $P(n)$).

[Sonic86]

Shtirlic писал(а):

Может не все так категорично, временами это может быть и полезно, когда знаешь верхнюю границу $n$. Да и притом если можешь доказать $P(n-1) \Rightarrow P(n)$, то я не вижу смысла доказывать $P(n) \Leftrightarrow P(n-1)$.

Ну если Вы доказываете, что $P(n)$ верно для некоего $n$, а потом доказываете $P(n) \Rightarrow P(n-1), P(n-1) \Rightarrow P(n-2), ...$, тогда да - все в порядке. А если Вы доказываете $P(0)$, а потом $P(1) \Rightarrow P(0), P(2) \Rightarrow P(1), ...$ и думаете, что позволит Вам по индукции доказать, что $(\forall k)P(k)$, то это неверно. Например я так могу доказать, что $(\forall k)k=0$. Действительно, $0=0$ - база верна, предположим, что для $k>0$ верно $k=0$, тогда $k(k-1)=0$ и сокращаем на $k>0$, получим $k-1=0$, то есть $P(k) \Rightarrow P(k-1)$, т.обр. "по индукции" мы "доказали", что $(\forall k)k=0$

creative писал(а):

Я всё таки туплю, всё получается:
$ 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) = P(n - 1) $

Только $P(n)$ не влечет $P(n - 1)$, а равен ему, а в книге написано влечет. Как-то не очень очевидно.

Правильнее писать $P(n) \Leftrightarrow P(n-1)$, а не $P(n)=P(n-1)$. Во-вторых, Вы при переходе от первого неравенства ко второму используете не равносильное преобразование, а только $\Rightarrow$, так что эта цепочка не доказывает $P(n) \Leftrightarrow P(n-1)$. И еще Вам можно использовать однородность неравенства для того, чтобы можно было использовать, например, $x_n \geq 1$

creative писал(а):

И ещё один вопрос, почему тут нужно использовать "обратную индукцию", а не стандартную

А вроде бы нет сильной необходимости. Авторы просто демонстрируют принцип на примере.

[Null]

Топик стартер пропустил часть $P(n)\Rightarrow P(2n)$
А $P(n-1)\Rightarrow P(n)$, доказывается сложнее чем приведенное рассуждение и из него не следует, так как в нем используется $x_n=\left(\frac {x_1 + ... + x_{n - 1}} {n - 1} \right)$

[creative]

Sonic86 в сообщении #353397 писал(а):

Правильнее писать $P(n) \Leftrightarrow P(n-1)$, а не $P(n)=P(n-1)$. Во-вторых, Вы при переходе от первого неравенства ко второму используете не равносильное преобразование, а только $\Rightarrow$, так что эта цепочка не доказывает $P(n) \Leftrightarrow P(n-1)$.

Да, я понял пока писал Вам ответ (уже стёр текст ), почему надо писать:

$P(n) \Rightarrow P(n - 1)$, а не $P(n) = P(n - 1).$

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

Топик стартер пропустил часть $P(n)\Rightarrow P(2n)$

Я специально её пропустил, так как хотел сначала разобраться с частью a.

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

А $P(n-1)\Rightarrow P(n)$, доказывается сложнее чем приведенное рассуждение и из него не следует, так как в нем используется $x_n=\left(\frac {x_1 + ... + x_{n - 1}} {n - 1} \right)$

Сейчас буду проверять.

to all

Но я же всё таки был прав в самом начале, что $P(n) = x_1^n$?

[Shtirlic]

Sonic86 в сообщении #353397 писал(а):

Shtirlic писал(а):

Может не все так категорично, временами это может быть и полезно, когда знаешь верхнюю границу $n$. Да и притом если можешь доказать $P(n-1) \Rightarrow P(n)$, то я не вижу смысла доказывать $P(n) \Leftrightarrow P(n-1)$.

Ну если Вы доказываете, что $P(n)$ верно для некоего $n$, а потом доказываете $P(n) \Rightarrow P(n-1), P(n-1) \Rightarrow P(n-2), ...$, тогда да - все в порядке.

Естественно я имел ввиду именно это. Следующий пример само собой бред.

[Null]

P(n) - принимает значения Истинна/Ложь и числу равняться не может
$P(n)\Rightarrow P(2n)$ пропускать нельзя

План такой: вначале доказываем P(2)
Потом по индукции $P(4), P(8)\dots , P(2^n)$
Далее: пусть есть $m<2^n$, $P(2^n)$ -доказано. Тогда доказываем $P(2^n - 1), P(2^n-2)\dots , P(m+1), P(m)$

[Shtirlic]

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

Но я же всё таки был прав в самом начале, что $P(n) = x_1^n$?

Нет! Давайте попробуем условиться так. Если речь идет о равенстве чисел то пишем знак равно. Если речь идеть о равенстве выражений (в вашем понимании, хотя для меня и думаю многих других это звучит неккоректно), то мы говорим равносильность ($\leftrightarrow$)

-- Сб сен 18, 2010 01:22:07 --

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

P(n) - принимает значения Истинна/Ложь и числу равняться не может

Абсолютно верно говорит. Нельзя равенство, неравенство сравнивать с числом (переменной, что олицетворяет число).

[creative]

Null, Shtirlic

Да, теперь понимаю, почему $\leftrightarrow$, а не $=$.