доказать неравенство n^k < m^n при n -> oo

[shust]

Элементарным путем, не пользуясь средствами матанализа доказать или указать, где можно найти доказательство, утверждения о том ,что для заданных натуральных k, m и всех натуральных n, большего некоторого натурального N, верно неравенство:
$n^k < m ^ n$ $,
говорящее о том, что показательная функция растет быстрее, чем степенная при стремлении аргумента к бесконечности,т.е. при условии,
$n\to \infty$.

[Brukvalub]

Представьте $ m ^ n =((m-1)+1)^ n$ и бином Ньютона Вам в помощь.

[Руст]

Логарифмируйте.

[shust]

Руст писал(а):

Логарифмируйте.

Не очень здорово, т.к. сводим к аналогичной задаче: доказать неравенство
$k\log n < n\log m$ $,
аналогичной сложности, даже более сложной, т.к. вводится трансцендентная в общем случае
функция $\log n $.

Исходная задача в силу монотонности степенной функции сводится к более простой
$n^k < 2 ^ n$ $.

Частный ее случай $n < 2 ^ n$ $
индукцией по $n $ доказывается совсем просто.

Надо доказать
$n^k < 2 ^ n$ $,
не используя логарифмов и корней.

[Андрей123]

Можно доказать по индукции. Для этого надо будет доказать, что начиная с некоторого N $(1+1/n)^k<2$, что,по-моему, просто.

[Руст]

shust писал(а):

Не очень здорово, т.к. сводим к аналогичной задаче: доказать неравенство
$k\log n < n\log m$ $,
аналогичной сложности, даже более сложной, т.к. вводится трансцендентная в общем случае
функция $\log n $.

Всё тривиально, неравенство выполняется при $n>max(e,N), \ \frac{N}{ln N}=\frac{k}{ln m}$ (функция x/ln x монотонно растущая при x>e ).

[shust]

Андрей123 писал(а):

Можно доказать по индукции. Для этого надо будет доказать, что начиная с некоторого N $(1+1/n)^k<2$, что,по-моему, просто.

Доказать верность индукционнго шага, согласен, просто.
Но как доказать верность базы индукции, т.е. показать, что
$n^k < 2 ^ n$ $
выполняется хотя бы при каком то значении $n=N $,
которое , естественно должно зависить от $k $, а $k $
может быть очень большим?

Добавлено спустя 26 минут 41 секунду:

Руст писал(а):

shust писал(а):

Не очень здорово, т.к. сводим к аналогичной задаче: доказать неравенство
$k\log n < n\log m$ $,
аналогичной сложности, даже более сложной, т.к. вводится трансцендентная в общем случае
функция $\log n $.

Всё тривиально, неравенство выполняется при $n>max(e,N), \ \frac{N}{ln N}=\frac{k}{ln m}$ (функция x/ln x монотонно растущая при x>e ).

У меня была просьба:
Надо доказать неравенство при n -> oo
$n^k < 2 ^ n$ $,
не используя логарифмов, корней и, по возможности, с использованием только целых или в крайнем случае рациональных чисел.

[Brukvalub]

shust писал(а):

У меня была просьба:
Надо доказать неравенство при n -> oo
$n^k < 2 ^ n$ ,
не используя логарифмов, корней и, по возможности, с использованием только целых или в крайнем случае рациональных чисел.

Я уже писал Вам: $ 2 ^ n=(1+1)^ n $, раскладываете правую часть равенства по биному Ньютона, при больших n один из биномиальных коэффициентов будет многочленом от n степени выше к, а уж сравнить скорости роста многочленов разной степени элементарными методами-это элементарно

[shust]

Brukvalub писал(а):

Я уже писал Вам: $ 2 ^ n=(1+1)^ n $, раскладываете правую часть равенства по биному Ньютона, при больших n один из биномиальных коэффициентов будет многочленом от n степени выше к, а уж сравнить скорости роста многочленов разной степени элементарными методами-это элементарно

Согласен с Вами.

