2014 dxdy logo

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

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




 
 Док-во, простые числа.
Сообщение03.03.2013, 22:55 
Как доказать, что ...

1) $\displaystyle\prod_{i=1}^{k}p_i\;\;<4^n$, причем $p_k\leqslant n\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;(*)$

2) Для $\dfrac{2n}{3}<p<n$ число $C_{2n}^n$ не кратно $p$?

1) Пробовал индукцию. a) База $n=3$. Выполняется.

б) Предположим, что $(*)$ выполняется для $n=m$. Проверим, будет ли тогда выполняться для $n=m+1$.

Случай $p_{m+1}\ne m+1$ автоматически подходит, так как

$\displaystyle\prod_{i=1}^{k}p_i\;\;<4^m<4^{m+1}$ при $p_k\leqslant n$

Если же $m+1=p_{m+1}$, то тут не знаю -- как поступить, кроме как домножить обе части $(*)$ на $p_{m+1}$.

2) $C_{2n}^n=\dfrac{(n+1)(n+2)...(n+n)}{n!}$

От чего тут оттолкнуться, что-то индукция здесь не пройдет, мне кажется...

 
 
 
 Re: Док-во, простые числа.
Сообщение03.03.2013, 23:25 
Аватара пользователя
Во втором наверняка пройдет формула Лежандра (показатель простого числа в факториале). Попробуйте это применить, т.е. $$v_{p}(n!)=\left[\frac{n}{p}\right]+\left[\frac{n}{p^2}\right]+\dots$$

 
 
 
 Re: Док-во, простые числа.
Сообщение04.03.2013, 01:47 
Аватара пользователя
Первую задачу можно вот так сделать:
Введем так называемую тэта-функцию Чебышева, которая определяется таким образом: $$\theta(x)=\sum \limits_{p\leqslant x}\ln p$$Как мы знаем $\pi(x)$ - количество простых чисел, не превосходящие $x$
Пусть $\pi(n)=k$, тогда $2=p_1<p_2<\dots<p_k\leqslant n$
Рассмотрим тэта-функцию Чебышева с аргументом $\pi(n)$, т.е.$$\theta(\pi(n))=\sum \limits_{p\leqslant \pi(n)}\ln p=\sum \limits_{i=1}^{k}\ln p_i=\ln\prod \limits_{i=1}^{k}p_i$$ Нетрудно доказать, что при $n\geqslant 1$ справедливо неравенство $\theta(n)\leqslant  2n\ln 2$
Применяя полученное неравенство к $\theta(\pi(n))$ получаем следующее: $$\theta(\pi(n))=\ln\prod \limits_{i=1}^{k}p_i<2\pi(n)\ln2<2n\ln2=n\ln 4$$Здесь я пользовался очевидным неравенством: $\pi(n)<n$
Потенцируя вышеуказанное неравенство получаем что: $$\prod \limits_{i=1}^{k}p_i<4^n$$

 
 
 
 Re: Док-во, простые числа.
Сообщение04.03.2013, 03:33 
Whitaker в сообщении #690879 писал(а):
Нетрудно доказать, что при $n\geqslant 1$ справедливо неравенство $\theta(n)\leqslant  2n\ln 2$

Спасибо, все понятно, кроме этого очевидного. А чтобы это нетрудно доказать, что нужно применить?

-- 04.03.2013, 03:41 --

Whitaker в сообщении #690846 писал(а):
Во втором наверняка пройдет формула Лежандра (показатель простого числа в факториале). Попробуйте это применить, т.е. $$v_{p}(n!)=\left[\frac{n}{p}\right]+\left[\frac{n}{p^2}\right]+\dots$$


Простое число $p$ входит в числитель с показателем $v_p(2n!)=\sum \limits_{j\geqslant 1} \left[\dfrac{2n}{p^j}\right]$, а знаменатель с показателем $2v_p(2n!)=\sum \limits_{j\geqslant 1} 2\left[\dfrac{n}{p^j}\right]$
А $\sum \limits_{j\geqslant 1}\left(\left[\dfrac{2n}{p^j}\right]-2\left[\dfrac{n}{p^j}\right]\right)=???$

 
 
 
 Re: Док-во, простые числа.
Сообщение04.03.2013, 07:26 
lampard в сообщении #690892 писал(а):
А $\sum \limits_{j\geqslant 1}\left(\left[\dfrac{2n}{p^j}\right]-2\left[\dfrac{n}{p^j}\right]\right)=???$
Попробуйте сначала понять, чему вообще может быть равно $\left[\frac{2n}{m}\right]-2\left[\frac{n}{m}\right]$.

