Предел с суммой внутри

[Tiberium]

ИСН в сообщении #1230322 писал(а):

Это тоже надо делать в уме.

Теперь буду делать такое в уме, спасибо!

ewert в сообщении #1230332 писал(а):

И опять же: ссылка на постоянную Эйлера тупо неприлична. Достаточно того, что эта сумма очевидным образом оценивается через логарифм плюс некая константа сверху (ну или ровно с тем же успехом снизу -- в зависимости от того, чего приспичило).

Да, вот к чему приводит бездумное переписывание из Википедии. Мне была известна эта оценка, но ни разу не приходилось ее при решении использовать, поэтому неосознанно подошел к записи.

Всем большое спасибо за такие терпеливые и наводящие намеки:)

[ex-math]

А главное, что логарифм-то и не нужен совсем: часть суммы по $k\leqslant\sqrt n $ содержит не более $\sqrt n $ слагаемых, каждое из которых не больше $1$, а оставшаяся часть -- не более $n$ слагаемых, каждое из которых не больше $1/\sqrt n $. Итого, вся сумма меньше $\sqrt n $, что достаточно для получения ответа, и не нужны ни логарифмы, ни интегралы.
По-моему, из оврага это должно быть неплохо видно :)

[ewert]

Ну если уж кустарничать, то и корни не нужны. По любому $\varepsilon$ выбираем $m$ так, что из $k>m$ следует $\frac{k}{k^2+1}<\frac{\varepsilon}2$ и затем $N>m$ так, чтобы при $n>N$ выполнялось $\frac1n\sum\limits_{k=1}^m\frac{k}{k^2+1}<\frac{\varepsilon}2$. Это лучше корней, поскольку шаблонно и вообще никакого изобретательства не требует.

[ex-math]

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

[Sonic86]

(Оффтоп)

Да было бы где кустарничать:
если $P,Q$ - многочлены, $(\forall x)Q(x)\neq 0$, то:
если $\deg P < \deg Q-1$
$\sum\limits_{k=1}^n\frac{P(k)}{Q(k)} =\mathrm{const}+o(1)$
если $\deg P = \deg Q-1$
$\sum\limits_{k=1}^n\frac{P(k)}{Q(k)} \sim\ln n$
если $\deg P > \deg Q-1$
$\sum\limits_{k=1}^n\frac{P(k)}{Q(k)} \sim\frac{n^{\deg P-\deg Q + 1}}{\deg P-\deg Q + 1}$
извините за китайский код

upd: $\sum\limits_{k=a}^n\frac{P(k)}{Q(k)}\sim\int\limits_a^n\frac{P(x)}{Q(x)}dx$
Вот так без китайского кода. Дальше с интегралом работать гораздо легче.

[Null]

Это же средние арифметические стремящейся к 0 последовательности.

[Padawan]

Теорему Штольца можно еще вспомнить