Простое число, док-во

[integral2009]

ИСН в сообщении #685893 писал(а):

Переход в таком изложении может прокатить перед слушателем, который уже и так согласен. Вы в одной строчке говорите "нужно проверить, что $p_{n+1}\leqslant 2^{n+1}$", а в следующей немедленно утверждаете этот факт как факт. Почему факт? Потому что нам нужно? Ну ОК.

Спасибо, да, там это было лишнее.

Нужно проверить, что $p_{n+1}\leqslant 2^{n+1}$.

Используя постулат Бертрана, взяв $k=2^n$ , имеем $2^{n}\leqslant p_{n+1} \leqslant2\cdot 2^{n}$. чтд.

[ИСН]

Как в точности формулируется постулат Бертрана, который Вы используете? А то у Вас получилось, что $2^n\leqslant p_{n+1}$, т.е., например, $1024=2^{10}\leqslant p_{11}=31$. От этого как-то тревожно.

[integral2009]

ИСН в сообщении #685910 писал(а):

Как в точности формулируется постулат Бертрана, который Вы используете? А то у Вас получилось, что $2^n\leqslant p_{n+1}$, т.е., например, $1024=2^{10}\leqslant p_{11}=31$. От этого как-то тревожно.

Для любого натурального $n \geqslant 2$ найдётся простое число $p$ в интервале $n < p < 2n$

(Оффтоп)

Ух, что ж я делал. Жуткая ошибка. Мозг вечером уже не тот, что утром

[ИСН]

Так. С учётом этого огласите ещё раз переход индукции.

[integral2009]

Не в ту сторону знаки рисуются...

Нужно доказать $p_k\leqslant 2^k$(*)

1) База ...

2) Пусть для $k=n$ выполняется, проверим для $k=n+1$.

$p_{n+1}\underbrace{\leqslant}_{?} 2p_n\leqslant 2^{n+1}$

Теперь нужно доказать, что $p_{n+1}\leqslant 2p_n$. Реально это сделать или я опять не туда?

[ИСН]

Ещё как реально! Надо применить... Вы не поверите... постулат Бертрана!

[integral2009]

ИСН в сообщении #685927 писал(а):

Ещё как реально! Надо применить... Вы не поверите... постулат Бертрана!

$p_{n}\leqslant p_{n+1}\leqslant 2p_n$

Спасибо, понятно!!! Что ж я так тупил.

[ИСН]

-- Ср, 2013-02-20, 01:03 --

оба неравенства можно сделать строгими

[Whitaker]

Да и нижнюю оценку можно доказать через теорему Чебышева:
Взяв $x=p_n$ мы получим, что

$$a\dfrac{p_n}{\ln p_n}\leqslant n \leqslant A\dfrac{p_n}{\ln p_n}$$

Рассматривая второе неравенство и оценив его получаем, что при $n>N_1$ будет $n\leqslant A\dfrac{p_n}{\ln p_n}\leqslant \dfrac{p_n}{3}$, а отсюда сразу получаем, что $p_n\geqslant 3n$ начиная с некоторого $n>N_1$

(Оффтоп)

ИСН
то, что теорема Чебышева -- сильное утверждение я с Вами полностью согласен, но я просто хотел, чтобы ТС увидел, что такие оценки получить легко из данного неравенства. Да и здесь нужно немного знания матана, а теорема Чебышева доказывается весьма просто. Да и постулат Бертрана на мой взгляд тоже сильное утверждение.

[Sonic86]

(Оффтоп)

ИСН в сообщении #685858 писал(а):

Whitaker, имейте совесть. Вы опираетесь на неадекватно сильное утверждение - фактически, что $p_n<C\cdot n\cdot\ln n$. Этого не нужно. Постулат Бертрана, как и было сказано - в самый раз.

Не надо, в самый раз, доказательство постулата Бертрана фактически задает верхнюю оценку $\pi (x)\leqslant A\frac{x}{\ln x}$. Вот $\pi(x)\sim \frac{x}{\ln x}$ сильнее.
И вообще, ТС должен понимать, что если он полез в АТЧ, то там надо быть во всеоружии.

Ward в сообщении #685877 писал(а):

как получить оценку $p_n\geqslant 3n$?

Ее можно получить через конечное число шагов решета Эратосфена + численную базу для шага индукции (для самых малых $n$ утверждение может быть просто неверно) + индукцией по $n$.

[RIP]

Вообще, постулат Бертрана не сильно проще оценок Чебышёва. Хотя вид оценки и намекает на него. Интересно, можно ли эту оценку доказать совсем по-простому? (Из совсем простых оценок я знаю только что-то вроде $p_n<4^n$; можно улучшить в константу раз, но четвёрку я уменьшать не умею.)

[ИСН]

Дух задания кагбе подразумевает, что Бертрана надо воспринимать как данность, без доказательства, и применять по необходимости.
Совсем простых не надо. Это сложно.

[sup]

RIP в сообщении #686074 писал(а):

Вообще, постулат Бертрана не сильно проще оценок Чебышёва. Хотя вид оценки и намекает на него. Интересно, можно ли эту оценку доказать совсем по-простому?

Можно воспользоваться известным соотношением
$\sum \limits_{p \leqslant x}\frac{1}{p} \geqslant \ln \ln x + O(1)$
Его, в свою очередь, легко вытащить из оценки
$\prod \limits_{p \leqslant x}(1+\frac{1}{p}+\frac{1}{p^2} \dots ) \geqslant \sum \limits_{k \leqslant x} \frac{1}{k}$

С другой стороны, при $n > 4$ имеем очевидное неравенство $p_n \geqslant 2n+1$, а значит
$2\sum \limits_{k \leqslant n}\frac{1}{p_k} \leqslant \sum \limits_{k \leqslant n} \frac{1}{k} + O(1)$
Отсюда
$\ln n \geqslant 2\ln \ln p_n + O(1)$
$p_n \leqslant e^{C\sqrt n}$

[Whitaker]

Можно дать еще такое доказательство:
Рассмотрим такое произведение

$$\prod \limits_{p\leqslant x}\left(1-\dfrac{1}{p}\right)^{-1}=\sum\limits^{*} \dfrac{1}{n}$$

причем зведочка в $\sum\limits^{*}$ означает, что суммирование ведется только по тем $n$, простые множители которых не превосходят $x$. В частности,

$$\sum\limits^{*} \dfrac{1}{n}>\sum\limits_{n\leqslant x} \dfrac{1}{n}>\int \limits_{1}^{[x]+1}\dfrac{d\xi}{\xi}>\ln x$$

Также понятно, что

$$\prod \limits_{p\leqslant x}\left(1-\dfrac{1}{p}\right)^{-1}\leqslant \prod \limits_{k=2}^{\pi(x)+1}\left(1-\dfrac{1}{k}\right)^{-1}=\dfrac{2\cdot 3 \cdots\{\pi(x)+1\} }{1\cdot 2 \cdots\pi(x) }=\pi(x)+1$$

Если воспользоваться еще тем, что $\pi(p_n)=n$, то получаем, что $p_n<e^{n+1}$

(Оффтоп)

Мне кажется, что ТС это уже вообще неинтересно