Простые числа.

[lampard]

Как в такой задаче доказать второй знак неравенства? Верно ли доказан первый?

Задача такая: доказать двойное неравенство.

$\displaystyle\prod_{n<p<2n}p\;\;<C_{2n}^{n}<\dfrac{4^n}{\sqrt{2n}}$

То, что найдутся простые числа между $n$ и $2n$ -- считать известным.

1) $\displaystyle\prod_{n<p<2n}p<C_{2n}^{n}$ доказывал вот так:

$\displaystyle\prod_{n<p<2n}p<\dfrac{n!(n+1)(n+2)...(n+n)}{n!\cdot n!}=(n+1)(n+2)...(n+n)$

Ну а то, что $\displaystyle\prod_{n<p<2n}p<\displaystyle\prod_{n< i\le 2n}i,\;\;i\in\mathbb{Z}$ -- очевидно.

Можно ли так было сделать?

2) А вот как доказать $C_{2n}^{n}<\dfrac{4^n}{\sqrt{2n}}$ -- пока что не очевидно, хотя есть одно несколько странное предположение:

Перепишем второе неравенство в виде:

$(n+1)(n+2)...(n+n)<\left(\dfrac{4}{\sqrt[2n]{2n}}\right)^n$

А как дальше или иначе нужно?

[nnosipov]

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

2) А вот как доказать $C_n^{2n}<\dfrac{4^n}{\sqrt{2n}}$

По индукции. Только предварительно его усильте до $C_n^{2n}<\dfrac{4^n}{\sqrt{2(n+1)}}$, иначе ничего не выйдет. А вообще верно даже неравенство $C_n^{2n}<\dfrac{4^n}{\sqrt{\pi n}}$.

Только сейчас заметил, что ТС (и я, его копируя) вместо $C_{2n}^n$ пишет $C_n^{2n}$.

[Sonic86]

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

1) $\displaystyle\prod_{n<p<2n}p<C_n^{2n}$ доказывал вот так:

$\displaystyle\prod_{n<p<2n}p<\dfrac{n!(n+1)(n+2)...(n+n)}{n!\cdot n!}=(n+1)(n+2)...(n+n)$

Ну а то, что $\displaystyle\prod_{n<p<2n}p<\displaystyle\prod_{n< i\le 2n}i,\;\;i\in\mathbb{Z}$ -- очевидно.

Равенство $\dfrac{n!(n+1)(n+2)...(n+n)}{n!\cdot n!}=(n+1)(n+2)...(n+n)$ неверно - факториал потерялся. Тут надо начинать с того, что если $n<p\leqslant 2n$, то $p\mid (n+1)(n+2)...(n+n)$ и дальше смотреть что будет с $p$, если $(n+1)(n+2)...(n+n)$ поделить на $n!$.
И кстати, пишите либо $C_{2n}^n$, либо $\binom{2n}{n}$, а $C_n^{2n}$ - это не то.

[lampard]

Sonic86 в сообщении #690314 писал(а):

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

1) $\displaystyle\prod_{n<p<2n}p<C_n^{2n}$ доказывал вот так:

$\displaystyle\prod_{n<p<2n}p<\dfrac{n!(n+1)(n+2)...(n+n)}{n!\cdot n!}=(n+1)(n+2)...(n+n)$

Ну а то, что $\displaystyle\prod_{n<p<2n}p<\displaystyle\prod_{n< i\le 2n}i,\;\;i\in\mathbb{Z}$ -- очевидно.

Равенство $\dfrac{n!(n+1)(n+2)...(n+n)}{n!\cdot n!}=(n+1)(n+2)...(n+n)$ неверно - факториал потерялся. Тут надо начинать с того, что если $n<p\leqslant 2n$, то $p\mid (n+1)(n+2)...(n+n)$ и дальше смотреть что будет с $p$, если $(n+1)(n+2)...(n+n)$ поделить на $n!$.
И кстати, пишите либо $C_{2n}^n$, либо $\binom{2n}{n}$, а $C_n^{2n}$ - это не то.

Спасибо, исправил перепутанные местами $n$ и $2n$.

$\dfrac{n!(n+1)(n+2)...(n+n)}{n!\cdot n!}=\dfrac{(n+1)(n+2)...(n+n)}{2\cdot 3\cdot...\cdot n}$