lampard в сообщении #690832 писал(а):
1) $\displaystyle\prod_{i=1}^{k}p_i\;\;<4^n$, причем $p_k\leqslant n\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;(*)$
Советую писать $\prod\limits_{p\leqslant n}p$ - буковок меньше :-)

lampard в сообщении #690832 писал(а):
2) Для $\dfrac{2n}{3}<p<n$ число $C_{2n}^n$ не кратно $p$?
Взять формулу
lampard в сообщении #690892 писал(а):
$$v_{p}(n!)=\left[\frac{n}{p}\right]+\left[\frac{n}{p^2}\right]+\dots$$
Вычислить по ней $v_p(C_{2n}^n)$ явно, найти число слагаемых в полученной сумме, а затем явно найти значение, используя неравенства. Для этого Вам понадобиться уже знать значение $\left[\frac{2n}{m}\right]-2\left[\frac{n}{m}\right]$.

 
 
 
 Re: Док-во, простые числа.
Сообщение04.03.2013, 14:42 
Аватара пользователя
lampard в сообщении #690892 писал(а):
А чтобы это нетрудно доказать, что нужно применить?
Оценку $\theta(n)<2n\ln2$ попробуйте доказать по индукции при $n\geqslant 2$

 
 
 
 Re: Док-во, простые числа.
Сообщение04.03.2013, 19:07 
Whitaker в сообщении #691068 писал(а):
lampard в сообщении #690892 писал(а):
А чтобы это нетрудно доказать, что нужно применить?
Оценку $\theta(n)<2n\ln2$ попробуйте доказать по индукции при $n\geqslant 2$


$\theta(n)=\sum \limits_{p\leqslant n}\ln p$

$\theta(n)<2n\ln2$

1) Для $n=2$

$\ln 2<4\ln 2$

2) Пусть неравенство $\theta(n)<2n\ln2$ выполнено для $n=k$

Проверим -- будет ли оно выполнено для $n=k+1$

а) Пусть $k+1$ -- составное число, тогда

$\theta(k+1)=\sum \limits_{p\leqslant k}\ln p<2k\ln 2<2(k+1)\ln 2$ ч.т.д.

б) Пусть $k+1$ -- простое число, тогда

$\theta(k+1)=\sum \limits_{p\leqslant k}\ln p+\ln(k+1)<2k\ln 2+\ln(k+1)<????$ Тут не получается...

 
 
 
 Re: Док-во, простые числа.
Сообщение04.03.2013, 19:43 
Там не такая индукция нужна, а индукция через неравенство $\theta(2n)-\theta(n)\leqslant A\ln n$, вспоминайте предыдущую тему про постулат Бертрана.

 
 
 
 Re: Док-во, простые числа.
Сообщение04.03.2013, 20:07 
Аватара пользователя
Базу верно проверили.
Проведем доказательство методом полной математической индукции по $n$.
Пусть верно, что $\theta(k)<2k\ln 2$ для всех $k=1,...,n-1$
Докажем для $n$: если $n$ - не простое, то $\theta(n)=\theta(n-1)<2(n-1)\ln2<2n\ln 2$
Пусть $n$ - нечетное и имеет вид $n=2m+1$. Тогда любое простое $p$ из $(m+1, 2m+1]$ делит $C_{2m+1}^{m}$ (проверьте это!)
По формуле бинома Ньютона получаем, что: $C_{2m+1}^{m+1}+C_{2m+1}^{m}<2^{2m+1}$ при $m\geqslant 1$ (при $m=0$ там будет знак равенства, но этот случай нас не интересует)
Получаем, что $C_{2m+1}^{m}<2^{2m}$, но $$C_{2m+1}^{m}\geqslant \prod \limits_{m+1<p\leqslant 2m+1} p$$Получаем, что $\theta(2m+1)-\theta(m+1)<2m\ln2$
Далее, пользуясь предположением индукции получаем, что $$\theta(2m+1)<\theta(m+1)+2m\ln2<2(m+1)\ln2+2m\ln2=2(2m+1)\ln 2$$

(Оффтоп)

Ну это уже Вы должны понять. Не задавайте сразу вопросов. Посидите, возьмите ручку и бумагу подумайте прокрутите. Нельзя все спрашивать.

 
 
 
 Re: Док-во, простые числа.
Сообщение05.07.2013, 21:58 
lampard в сообщении #690832 писал(а):
Как доказать, что ...

1) $\displaystyle\prod_{i=1}^{k}p_i\;\;<4^n$, причем $p_k\leqslant n\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$

2) Для $\dfrac{2n}{3}<p<n$ число $C_{2n}^n$ не кратно $p$?



п.1,2 в Д-ве Ердеша постулата Бертрана 1932 г.

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


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