2014 dxdy logo

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

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




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

 
 
 
 
Сообщение27.01.2007, 14:45 
Аватара пользователя
Представьте $ m ^ n =((m-1)+1)^ n$ и бином Ньютона Вам в помощь.

 
 
 
 
Сообщение27.01.2007, 15:14 
Логарифмируйте.

 
 
 
 
Сообщение28.01.2007, 14:32 
Руст писал(а):
Логарифмируйте.

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

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

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

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

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

 
 
 
 
Сообщение28.01.2007, 16:08 
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 ).

 
 
 
 
Сообщение28.01.2007, 19:05 
Андрей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$     $,
не используя логарифмов, корней и, по возможности, с использованием только целых или в крайнем случае рациональных чисел.

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

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

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


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

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

 
 
 
 
Сообщение28.01.2007, 20:35 
Аватара пользователя
shust писал(а):
Надо доказать неравенство при n -> oo
$n^k < 2 ^ n$ ,
не используя логарифмов, корней...

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

 
 
 
 
Сообщение28.01.2007, 21:34 
RIP писал(а):
shust писал(а):
Надо доказать неравенство при n -> oo
$n^k < 2 ^ n$ ,
не используя логарифмов, корней...

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

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

 
 
 
 
Сообщение28.01.2007, 23:18 
Цитата:
Но как доказать верность базы индукции, т.е. показать, что
$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$, можно получить требуюмую базу индукции.

 
 
 
 
Сообщение30.01.2007, 21:47 
Андрей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 или это противоречивые требования?

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

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

 
 
 
 
Сообщение31.01.2007, 21:49 
Андрей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 $, впрочем, их не содержит.

 
 
 [ Сообщений: 15 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group