в конце поста https://t.me/compmathweekly/6 был вопрос без ответа, можно ли так получить асимптотически правильную (пусть с точностью до константы) оценку на факториал

а сегодня коллега Устинов всё объяснил

// дальше техническое математическое, простите

напомню контекст: e^n = …+n^n/n!+…, поэтому e^n>n^n/n! (мы оценили сумму положительных чисел самым большим слагаемым), т.е. n!>(n/e)^n

так вот, если n^n/n!=S(n), то следующий член равен S(n)/(1+1/n), т.е. больше, чем S(n)e^{-1/n}; следующий равен S(n)/(1+1/n)(1+2/n), т.е. больше, чем S(n)e^{-1/n}e^{-2/n} и т.д. — если отойти на m шагов, то получится хотя бы S(n)e^{-m(m+1)/2n}

в частности, если отойти на (как и было предсказано :) на √n шагов, то получится хотя бы с⋅S(n) (для некоторого с, не зависящего от n) — и это дает оценку e^n > √n с S(n), т.е. n! > с√n (n/e)^n

можно доказать и оценку с другой стороны:
(1+1/n)(1+2/n)…(1+m/n)>1+1/n+…+m/n>1+m²/2n, поэтому если отойти на √n шагов, то слагаемое уменьшится хотя бы в полтора раза и т.д. — получается, что n! < C√n (n/e)^n

можно вытащить и полноценную формулу Стирлинга с использованием формулы Валлиса (оценивая центральный биномиальный коэффициент)