Конкретная математика, задача 9.2

[caxap]

Нужно определить какая из функций растет быстрее ($n\to infty$)
b) $n^{\ln\ln\ln n}$ или $(\ln n)!$
В ответе написано $n^{\ln\ln\ln n} \prec (\ln n)! \prec n^{\ln\ln n}$, но не объяснено почему. Подскажите пож-ста, почему так?

c) $(n!)!$ или $((n-1)!)!(n-1)!^{n!}$
Я размышлял так: при больших $n$ разница между $n$ и $n-1$ незначительна, поэтому второе выражение можно записать примерно как $(n!)!n!^{n!}$, что разумеется больше первого. Но в ответе написано: "прологарифмируйте и покажите, что $(n!)!$ растет быстрее". Непонятно, как это логарифмировать и почему неверны мои рассуждения?

[ИСН]

Логарифмировать по формуле Стирлинга, в первом случае делать то же самое, а рассуждения я продолжу так: при больших $n$ совершенно стирается разница между $n$ и $n+1000$, поэтому немедленно дайте мне 1000 рублей, ведь Вам всё равно.

[caxap]

Проверьте, пожалуйста:
b) От первой функции логарифм: $\ln\ln\ln n\cdot \ln n$.
Вторая функция по формуле Стирлинга: $(\ln n)!\sim \sqrt{2\pi\ln n}\left(\dfrac {\ln n} e\right)^{\ln n}$, её логарифм:

$$\ln \sqrt{2\pi\ln n}+\ln n(\ln\ln n-\ln e)=\frac 1 2 (\ln 2\pi+\ln\ln n)+\ln n\cdot \ln\ln n-\ln n\sim \frac 1 2 \ln\ln n + \ln n\cdot \ln\ln n$$

Т.к. $\ln n\cdot \ln\ln n \succ \ln\ln\ln n\cdot \ln n$, то вторая функция растет быстрее?

И вообще идея правильная? Её же применять для второго примера? Там просто получается слишком большие выражения. Ещё там два факториала, после такого разложения первого ещё ведь и второй также надо разложить. Неужели нет путя проще? Может сравнить с другими функциями?

И самое главное: почему при $n\to \infty$ нельзя заменять $n-1$ на $n$? При решении пределов всегда так делал и с ответом всегда совпадало. Когда $n$ принимает астрономические числа типа $10^{100}$, то какое значение имеет эта единичка (или вообще константа)?

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

а рассуждения я продолжу так: при больших $n$ совершенно стирается разница между $n$ и $n+1000$, поэтому немедленно дайте мне 1000 рублей, ведь Вам всё равно.

Если бы у меня количество денег стреимилось к $\infty$, то дал бы.

[ИСН]

Действительно, какое значение может иметь 1? Ну, попробуйте вот здесь заменить так-то.
$\lim\limits_{n\to\infty}\left(1-{n-1\over n}\right)\cdot n$

[venco]

caxap в сообщении #337775 писал(а):

И самое главное: почему при $n\to \infty$ нельзя заменять $n-1$ на $n$? При решении пределов всегда так делал и с ответом всегда совпадало.

Покажите это на примере $\lim\limits_{n\to\infty}{n!\over(n-1)!}$

[ИСН]

Да, так ещё лучше.

[ShMaxG]

Или в таком: $ \[\mathop {\lim }\limits_{n \to \infty } \left( {n - 1 - n} \right)\]$

[caxap]

venco в сообщении #337781 писал(а):

Покажите это на примере $\lim\limits_{n\to\infty}{n!\over(n-1)!}$

$\infty$. Ага. Понятно. Факториал -- это же $1\cdots n$, т.е. если мы отнимем 1, то результат изменится в $n$ раз, а $n$ очень велико.
А нет ли каких нибудь общих критериев, когда можно пренебрагать константами? Ну например $\lim\limits_{n\to \infty}\dfrac {(n+10^{10})^{10}-1000n^9}{(5n+100)^{10}}=\lim\limits_{n\to \infty}\dfrac {n^{10}}{5^{10} n^{10}}=1/5^{10}$ -- здесь же можно ими пренебрегать. А как в общем случае узнать о такой возможности?

