Формально докажите, что n ^ n есть Ω (n!)

Question

Используя формальное определение: f (n) = Ω (g (n)), если существует постоянная 'C' такая, что f (n)> = cg (n), где C> 0 и n приближается к бесконечности. Когда я показывал это неформально, я смог через график увидеть, что это утверждение верно. Однако я не уверен, как это показать формально. Любая помощь будет оценена

Answer 1

Если вам нужно формальное доказательство, вы можете по индукции доказать, что n ^ n> n! для любого n> 1.

Базовый случай состоит в том, что 2 ^ 2> 2! (так как 4> 2). Шаг индукции состоит в том, что n! = n (n-1)!