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

[Ktina]

С какой скоростью возрастает эта последовательность?

$$1, 12, 123, \dots , \overline{123...n}, \dots$$

(энный член равен числу, образующемуся выписыванием десятичных записей всех натуральных от 1 до n)

Явно быстрее, чем $O(n!)$ (так как для всех $n>1$ выполняется $a_n>n!$)
Как оценить точнее?

[Mysterious Light]

(Оффтоп)

моё скромное мнение говорит:
Растёт быстрее, чем $10^n$, потому что $a_n$ содержит не менее $n$ цифр. Поскольку $O$-нотация предполагает оценку сверху, то можно более точным образом определить (сверху) количество цифр. Будет что-то в духе $O(10^{n\lg n})=O(n^n)$.
Ещё: $a_n>f(n)$ ещё не означает, что $a_n\neq O(f(n))$

[mihiv]

Асимптотику можно уточнить, а именно:

$a_n=n+(n-1)10^{[\lg n]+1}+(n-2)10^{[\lg n]+[\lg (n-1)]+2}+\dots +n!10^{[\lg n]+[\lg (n-1)]+\dots +[\lg 2]+(n-1)}<n\cdot 10^0+n(n-1)10^{1}+\dots +n!10^{n-1}<n!10^n$.

С другой стороны $a_n>n!10^{n-1}$, поэтому с учетом асимптотики $n!$ получим $a_n=O(e^{n\ln n+n(\ln10 -1)-\frac 12\ln n})$

[mihiv]

mihiv в сообщении #676393 писал(а):

С другой стороны $a_n>n!10^{n-1}$

С нижней оценкой ошибся, должно быть неравенство, которое привела Ktina : $a_n>n!$.

[ewert]

Уточним. Имеем $a_n\sim c\cdot10^{s_n}$, где $c=0,\!1234567891011121314\ldots$ и $s_n$ -- суммарная длина участвующих в построении $a_n$ чисел; для этой длины и нужны оценки. Оценка снизу получается очень просто. Пусть $n=10^m-1$; тогда

$$s_n=9+2\cdot90+3\cdot900+\ldots+m\cdot9\cdot10^{m-1}=m\cdot10^m-\dfrac{10^m-1}9=(n+1)\lg(n+1)-\dfrac{n}9\equiv s_n^-.$$

Отсюда получаем точную оценку снизу $s_n\geqslant s_n^-$ уже при всех $n$ (поскольку последовательность $s_n^-$ выпукла вниз, а последовательность $s_n$ -- кусочно линейна).

Теперь сверху. Рассмотрим участок от $n_0=10^m-1$ до $n_1=10^{m+1}-1$, на котором $s_n$ линейна. Её производная на этом участке равна $(s_n)'_n=m+1=\lg(n_0+1)+1$, т.е. на этом участке $s_n=s_{n_0}+(n-n_0)\cdot\big(\lg(n_0+1)+1\big)$. Следовательно,

$$s_n-s_n^-=\left((n_0+1)\lg(n_0+1)-\dfrac{n_0}9+(n-n_0)\cdot\big(\lg(n_0+1)+1\big)\right)-\left((n+1)\lg(n+1)-\dfrac{n}9\right)=$$

$$=(n+1)\lg\dfrac{n_0+1}{n+1}+\dfrac{10}9(n-n_0).$$

Отношение $\dfrac{s_n-s_n^-}{n+1}=\lg(n_0+1)-\lg(n+1)+\dfrac{10}9-\dfrac{10}9\cdot\dfrac{n_0+1}{n+1}$ достигает максимума при $n+1=\dfrac{10\ln10}9(n_0+1)$ и равно в этой точке $\lg\dfrac9{10\ln10}+\dfrac{10}9-\dfrac1{\ln10}=\lg\dfrac{9e}{\ln10}+\dfrac19$. Отсюда оценка сверху: $s_n<s_n^+$, где

$$s_n^+\equiv s_n^- + (n+1)\cdot\left(\lg\dfrac{9e}{\ln10}+\dfrac19\right)=(n+1)\lg(n+1)+n\lg\dfrac{9e}{\ln10}+\lg\dfrac{9e}{\ln10}+\dfrac19.$$

Это неравенство (в отличие от оценки снизу) именно строгое, однако асимптотически точное, т.е. его нельзя улучшить более чем на $O(n^{-1})$.

Окончательно:

$$\mathop{\underline{\lim}}\limits_{n\to\infty}a_n\cdot(n+1)^{-(n+1)}\cdot 10^{n/9}=0,\!12345678910111213\ldots;$$

$$\mathop{\overline{\lim}}\limits_{n\to\infty}a_n\cdot(n+1)^{-(n+1)}\cdot \left(\dfrac{9e}{\ln10}\right)^{-n}=\dfrac{9e\cdot10^{1/9}}{\ln10}\cdot 0,\!12345678910111213\ldots$$

(если нигде не напутал в арифметике).