Пока что мне не очевидно -- почему собственно $(n+1)(n+2)...(n+n)$ делится на $2\cdot 3\cdot...\cdot n$, кроме здравого смысла, который подсказывает, что число сочетаний - целое.

[nnosipov]

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

почему собственно $(n+1)(n+2)...(n+n)$ делится на $2\cdot 3\cdot...\cdot n$, кроме здравого смысла, который подсказывает, что число сочетаний - целое.

Вы что, своему здравому смыслу не доверяете? Вам о другом предлагают подумать: почему $(n+1) \ldots (n+n)/n!$ будет делиться на любое простое $p$, для которого $n \leqslant p<2n$.

[Whitaker]

Потому что Ваше выражение есть $C_{2n}^n=\dfrac{(2n)!}{(n!)^2}$
Простое число $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)=1$ так как $n<p\leqslant 2n$

[nnosipov]

Whitaker, не пугайте ТС. Здесь можно обойтись более простыми (если не сказать очевидными) соображениями.

[Whitaker]

nnosipov
Хотя да согласен с Вами. Этот факт

nnosipov в сообщении #690336 писал(а):

почему $(n+1) \ldots (n+n)/n!$ будет делиться на любое простое $p$, для которого $n \leqslant p<2n$.

можно не доказывать. Очевиднее уже некуда

[nnosipov]

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

То, что найдутся простые числа между $n$ и $2n$ -- считать известным.

А зачем? Для доказательства Вашего двойного неравенства это не нужно.

[lampard]

nnosipov в сообщении #690336 писал(а):

почему $(n+1) \ldots (n+n)/n!$ будет делиться на любое простое $p$, для которого $n \leqslant p<2n$.

Понятно -- почему числитель делится на любое просто $p$ , для которого $n \leqslant p<2n$, ибо в числителе ровно есть все простые от $n$ до $2n$ ( и не только простые), ну а значит произведение делится на $p$, другое дело -- а не "схавает" $n!$ нужные числа?

Upd: Не схавает, так как простые числа от $n$ до $2n$ не могут иметь делителей до $n$, кроме $1$, что нас особенно не волнует)

nnosipov в сообщении #690313 писал(а):

По индукции. Только предварительно его усильте до $C_{2n}^{n}<\dfrac{4^n}{\sqrt{2(n+1)}}$, иначе ничего не выйдет. $[/math].

1) Проверим базу индукции. $n=2$

$C_4^1=4<\dfrac{16}{\sqrt{10}}\approx 5$ (грубо)

База проверена.

2) Предположим, что неравенство $C_{2n}^{n}<\dfrac{4^n}{\sqrt{2(n+1)}}$ выполняется для $n=k$. Проверим -- будет ли оно выполняться для $n=k+1$?

Т.е. будет ли выполняться неравенство $C_{2k+2}^{k+1}<\dfrac{4^{k+1}}{\sqrt{2(k+2)}}$

$C_{2k+2}^{k+1}=\dfrac{(2k)!\cdot (2k+1)(2k+2)}{(k+1)!(k+1)!}=2\cdot \dfrac{(2k)!\cdot (2k+1)}{(k+1)\cdot k!k!}=\dfrac{2(2k+1)}{k+1}\cdot C_{2k}^k$

$\dfrac{4^k}{\sqrt{2(k+1)}}<\dfrac{4^{k+1}}{\sqrt{2(k+2)}}$

Пока что больше не могу ничего придумать для док-ва...Что можно еще сделать?

[nnosipov]

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

Upd: Не схавает, так как простые числа от $n$ до $2n$ не могут иметь делителей до $n$,

Да, в этом всё дело.

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

1) Проверим базу индукции. $n=2$

$C_4^1=4<\dfrac{16}{\sqrt{10}}\approx 5$ (грубо)

База проверена.

Не проверена. Будьте внимательнее.

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

$\dfrac{4^k}{\sqrt{2(k+1)}}<\dfrac{4^{k+1}}{\sqrt{2(k+2)}}$

Пока что больше не могу ничего придумать для док-ва...Что можно еще сделать?

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

$$ C_{2k+2}^{k+1}=\dfrac{2(2k+1)}{k+1}\cdot C_{2k}^k $$

