2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.



Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Факториал растёт быстрее любого многочлена. Как доказать?
Сообщение13.11.2015, 05:52 
Аватара пользователя


21/09/12

1871
Утверждение это известно: "Факториал ... растёт быстрее, чем многочлен любой степени" (Википедия, "Факториал") и интуитивно понятно.
Но вот доказательства найти не смог.
Мои попытки решения конструктивно ограничились следующим приёмом:
Если прологарифмировать обе величины (в многочлене оставляем только высшую степень $k$), то получаем довольно нетривиальное выражение:
$\ln(1)+\ln(2)+\ln(3)+...+\ln(n)>k\ln(n)$, начиная с некоторого $n$.
Что дальше делать, не представляю.

 Профиль  
                  
 
 Re: Факториал растёт быстрее любого многочлена. Как доказать?
Сообщение13.11.2015, 06:26 
Заслуженный участник


25/02/08
2961
atlakatl
Ну так оцените левую часть интегралом и всё

 Профиль  
                  
 
 Re: Факториал растёт быстрее любого многочлена. Как доказать?
Сообщение13.11.2015, 06:55 
Аватара пользователя


21/09/12

1871
Ms-dos4
Можно поподробнее?
Оценить, - это ж проинтегрировать последний член?
Получаем слева
$n\ln(n)-n$
Справа
$k\ctod (n\ln(n)-n)$
Легче не стало.

 Профиль  
                  
 
 Re: Факториал растёт быстрее любого многочлена. Как доказать?
Сообщение13.11.2015, 07:17 
Заслуженный участник
Аватара пользователя


08/11/11
5940
Воспользуйтесь неравенством $n!\ge(n/2)^{n/2}$.

 Профиль  
                  
 
 Re: Факториал растёт быстрее любого многочлена. Как доказать?
Сообщение13.11.2015, 07:19 
Заслуженный участник


26/10/14
380
Новосибирск
atlakatl в сообщении #1072890 писал(а):
Оценить, - это ж проинтегрировать последний член?

Нет, это вспомнить, что интеграл - площадь подграфика, нарисовать график логарифма от точки $0$ до $n$ и подумать, почему площадь подграфика на этом участке (он же интеграл) меньше суммы в левой части.

 Профиль  
                  
 
 Re: Факториал растёт быстрее любого многочлена. Как доказать?
Сообщение13.11.2015, 07:29 
Аватара пользователя


21/09/12

1871
g______d
Ваше выражение - для меня - тоже надо доказывать.
NSKuber
Считаю, что моё понятие "оценки" гораздо ближе к традиционному.
То, что Вы предложили, тривиально отсылает к картинке и "подумать". Распишите продолжение, если считаете, что я неправ.

 Профиль  
                  
 
 Re: Факториал растёт быстрее любого многочлена. Как доказать?
Сообщение13.11.2015, 07:32 
Заслуженный участник
Аватара пользователя


08/11/11
5940
atlakatl в сообщении #1072897 писал(а):
Ваше выражение - для меня - тоже надо доказывать.


Посмотрите на последние $n/2$ множителей.

 Профиль  
                  
 
 Re: Факториал растёт быстрее любого многочлена. Как доказать?
Сообщение13.11.2015, 07:32 
Заслуженный участник


25/02/08
2961
atlakatl
Вообще-то, я имел ввиду, что $\[\sum\limits_{k = 1}^n {\ln k}  \approx n\ln n - n\]$, а справа то интегрировать ничего не нужно. Отсюда сразу и имеем ответ.

 Профиль  
                  
 
 Re: Факториал растёт быстрее любого многочлена. Как доказать?
Сообщение13.11.2015, 07:41 
Заслуженный участник


26/10/14
380
Новосибирск
atlakatl в сообщении #1072897 писал(а):
То, что Вы предложили, тривиально отсылает к картинке и "подумать".

А вы что, пришли сюда, чтобы вам на тарелочке полное решение принесли? Тут обычно лишь подталкивают в нужном направлении, а "подумать", увы, надо самому.
atlakatl в сообщении #1072897 писал(а):
Распишите продолжение, если считаете, что я неправ.

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

 Профиль  
                  
 
 Re: Факториал растёт быстрее любого многочлена. Как доказать?
Сообщение13.11.2015, 07:49 
Аватара пользователя


21/09/12

1871
Ms-dos4
Понял. Т.е. интегралом мы заменяем сумму ряда. Правой части оставаться той же ничего не мешает.
Теперь порядок. $k$ константа, а $n$ растёт, сколько угодно.
Спасибо.

 Профиль  
                  
 
 Re: Факториал растёт быстрее любого многочлена. Как доказать?
Сообщение13.11.2015, 08:15 
Заслуженный участник


11/05/08
32166
atlakatl в сообщении #1072886 писал(а):
Если прологарифмировать обе величины

-- то, значит, больше заняться нечем. Что показательная функция растёт быстрее многочлена -- надеюсь, известно? и понятно, почему?

По ссылке в Вике, кстати, написана какая-то нелепость: дескать, $e^{e^n}$ растёт ещё быстрее. Они б ещё с десяток экспонент навесили.

 Профиль  
                  
 
 Re: Факториал растёт быстрее любого многочлена. Как доказать?
Сообщение13.11.2015, 08:22 
Аватара пользователя


21/09/12

1871
ewert в сообщении #1072907 писал(а):
значит, больше заняться нечем

Именно это "занятие" дало доказательство.
ewert в сообщении #1072907 писал(а):
показательная функция растёт быстрее многочлена -- надеюсь, известно? и понятно, почему?

Понятно. Это другой подход к доказательству?

 Профиль  
                  
 
 Posted automatically
Сообщение13.11.2015, 09:24 


20/03/14
12041
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);
- отсутствуют собственные содержательные попытки решения задач(и).

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

 Профиль  
                  
 
 Posted automatically
Сообщение13.11.2015, 10:23 


20/03/14
12041
 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

 Профиль  
                  
 
 Re: Факториал растёт быстрее любого многочлена. Как доказать?
Сообщение13.11.2015, 15:46 
Заслуженный участник
Аватара пользователя


30/01/06
72407
Я тоже "решающий", не знаю как доказать, поэтому прошу проверить моё решение:

    (топикстартеру не подсматривать)

    1. Выберем такое $m,$ что $\ln(m)=k$ (точнее, $\lfloor\ln(m)\rfloor=k$), и будем брать $n>m.$ Тогда
        $\mathrm{l.\ h.\ s.}>(n-m)k\stackrel{?}{>}k\ln{n}.$
    2. Теперь, достаточно выбрать $n$ достаточно большим, чтобы $n-m\text{ было }>\ln{n}.$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 32 ]  На страницу 1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group