Сумма не выразимая в замкнутом виде

[Sonic86]

$$S_n=\sum\limits_{k=1}^n\left[\frac{n}{k}\right]$$

Докажите, что для $S_n$ не может быть выражена в замкнутом виде через многочлены и кратные логарифмы (т.е. $\ln n, \ln\ln n$ и т.п.).

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

[Профессор Снэйп]

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

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

Чтобы понять, хороша задача или нет, нужно её сначала решить!

[Naf2000]

Ковыряясь пальцем в ухе - скорость роста $S_n$ выше многочлена, тем более логарифма

[Профессор Снэйп]

Naf2000 в сообщении #611614 писал(а):

Ковыряясь пальцем в ухе - скорость роста $S_n$ выше многочлена, тем более логарифма

Да ну с чего бы она была выше?

$$ S_n = \sum\limits_{k=1}^n \left[ \frac{n}{k} \right] \leqslant \sum\limits_{k=1}^n \left[ \frac{n}{1} \right] = n^2 $$

[nnosipov]

$S_n \sim n\ln{n}+(2\gamma-1)\ln{n}$, где $\gamma$ --- константа Эйлера. По-моему, задача точно не сформулирована.

[Sonic86]

nnosipov в сообщении #611617 писал(а):

По-моему, задача точно не сформулирована.

Я просто не могу нормально класс функций описать. Хочется сказать: "класс функций", имеющих асимптотику, но это не точно. Точнее - класс логарифмически-экспоненциальных функций Харди, но он сложно выглядит (там $f(x)=x\in K, f,g\in K\Rightarrow f\pm g, f\cdot g,\frac{f}{g}\in K, \ln f, \exp f \in K$ + ограничение на определенность функции на некотором луче $(a;+\infty)$, т.к. логарифм не везде определен). Потому взял класс функций, представляемых многочленами от $n,\ln n, \ln\ln n$ и т.п. над $\mathbb{R}$. Извините
Вообще, на самом деле доказательство короткое.

[nnosipov]

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

Потому взял класс функций, представляемых многочленами от $n,\ln n, \ln\ln n$ и т.п. над $\mathbb{R}$.

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

[Профессор Снэйп]

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

nnosipov в сообщении #611617 писал(а):

По-моему, задача точно не сформулирована.

Я просто не могу нормально класс функций описать.

$\mathcal{F}$ - наименьший по включению класс функций, для которого:

1) Функции $f(x) = x$ и $f(x) = \mathrm{Const}$ принадлежат $\mathcal{F}$;
2) Если $f(x), g(x) \in \mathcal{F}$, то $f(x) + g(x)$, $f(x) \cdot g(x)$ и $\ln f(x)$ принадлежат $\mathcal{F}$.

[Sonic86]

Профессор Снэйп в сообщении #611699 писал(а):

$\mathcal{F}$ - наименьший по включению класс функций, для которого:

1) Функции $f(x) = x$ и $f(x) = \mathrm{Const}$ принадлежат $\mathcal{F}$;
2) Если $f(x), g(x) \in \mathcal{F}$, то $f(x) + g(x)$, $f(x) \cdot g(x)$ и $\ln f(x)$ принадлежат $\mathcal{F}$.

Ну например так (я уж забил на избыточность описания)

[Руст]

Можно показать, что $|S_n-n\ln n -(2\gamma -1)\ln n|>n^{1/4}$ отклоняется бесконечно много раз как в одну, так и в другую сторону. Такой функции нет в указонном классе.

[Sonic86]

Руст в сообщении #611789 писал(а):

Можно показать, что $|S_n-n\ln n -(2\gamma -1)\ln n|>n^{1/4}$ отклоняется бесконечно много раз как в одну, так и в другую сторону. Такой функции нет в указонном классе.

О! А доказательство сложное?!

[Руст]

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

[Sonic86]

Ну ладно. У меня так было:
На самом деле $S_n=\sum\limits_{k=1}^n\tau (k)$, где $\tau(k)$ - число делителей числа $k$. Тогда $\tau(n)=S_n-S_{n-1}$. Если бы формула для $S_n$ существовала, то существовала бы асимптотическая формула для $\tau(n)$. Однако, для подпоследовательности простых $\tau(n)=2$ - одна асимптотика, а для $n=2^k$, например, $\tau(n)=\frac{\ln n}{\ln 2}$ - другая асимптотика, что противоречит тому, что у $S_n-S_{n-1}$ есть асимптотика.
Вот и все