Математическая индукция.

[Guliashik]

По методу мат. индукции делается предположение, что утверждение верно для случая n, а затем из этого предположения доказывается что утверждение верно для случая n+1.

Вопрос следующий, как основываясь на предположении можно что то доказать? То есть утверждение для случая n не является точным, а из него каким то образом получается доказательство того, что утверждение верно для всех n.

Может не совсем корректный вопрос. Но надеюсь вы меня поймёте верно.

[gris]

Вы пропустили так называемую "базу индукции".
Утверждение надо доказать для некоторого начального значения $n_0$.
Есть примеры, которые показывают, что без первого шага можно получать "доказательства" совершенно ложных утверждений. Даже более замаскировано: когда индукционный переход не срабатывает именно при первом шаге. Но этим можно обмануть только невнимательных людей.
А бывает, что утверждение верно не для всех натуральных чисел, а только больших некоторого числа.

[Guliashik]

Я ей не уделил должного внимания.
Предположим мы можем доказать для n=1, что утверждение верно. Дальше делаем предположение что утверждение доказано для K случаев. Но это же предположение. Как основываясь на нём, можно дальше что то доказывать?

[gris]

Утверждение может быть либо верным, либо неверным. Мы доказываем, что если оно верно для некоторого $k$ (включая базовый номер), то оно верно для $k+1$.

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

То есть вообще уму не постижимо, однако такова уж логика математики.

[Someone]

Guliashik в сообщении #544852 писал(а):

Предположим мы можем доказать для n=1, что утверждение верно. Дальше делаем предположение что предположение доказано для K случаев. Но это же предположение. Как основываясь на нём, можно дальше что то доказывать?

Ну, для $K=1$ мы ведь доказали? И доказали, что "из $K$ следует $K+1$"? Раз для $K=1$ верно, то и для $K=2$ верно. Раз для $K=2$ верно, то и для $K=3$ верно. Раз для $K=3$ верно, то и для $K=4$ верно. ...

[Guliashik]

Наверно вам будет проще мне объяснить на примере.
Есть варианта $x_1=\sqrt{c}, x_2=\sqrt{c+\sqrt{c}},x_3=\sqrt{c+\sqrt{c+\sqrt{c}}}$....и т.д. c>0.
Нужно найти предел данной варианты, для этого нужно доказать что она монотонная, и ограничена.
Монотонность очевидна. По поводу ограниченности, можно предположить что для некоторого n значение варианты меньше$\sqrt{c}+1$. То есть тут вроде как совсем и не предположение, а вполне очевидный факт, что для некоторого n данное неравенство верно.
По методу мат. индукции
1) База $x_1=\sqrt{c}<\sqrt{c}+1$.
2)Допустим что какое либо значение $x_n<\sqrt{c}+1$
3)$x_{n+1}<\sqrt{c+2\sqrt{c}+1}=\sqrt{c}+1$
читд.
Пример взят из Фихтенгольца.
Someone, вот для вышеприведённого примера, для меня это очевидно.
Но вот как доказать ограниченность варианты для другого примера понять не могу:
$x_1=\frac{c}{2}$
$x_{n+1}=\frac{c}{2}+\frac{x_n^2}{2}$
0<c<=1.
Объясните, пожалуйста.

[bot]

Ну для этого сначала надо догадаться, какой константой она ограничена. Попробуйте $1+\sqrt{1-c} $

[ewert]

Guliashik в сообщении #544868 писал(а):

Но вот как доказать ограниченность варианты для другого примера понять не могу:
$x_1=\frac{c}{2}$
$x_{n+1}=\frac{c}{2}+\frac{{x_n}^2}{2}$

Доказывайте, что она ограничена сверху меньшим корнем уравнения $\frac{x^2}2-x+\frac c2$. Собственно, к которому она и стремится.

(Это станет геометрически очевидным, если нарисовать на одной картинке графики $y=\frac{x^2}2+\frac c2$ и $y=x$.)

[Guliashik]

1) База $x_1=\frac{c}{2}<1+\sqrt{1-c}$ -очевидно.
2)Тогда для некоторого n неравенство $x_n=\frac{c}{2}+\frac{{x_n-1}^2}{2}<1+\sqrt{1-c}$ имеет место быть верным(для каких то первых значений очевидно).
3)$x_{n+1}=\frac{c}{2}+\frac{x_n^2}{2}$.
$x_n^2<2+2\sqrt{1-c}-c$
$\frac{x_n^2}{2}+\frac{c}{2}<1+\sqrt{1-c}$
$x_{n+1}<1+\sqrt{1-c}$.

Вроде бы чуток прояснилось.

[ewert]

Теперь попытайтесь по индукции доказать, что $x_n<1-\sqrt{1-c}$.

[Guliashik]

1)База
$\frac{c}{2}<1-\sqrt{1-c}<1$
2) Для некоторых n $x_n<1-\sqrt{1-c}$ верно.
3) $x_{n+1}=\frac{c}{2}+\frac{x_n^2}{2}<1-\sqrt{1-c}$ (выводится также как и выше).
Спасибо, стало понятнее.
Хотя по поводу первого утверждения вроде бы наврал, сейчас проверю.

[Guliashik]

Не получилось у меня доказать, что $\frac{c}{2}<1-\sqrt{1-c}$. Может надо смотреть не $x_1$, а $x_2$?

[ewert]

Там ничего вообще считать не надо, там принципиальна лишь идеология:

1) что та парабола лежит выше биссектрисы первой четверти -- пока они не пересекутся;

2) что они справа от нуля пересекутся-таки (это единственный момент, где хоть что-то надо считать);

3) что та парабола при положительных иксах возрастает;

4) что начальное приближение лежит между нулём и первой от нуля точкой пересечения.

Далее всё и геометрически очевидно, и (уж коль геометрия ясна) аналитически легко обосновывается.

[TR63]

quote=868"Guli[ashik в сообщении #544"]$x_1=\sqrt{c}, x_2=\sqrt{c+\sqrt{c}},x_3=\sqrt{c+\sqrt{c+\sqrt{c}}}$....и т.д. c>0.
Нужно найти предел данной варианты, для этого нужно доказать что она монотонная, и ограничена..[/quote]
Ограниченность здесь очевидна, если положить $\sqrt{c+x}=x$. Тогда $x_{n+1}<x$.

[TR63]

В книге "Сборник задач по математике" Л.В.Кованцева, И.Г.Малышев доказывается, что для данной последовательности существует единственный предел, равный x. А, если границу найти другим способом, например, так $\sqrt{c+{\sqrt{x}}}=x$, то будет ли она меньше указанного в книге предела? У меня получается, что меньше. Но, возможно ли такое? Может я не заметила ошибку?