А 2-й пример как решать? И первый-то правильно решен?

[ИСН]

В общем случае надо таскать за собой о-малые и всегда помнить, чем пренебрегли.
Первый - правильно. А что до второго, то я как-то читал одну книгу, не помню автора, по стилю похоже на Урсулу Ле Гуин, может, она и есть - так там были такие маги, которые свои заклинания применяли очень экономно, потому что те были одноразовыми. Применил - и тут же забыл.

[caxap]

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

А что до второго, то я как-то читал одну книгу, не помню автора, по стилю похоже на Урсулу Ле Гуин, может, она и есть - так там были такие маги, которые свои заклинания применяли очень экономно, потому что те были одноразовыми. Применил - и тут же забыл.

Не понял
А что со вторым можно сделать? Формулу стирлинга только не надо --- там получаются слишком длинные выражения. Мне кажестся должен существовать более простой способ.

[ИСН]

Вот-вот, мне ещё тогда этот элемент сюжета показался несколько натянутым: ну как это так может быть, применил и забыл?
А нет, выходит, сюжет-то жизненный.

[ewert]

caxap в сообщении #338339 писал(а):

А что со вторым можно сделать? Формулу стирлинга только не надо

Боюсь,что без Стирлинга как-то никак -- там оценка достаточно тонкая.

Берём Стирлинга в форме: $\ln(m!)=m\ln m-m+{1\over2}\ln m+O(1)$. Тогда логарифм отношения левой части к правой -- это вот что такое:

$$n!\,\ln n!-n!+{1\over2}\ln n!-(n-1)!\,\ln (n-1)!+(n-1)!-{1\over2}\ln (n-1)!-n!\,\ln(n-1)!+O(1)=$$

$$=(n-1)!\,\Big(n\,\ln n!-n-\ln(n-1)!+1-n\ln(n-1)!\Big)+{1\over2}\ln n+O(1)=$$

$$=(n-1)!\,\Big(n\,\ln n-n-\ln(n-1)!+1\Big)+{1\over2}\ln n+O(1)=$$

$$=(n-1)!\,\Big(\ln n!-{1\over2}\ln n-\ln(n-1)!+O(1)\Big)+{1\over2}\ln n+O(1)=$$

$$=(n-1)!\,\Big({1\over2}\ln n+O(1)\Big)+{1\over2}\ln n+O(1).$$

И вот только теперь видно, что это и впрямь уходит на бесконечность.

-- Сб июл 10, 2010 13:51:42 --

Да, а первая задачка -- существенно проще. Там достаточно грубой интегральной оценки: $\ln m!\sim\int\limits_0^m\ln x\,dx= m\,\ln m-m$, а стирлинговской поправки в поллогарифма вовсе и не нужно.

[caxap]

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

Там достаточно грубой интегральной оценки: $\ln m!\sim\int\limits_0^m\ln x\,dx= m\,\ln m-m$

У вас $\ln m!=(\ln m)!$? А откуда эта интегральная оценка? Её просто надо знать?

[ewert]

caxap в сообщении #338379 писал(а):

У вас $\ln m!=(\ln m)!$?

Нет, наоборот.

caxap в сообщении #338379 писал(а):

А откуда эта интегральная оценка? Её просто надо знать?

Очень просто: из монотонности логарифма следует, что

$$\int\limits_0^m\ln x\,dx<\ln m!=\sum\limits_{k=1}^m\ln k\leqslant\int\limits_1^{m+1}\ln x\,dx$$

(сумма в центре -- это сумма площадей прямоугольников, лежащих выше подынтегральной кривой для левого интеграла и ниже для правого). А разность интегралов слева и справа есть $O(\ln m)$, т.е. много меньше каждого слагаемого в $m\,\ln m-m=\int\limits_0^m\ln x\,dx$.

[caxap]

Понятно