Док-во, простые числа.

[lampard]

Как доказать, что ...

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!}$

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

[Whitaker]

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

$$v_{p}(n!)=\left[\frac{n}{p}\right]+\left[\frac{n}{p^2}\right]+\dots$$

[Whitaker]

Первую задачу можно вот так сделать:
Введем так называемую тэта-функцию Чебышева, которая определяется таким образом:

$$\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$$

[lampard]

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)=???$

[Sonic86]

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]$.

[Whitaker]

lampard в сообщении #690892 писал(а):

А чтобы это нетрудно доказать, что нужно применить?

Оценку $\theta(n)<2n\ln2$ попробуйте доказать по индукции при $n\geqslant 2$

[lampard]

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)<????$ Тут не получается...

[Sonic86]

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

[Whitaker]

Базу верно проверили.
Проведем доказательство методом полной математической индукции по $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$$

(Оффтоп)

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

[megamix62]

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 г.