Субаддитивная последовательность

[Ian]

Последовательность [math]x_n,\; n=1,2... удовлетворяет условию [math]0\leq x_{n+m}\leq x_n+x_m. Доказать, что [math]\frac{x_n}n сходящаяся.
Ограниченной она будет, так как [math]0\leq x_{n}\leq nx_1. Монотонной- не обязательно

[zykov]

Думаю можно рассуждать так (может и не самый элегантный способ, но зато более-менее конструктивно):

Обозначим [math]y_n=x_n/n. Тогда имеем [math]0\leq y_{n+m}\leq\frac{ny_n+my_m}{n+m}, т.е [math]y_n неотрицательно и не более чем средневзвешенное соответствующих пар.
Далее выделим для [math]k=1,2... интервалы [math]2^{k-2}\leq n \leq 2^{k-1}. Каждый элемент интервала [math]k+1 можно представить, как сумму двух элементов интервала [math]k (кроме [math]n=1).
([math]k=1: n\in\{1\};\quad k=2: n\in\{1,2\};\quad k=3: n\in\{2,3,4\};\quad k=4: n\in\{4,5,6,7,8\};\quad и т.д.)
И обозначим [math]y_{min}(k) и [math]y_{max}(k) - минимум и максимум [math]y_n в соотвествующем интервале [math]k.
Тогда для интервала [math]k+1 имеем [math]y_{max}(k+1)\leq\frac{2^{k-2}y_{min}(k)+2^{k-1}y_{max}(k)}{2^{k-2}+2^{k-1}}=\frac{y_{min}(k)+2y_{max}(k)}{3}. Отсюда в частности следует, что [math]y_{max}(k) не возрастает.

Докажем от противного, что [math]r_k=y_{max}(k)-y_{min}(k) стремится к нулю.
Очевидно, что [math]r_k\geq0. Предположим, что [math]r_k не стремится к нулю. Тогда существует [math]C>0 и бесконечная подпоследовательность [math]k(l), такие что [math]r_{k(l)}>C для всех [math]l.
Следовательно [math]y_{max}(k(l+1)) \leq y_{max}(k(l)+1) \leq \frac{y_{min}(k(l))+2y_{max}(k(l))}{3}=y_{max}(k(l))-\frac{r_{k(l)}}{3} < y_{max}(k(l))-\frac{C}{3}.
Из этого следует, что подпоследовательность [math]y_{max}(k(l)) \leq y_{max}(k(1)) - C\cdot(l-1)/3 и значит для достаточно большого [math]l будет [math]y_{max}(k(l)) < 0, но [math]y_{max}(k)\geq0. Противоречие!
Значит [math]r_k стремится к нулю.

Далее элементарно. Из того что [math]0 \leq y_{min}(k) \leq y_{max}(k), из того что [math]y_{max}(k) не возрастает и из того что [math]y_{max}(k) - y_{min}(k) стремится к нулю, следует что [math]y_{min}(k) и [math]y_{max}(k) сходятся, причем к одному пределу.
Из этого следует, что [math]y_n тоже сходится к тому же пределу.


Вот как-то так, если ничего не напутал.

PS: Некоторые промежуточные шаги пропустил, как очевидные. Если что-то не понятно, поясню отдельно.

[zykov]

Как-то у меня оно громоздко выглядит...
Если у кого есть более элегантный подход, было бы интересно взглянуть!

[zykov]

Похоже тут я накосячил:

Source of the post Тогда для интервала [math]k+1 имеем [math]y_{max}(k+1)≤\frac{2^{k−2}y_{min}(k)+2^{k−1}y_{max}(k)}{2^{k−2}+2^{k−1}}.

Минимум там не обязан появлятся. Может быть просто среднее арифметическое двух максимумов.

Так что нужно ещё думать!

[Ian]

Вот же достала задачка.
Неочевидный, но известный факт. Из субаддитивности последовательности [math]x_n следует субаддитивность [math]z_n=\frac{x_n}{1+x_n}.Но [math]z_n уже ограниченная.

[zykov]