Я, правда, использовал разложение по биному Ньютона
эквивалентного неравенства
$n < m ^n^/^k$ $
и ограничился только третьим членом разложения, отбросив остальные.
При этом получается простая оценка для числа N, такого, что при всех n > N верно
$n^k < m ^ n$ $.

[RIP]

shust писал(а):

Надо доказать неравенство при n -> oo
$n^k < 2 ^ n$ ,
не используя логарифмов, корней...

И потом сами же пишете

shust писал(а):

Я, правда, использовал разложение по биному Ньютона
эквивалентного неравенства
$n < m ^n^/^k$

[shust]

RIP писал(а):

shust писал(а):

Надо доказать неравенство при n -> oo
$n^k < 2 ^ n$ ,
не используя логарифмов, корней...

И потом сами же пишете

shust писал(а):

Я, правда, использовал разложение по биному Ньютона
эквивалентного неравенства
$n < m ^n^/^k$

Это не противоречит моей просьбе т.к. я доказал неравенство
$n < m ^ n^/^k$ $
раньше(вчера), чем попросил(сегодня) доказать неравенство без использования логарифмов и корней т.к.
хотелось бы не использовать сложные понятия, а использовать только степени - что явно проще.
Кстати для меня оказалось, что доказать неравенство с использованием только степеней
оказалось несколько сложнее, чем с использованием корней.

[Андрей123]

Цитата:

Но как доказать верность базы индукции, т.е. показать, что
$n^k < 2 ^ n$ $
выполняется хотя бы при каком то значении $n=N $,
которое , естественно должно зависить от $k $, а $k $
может быть очень большим?

Можно доказать, что каково бы ни было натуральное p найдётся натуральное M>p такое, что
$M^k < 2 ^ M$ $. Это можно сделать, например, ища M в виде
$2^l$. Для l получим неравенство $lk<2^l$, которое выполняется при всех l>2k+1. Тогда $ M=max(2^{2k+2},2^t)$, где $ 2^t>p$, . Взяв вместо p номер, начиная с которого выполняется $(1+1/n)^k<2$, можно получить требуюмую базу индукции.

[shust]

Андрей123.
Переосмысление вашей реплики позволило упростить ранее приведенное мною доказательство неравенства.
Если n представить в виде $n = 2 ^ l$, то доказательство неравенства $n^k < 2 ^ n$, сводится к доказательству
неравенства $lk < 2 ^ l$, а оно верно при $l > 2k+1, что доказывается разложением $ 2 ^ n$, по биному Ньютона и удержанием 3-го члена.
Таким образом, при всех n , удовлетворяющих условию $n > 2 ^2^k^+^1 $,
имеет место неравенство $n^k < 2 ^ n$, а тем более и исходное неравенство
$n^k < m ^ n$. Не надо никакой индукции!
Хочу отметить, что доказательство не использует ни логарифмов, ни корней,
а только целые числа и их степени, как и доказуемое неравенство.
Неясно можно ли еще упростить доказательство и улучшить полученную
оценку для N или это противоречивые требования?

[Андрей123]

shust писал(а):

Таким образом, при всех n , удовлетворяющих условию $n > 2 ^2^k^+^1 $,
имеет место неравенство $n^k < 2 ^ n$, а тем более и исходное неравенство
$n^k < m ^ n$. Не надо никакой индукции!

По-моему, мы доказали неравенство только для n вида $2^l$, а не для всех n, поэтому индукция всё-таки нужна.

[shust]

Андрей123 писал(а):

shust писал(а):

Таким образом, при всех n , удовлетворяющих условию $n > 2 ^2^k^+^1 $,
имеет место неравенство $n^k < 2 ^ n$, а тем более и исходное неравенство
$n^k < m ^ n$. Не надо никакой индукции!

По-моему, мы доказали неравенство только для n вида $2^l$, а не для всех n, поэтому индукция всё-таки нужна.

В варианте $l= 2 ^ n$, l - целое, индукция, пожалуй нужна.

Но ничто не мешает взять за l - нецелое вида
$l= \log _2 n$.
Все рассуждения мои остаются в силе, за исключением фразы о неиспользовании логарифмов и корней.
Однако оценка $n > 2 ^2^k^+^1 $, впрочем, их не содержит.