и оценить её тем самым сверху. Ну, а дальше немного подумать.

[lampard]

nnosipov в сообщении #690424 писал(а):

Не проверена. Будьте внимательнее.

Исправился.
$C_4^1=4<\dfrac{16}{\sqrt{6}}\approx 6,5$

-- 03.03.2013, 14:16 --

nnosipov в сообщении #690424 писал(а):

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

$$ C_{2k+2}^{k+1}=\dfrac{2(2k+1)}{k+1}\cdot C_{2k}^k $$

и оценить её тем самым сверху. Ну, а дальше немного подумать.

$$C_{2k+2}^{k+1}=\dfrac{2(2k+1)}{k+1}\cdot C_{2k}^k < \dfrac{2(2k+1)}{k+1}\cdot \dfrac{4^k}{\sqrt{2(k+1)}}<\dfrac{2(2k+2)}{k+1}\cdot \dfrac{4^k}{\sqrt{2(k+1)}}= \dfrac{4^{k+1}}{\sqrt{2(k+1)}}$$

Если бы в знаменателе было под корнем $2(k+2)$, а не $2(k+1)$, то все было доказано. Пока что не могу догадаться -- откуда эту единичку можно выудить...

[nnosipov]

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

Исправился.

Нет. Чему равно $C_{2n}^n$ при $n=2$?

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

$$C_{2k+2}^{k+1}=\dfrac{2(2k+1)}{k+1}\cdot C_{2k}^k < \dfrac{2(2k+1)}{k+1}\cdot \dfrac{4^k}{\sqrt{2(k+1)}}<\dfrac{2(2k+2)}{k+1}\cdot \dfrac{4^k}{\sqrt{2(k+1)}}= \dfrac{4^{k+1}}{\sqrt{2(k+1)}}$$

Второе неравенство --- грубое, поэтому и не получается. Вы уже вывели неравенство

$$ C_{2k+2}^{k+1} < \dfrac{2(2k+1)}{k+1}\cdot \dfrac{4^k}{\sqrt{2(k+1)}}, \eqno(*) $$

а нужно получить неравенство

$$ C_{2k+2}^{k+1} < \dfrac{4^{k+1}}{\sqrt{2(k+2)}}. \eqno(**) $$

Что достаточно доказать, чтобы из неравенства $(*)$ следовало неравенство $(**)$?

[lampard]

nnosipov в сообщении #690610 писал(а):

Чему равно $C_{2n}^n$ при $n=2$?

6

nnosipov в сообщении #690610 писал(а):

Вы уже вывели неравенство

$$ C_{2k+2}^{k+1} < \dfrac{2(2k+1)}{k+1}\cdot \dfrac{4^k}{\sqrt{2(k+1)}}, \eqno(*) $$

а нужно получить неравенство

$$ C_{2k+2}^{k+1} < \dfrac{4^{k+1}}{\sqrt{2(k+2)}}. \eqno(**) $$

Что достаточно доказать, чтобы из неравенства $(*)$ следовало неравенство $(**)$?

$$C_{2k+2}^{k+1} < \dfrac{2(2k+1)}{k+1}\cdot \dfrac{4^k}{\sqrt{2(k+1)}}= \dfrac{2(2k+1)}{k+1}\cdot \dfrac{4^k}{\sqrt{2(k+1)}}\cdot \dfrac{4\sqrt{2(k+2)}}{4\sqrt{2(k+2)}}=\dfrac{2(2k+1)}{k+1}\cdot \dfrac{\sqrt{2(k+2)}}{4\sqrt{2(k+1)}}\cdot \dfrac{4^{k+1}}{\sqrt{2(k+2)}}$$

То есть нужно доказать это неравенство $\dfrac{2(2k+1)}{k+1}\cdot \dfrac{\sqrt{2k+4}}{4\sqrt{2k+2}}>1$

Преобразуя:

$\dfrac{4k+2}{4k+4}\cdot \dfrac{\sqrt{k+2}}{\sqrt{k+1}}>1$

Что-то странное получается...

[nnosipov]

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

То есть нужно доказать это неравенство $\dfrac{2(2k+1)}{k+1}\cdot \dfrac{\sqrt{2k+4}}{4\sqrt{2k+2}}>1$

Нет, не это нужно доказывать.