Тут дело в минимуме. Правда не так, как я написал.
Просто это неравенство не ограничивает, насколько маленьким может стать [math]x_n.
Вот например [math]x_n растёт линейно, предел идёт скажем к 1. Но в какой -то момент ничто не мешает [math]x_n занулится дальше, и предел будет 0.
Но даже один 0 уже приводит к пределу 0. Если какой-то [math]x_n=0, то все [math]x_{kn}=0. А значения между ними не больше тех, что были до нуля - следовательно [math]x_n будет ограниченной.

[zykov]

Вот через минимум вроде получается.

Опять же обозначим [math]y_n=x_n/n и [math]y_{min}(n) - минимум [math]y_i для [math]1\leq i\leq n. Заметим, [math]y_{min}(n)\geq0 и [math]y_{min}(n) не возрастает, а значит имеет конечный предел не менее нуля. Обозначим его [math]Y_0.

Теперь докажем вспомогательную лемму о том как маленькое значение [math]y_{n_0} влияет на значения [math]y_n при [math]n>n_0. (Такое обобщение упомянутого факта про 0 на конечные значения.)
* Пусть для какого-то [math]n_0 будет [math]x_{n_0}=k\cdot n_0, где [math]k=y_{n_0}. И пусть [math]m равен максимуму [math]x_n для [math]1\leq n \leq n_0.
Тогда:
1) [math]x_{i \cdot n_0} \leq i \cdot x_{n_0} = i \cdot k \cdot n_0 = k \cdot (i\cdot n_0)
2) Для всех [math]n будет [math]x_n \leq m + k \cdot (\lfloor {\frac{n}{n_0}} \rfloor \cdot n_0) \leq m + k\cdot(n+n_0)=(m+k\cdot n_0)+k\cdot n. Отсюда следует, что для любого [math]\epsilon >0 и для достаточно больших [math]n будет [math]y_n \leq k + \epsilon = y_{n_0} + \epsilon.
Таким образом любое маленькое [math]y_{n_0} ограничивает величину [math]y_n для больших [math]n.


Из этой леммы легко доказать, что [math]y_n стремится к [math]Y_0.
Для любого [math]\epsilon>0 существует [math]N, такое что для всех [math]n\geq N будет [math]Y_0 \leq y_{min}(n) <Y_0+\epsilon.
Значит в силу леммы существует [math]N_1, такое что для всех [math]n \geq N_1 будет [math]Y_0 \leq y_n < (Y_0+\epsilon)+\epsilon=Y_0+2\epsilon.


Вот как-то так. Вроде на этот раз не ошибся. Выглядит довольно прозрачно.

[Ian]

Спасибо, Вы доказали. Что имел преподаватель, задавший задачу на матанализе, хорошее доказательство или с ошибкой, узнать уже невозможно, никто из студентов не придумал ничего. Но вроде в это время шла тема сжимающих отображений, остальные задачки из серии были про это(

[Ian]

Что имел преподаватель, задавший задачу на матанализе, хорошее доказательство или с ошибкой, узнать уже невозможно

Узнал. Это задача из задачника Кудрявцева т.1 стр 166, N267. Каких-то указаний по решению -в ответах нет, но раз задача есть в задачнике, можно задавать студентам, и не прорешивая. И действительно доказательство Zykov -самое простое что тут может быть, идея деления номеров с остатком один на другой всегда присутствует. Еще раз спасибо

[Ian]

Подберите формулу n-ого члена последовательности, если последовательность возрастающая и состоит из всех трёхзначных чисел, сумма цифр которых равна 24.

Зы: Я смог найти члены последовательности, но кто поможет подобрать формулу, если это возможно ? Спасибо.

[math]692+9n+\left[\frac{n+10}{12}\right]\cdot 81\left[\frac{n+10}{14}\right]\cdot 72\left[\frac{n+10}{17}\right]\cdot 63=
(699,789,798,879,888,897,969,978,987,996). Эти три квадратных скобки скачут от 0 до 1 при n=2,4 и 7 соответственно, при других n скачки по 9, при [math]n>10 формула начинает выдавать числа большие 1000 которые не относятся к делу. Только зачем формула, множество можно описать его свойством (сумма цифр) или перечислением, это не хуже.