Демидович. Доказать существование предела

[Ivan_B]

137. Пусть числовая последовательность $x_1, x_2, \dots, x_n, \dots$ удовлетворяет условию $0\leqslant x_{n+m}\leqslant x_n+x_m$, ($m, n=1, 2, \dots$).
Доказать, что $\lim\limits_{n\to\infty}\frac{x_n}{n}$ существует.

Можно показать, что $0\leqslant x_n\leqslant nx_1$ и что $x_n\leqslant \max\limits_{i<n}x_i + \min\limits_{i<n}x_i$, но это ничего не дает.

Предположить что предела нет и $\varliminf\limits_{n\to\infty}\frac{x_n}{n}=a$ $\varlimsup\limits_{n\to\infty}\frac{x_n}{n}=b$
Тогда можно подобрать $i, k$ такие что
$\frac{x_i}{i}<a+\varepsilon$, $\frac{x_k}{k}<b+\varepsilon$ и $\frac{x_{i+k}}{i+k}>b-\varepsilon$
Откуда $(b-\varepsilon)(i+k)<x_{i+k}\leqslant x_i+x_k<(a+\varepsilon)i+(b+\varepsilon)k$
$b(i+k)<ai+bk+2\varepsilon(i+k)$
$(b-a)i<2\varepsilon(i+k)$
$b-a<2\varepsilon\frac{i+k}{i}$
Тоже ничего не дает.

[vpb]

Эта задача весьма поучительна (само утверждение называется леммой Фекете). Попытайтесь все-таки сами порешать, часов несколько. Если совсем в тупик зайдете --- под спойлером совет.

(совет)

Докажите такое утверждение: если существует $m$ такое, что $x_m=Am$, где $A$ --- некоторое число, то непременно $\overline\lim_{n\to \infty}x_n/n\leq A$.

[Ivan_B]

Пусть $y_n=\frac{x_n}{n}$. Тогда $y_{in+j}\leqslant\frac{1}{in+j}\left(\left(\left(i-1\right) n+j\right)y_{(i-1)n+j}+ny_n\right)\leqslant$$\frac{1}{in+j}\left(\left(\left(i-2\right) n+j\right)y_{(i-2)n+j}+2ny_n\right)\leqslant$$\frac{1}{in+j}\left(\left(\left(i-k\right) n+j\right)y_{(i-k)n+j}+kny_n\right)\leqslant$$\frac{1}{in+j}\left(jy_j+iny_n\right)$
Получается, что верхняя граница для подпоследовательности вида $y_{in+j}$ приближается к $y_n$ сколь угодно близко.
По индукции $x_1\leqslant x_1$ и $x_i\leqslant ix_1 \Rightarrow 0\leqslant x_{i+1}\leqslant x_i+x_1\leqslant (i+1)x_1$
Тогда $0\leqslant y_i \leqslant x_1$ и $y_i$ имеет точную нижнюю границу $y$, которая и будет пределом последовательности $y_i$:
Пусть для некоторого $n$ выполнено $y_n-y\leqslant\varepsilon$, по доказанному $y_n+\varepsilon > y_{in+j}$ Тогда $y+2\varepsilon>y_{in+j}$
Проверьте, пожалуйста, все ли верно.

[vpb]

Да, в основном правильно. Однако: фразу

Ivan_B в сообщении #1320203 писал(а):

Получается, что верхняя граница для подпоследовательности вида $y_{in+j}$ приближается к $y_n$ сколь угодно близко

следует заменить на "Отсюда следует, что верхний предел подпоследовательности $y_{in+j}$ не превосходит $y_n$, для любого $j=0,1,\ldots, n-1$".

Ivan_B в сообщении #1320203 писал(а):

по доказанному $y_n+\varepsilon > y_{in+j}$

надо добавить "для каждого $j$ и всех достаточно больших $i$". И еще несколько поправок того же типа. То есть, надо не пропускать всякие логические связки и т.д.

[Ivan_B]

Еще одна попытка:
По индукции докажем $x_{in+j}\leqslant ix_n+x_j$: По условию $x_{n+j}\leqslant x_n+x_j$ и $x_{(i+1)n+j}\leqslant x_n+x_{in+j} \leqslant (i+1)x_n+x_j$
$x_{in+j}\leqslant ix_n+x_j \Rightarrow \frac{x_{in+j}}{in+j} \leqslant \frac{ix_n+x_j}{in+j}$
Тогда будет верно и неравенство $\varlimsup\limits_{i\to\infty}\frac{x_{in+j}}{in+j} \leqslant \varlimsup\limits_{i\to\infty}\frac{ix_n+x_j}{in+j}$
$\varlimsup\limits_{i\to\infty}\frac{ix_n+x_j}{in+j}=\lim\limits_{i\to\infty}\frac{x_n+\frac{x_j}{i}}{n+\frac{j}{i}}=\frac{x_n}{n}$
Пусть $y_n=\frac{x_n}{n}$, тогда $\varlimsup\limits_{i\to\infty}y_{in+j}\leqslant y_n$
Любое $k\geqslant n$ можно представить в виде $k=in+j$, $j=0,1,\dots n-1$. Поэтому последовательность $y_k$ можно разделить на $n$ подпоследовательностей вида $y_{in+j}$ для каждой из которых верно $\varlimsup\limits_{i\to\infty}y_{in+j}\leqslant y_n$. Тогда будет верно и $\varlimsup\limits_{k\to\infty}y_{k}\leqslant y_n$
По условию $x_n\geqslant 0$, тогда $y_n\geqslant 0$, тогда последовательность $y_n$ имеет точную нижнюю границу $y$.
Тогда $\forall \varepsilon>0\;\exists n\; (y_n<y+\varepsilon)$
Из $\varlimsup\limits_{k\to\infty}y_{k}\leqslant y_n$ следует $\exists k \sup\limits_{i\geqslant k}y_i<y_n+\varepsilon$, тогда $\forall i>k\; y_i<y_n+\varepsilon<y+2\varepsilon$
Тогда $\forall \varepsilon>0\;\exists k\;\forall i>k\; y\leqslant y_i <y+2\varepsilon$

