|
Как доказывать такие неравенства, как $%(n!)^2>n^n$%, по индукции? задан 12 Окт '14 23:14 
student |
|
Доказывать можно по-разному. Главное здесь -- не принцип технического оформления, а суть используемых оценок. Данное неравенство является достаточно грубым, поэтому его можно доказать совсем просто. Если мы запишем $%n!^2$% как $%(1\cdot n)\ldots(k\cdot(n+1-k))\ldots(n\cdot1)$%, то легко заметить, что все сомножители получаются не меньше $%n$%, поскольку при $%k$% от $%1$% до $%n$% разность $%k(n+1-k)-n$% равна $%(k-1)(n-k)$%, и потому неотрицательна. Значит, произведение не меньше $%n^n$%. Рассуждение при помощи индукции тоже возможно, но там возникнет что-то, связанное с числом $%e$%, а это само по себе нечто более сложное. Индукция неплохо работает при доказательстве неравенства $%n! > (\frac{n}e)^n$%, которое при больших значениях $%n$% является гораздо более сильным. отвечен 12 Окт '14 23:42 
falcao Я думаю здесь уместно более строгое доказательство с использованием индукции. А через формулу Стирлинга можно доказать или нет?
(13 Окт '14 2:37)
night-raven
1
@void_pointer: принцип индукции является одной из главных аксиом арифметики, и он неизбежно используется почти во всех рассуждениях. Без него не определить даже сумму двух натуральных чисел, не говоря об остальном. Многие доказательства используют это всё в неявной форме, но от этого они не становятся нестрогими. Формула Стирлинга -- это намного более сильный факт, и она существенно сложнее доказывается. Хотя чуть более слабые утверждения в виде неравенств можно получить в рамках школьных знаний элементарного уровня.
(13 Окт '14 2:47)
falcao
|
|
Возьмем логарифм с обеих сторон: $${(n!)^2} > {n^n} \Leftrightarrow 2\log n! > n\log n$$ Докажем по индукции $$\log n! \geqslant \frac{1}{2}n\log n,\,\,\,\,\,\forall n \geqslant 2$$ База индукции: $$n = 2 \Leftrightarrow {\log _2}2! = 1 \geqslant \frac{1}{2} \cdot {\text{2}} \cdot {\text{lo}}{{\text{g}}_2}{\text{2 = 1 ВЕРНО}}$$ Индукционная гипотеза: $$\log ((n - 1)!) \geqslant \frac{1}{2}(n - 1)\log (n - 1)$$ Имеем: $$\log n! = \log (n \cdot (n - 1)!) = \log n + \log ((n - 1)!) \geqslant \log n + \frac{1}{2}(n - 1)\log (n - 1)$$ Теперь нам нужно показать, что $%\log (n - 1) \geqslant \log n - \varepsilon $% для очень маленьких значений эпсилона. Для доказательства константы $%\varepsilon $% не достаточно, нужно что-то порядка $%\frac{1}{n}$%. Воспользуемся разложением в ряд Тейлора $%{e^x}$%: $${e^x} = 1 + \frac{x}{{1!}} + \frac{{{x^2}}}{{2!}} + \frac{{{x^3}}}{{3!}} + \ldots $$ Следовательно, для любого $%x > 0$%, получим $%{e^x} > 1 + x$%. Подставив $%\frac{1}{{n - 1}}$% вместо $%x$%, имеем $%{e^{\frac{1}{{n - 1}}}} > 1 + \frac{1}{{n - 1}} = \frac{n}{{n - 1}}$%. Возьмем логарифм с обеих сторон: $$\frac{1}{{n - 1}}\log e > \log \frac{n}{{n - 1}} \Leftrightarrow \log (n - 1) > \log n - \frac{{\log e}}{{n - 1}}$$ Подставим полученное значение в $$\log n! = \log (n \cdot (n - 1)!) = \log n + \log ((n - 1)!) \geqslant \log n + \frac{1}{2}(n - 1)\log (n - 1)$$ $$\eqalign{ & \log n! \geqslant \log n + \frac{1}{2}(n - 1)\log (n - 1) \cr & \,\,\,\,\,\,\,\,\,\,\,\, > \log n + \frac{1}{2}(n - 1)(\log n - \frac{{\log e}}{{n - 1}}) = \log n + \frac{1}{2}(n - 1)\log n - \frac{1}{2}\log e \cr & \,\,\,\,\,\,\,\,\,\,\, = \frac{1}{2}n\log n + \frac{1}{2}\log n - \frac{1}{2}\log e \cr} $$ Теперь достаточно показать, что $$\frac{1}{2}\log n - \frac{1}{2}\log e \geqslant 0 \Leftrightarrow \log n \geqslant \log e \Leftrightarrow n \geqslant e$$ Последнее неравенство выполняется для всех $%n \geqslant 3$%, отсюда следует что, $$\log n! \geqslant \frac{1}{2}n\log n.$$ Это доказывает индукционный шаг. отвечен 13 Окт '14 2:20 
night-raven @void_pointer: при доказательстве по индукции можно не логарифмировать, а основываться на том, что из $%k!^2\ge k^k$% выводится $%(k+1)!^2\ge(k+1)^{k+1}$% на основе известного неравенства $%(1+\frac1n)^n < e$%. Это работает при $%k+1 > e$%.
(13 Окт '14 2:31)
falcao
|
Я забыл отметить, что строгое неравенство верно только при $%n\ge3$%, а в общем случае его нужно заменить на нестрогое.