[vpb]

Чтоб я так жил! (как говорят в Одессе)

[vpb]

Я имел в виду "очень хорошо!". Гугл, однако, сказал, что это выражение означает любую сильную эмоцию вообще, так что уточняю, на всякий случай.

[Ivan_B]

vpb
Спасибо огромное за Ваши подсказки и замечания!

[ilyav]

Простите, что занимаюсь воскрешением.

Недавно сам долго, мучительно и безуспешно решал эту задачу.
После этого прорешал все задачи из Демидовича на последовательности до нее и с новой интуицией опять взялся и опять не нашел решения.
Сдался и нашел решение на этом форуме, интуицию этого решения уже удалось более менее осознать.

Я так понимаю задача позиционируется как стандартная для решения первокурснику и не считается особо сложной.
Вопрос тем, кто самостоятельно решил эту задачу: подскажите, пожалуйста, как развивалась интуиция, чтобы прийти к решению? На что он обратил внимание, какую картинку удалось увидеть, какая здесь естественная цепочка выводов, которая приводит к решению? Или может решение вообще можно увидеть почти сразу без исследования, просто я не очень умный или мало задач решал?

Буду благодарен за любые мнения

[vpb]

ilyav в сообщении #1498476 писал(а):

Я так понимаю задача позиционируется как стандартная для решения первокурснику и не считается особо сложной.

Не такая уж она стандартная, но и не особо сложная, примерно как и те задачи, которые в задачнике с ней рядом находятся.

ilyav в сообщении #1498476 писал(а):

Вопрос тем, кто самостоятельно решил эту задачу: подскажите, пожалуйста, как развивалась интуиция, чтобы прийти к решению?

Одним словом: постепенно. Она развивалась постепенно.

ilyav в сообщении #1498476 писал(а):

Или может решение вообще можно увидеть почти сразу без исследования,

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

Решайте задачи, всякие разные, особенно не тупо счетные, а где подумать и доказать надо, может и разовьется интуиция.
Есть такой учебник Решетняка, там много таких нетривиальных задачек, в конце глав. И книжки читайте, подробные и расслабленные, типа Фихтенгольца, осмысливайте ход рассуждений в этих книжках, тоже очень полезно.

[novichok2018]

Все доказательства примерно одинаковые, чётко написанное короткое нашёл здесь:
https://www.comm.utoronto.ca/frank/note ... tivity.pdf
предел равен инфинимуму отношения. Парный результат для супераддитивных последовательностей есть, например, здесь, как и интересные приложения:
https://arxiv.org/pdf/2010.09896v1.pdf
Не удержусь рассказать байку про Фекете, хотя здесь многие лекции Саймона по истории математики знают. У знаменитого Шварца (по-немецки чёрный) был тоже знаменитый ученик Вайсманн (по немецки белый человек). Фамилия то светлая, но во времена нацизма не очень котировалась. И ученик изменил фамилию на Фейер (по-венгерски белый). Господь видно проходил (пролетал) где-то рядом, увидел краем глаза, и замкнул эту цепочку - у Фейера был ученик Фекете, по-венгерски чёрный.

[novichok2018]

И ещё: неужели этот предел нельзя вывести по теореме Штольца? Было бы интересно.

[Flood]

novichok2018
Не подскажите, что это за лекции по истории математики, которые Вы упомянули?

[novichok2018]

Эти лекции Саймон читает несколько последних лет. Пишите в личку, постараюсь найти и выслать.

[Flood]

А если рассуждать так:
Пусть $y_n = \frac{x_{n}}{n}$
Тогда $0 \leq y_n \leq x_1$, следовательно последовательность $y_n$ ограниченная. Рассмотрим разность $y_{n+1} - y_{n}$.
$y_{n+1} - y_{n} = \frac{x_{n+1}}{n+1}-\frac{x_{n}}{n} = \frac{n(x_{n+1}-x_{n})-x_n}{n(n+1)} \leq \frac{nx_{1}-x_n}{n(n+1)}$
$\frac{nx_{1}-x_n}{n(n+1)} \leq \frac{nx_{1}}{n(n+1)} \leq \frac{nx_{1}}{n^2}$

Начиная с достаточно большого $n$ последовательность $y_{n}$ монотонно убывает. Где тут ошибка?