[wpoms.]

(i) Докажите, что если `n` является натуральным числом, то `((2n),(n)) = ((2n)!)/(n!)^2` является натуральным числом, которое делится на все простые числа `p` из интервала `n < p <= 2n`, и что `((2n),(n)) < 2^{2n}`. (ii) Для положительного действительного числа `x` обозначим через `pi(x)` количество простых чисел `p <= x`. Например, `pi(10) = 4` так как есть четыре простых числа, не превосходящих `10`: `2`, `3`, `5` и `7`. Докажите, что для натуральных чисел `n >= 3` выполняется: (a) `pi(2n) < pi(n) + (2n)/(log_2(n))`; (b) `pi(2^n) < (2^{n+1) log_2(n-1))/n`; (c) Выведите, что для всех действительных чисел `x >= 8`, `pi(x) < (4x log_2(log_2(x)))/(log_2(x))`.

@темы: Теория чисел

Comments

[bigant]

(i) первое утверждение очевидно (целое - так как это биномиальный коэффициент, а делится поскольку числитель дроби делится на все такие простые, а знаменатель нет)
второе можно доказать по индукции:
база очевидна, переход от n-1 к n: (2n,n)=2n*(2n-1)/n^2 * (2(n-1),n-1)< 4 * 2^{2(n-1)} = 2^{2n}

(ii) a) заметим, что (2n,n) > n^{pi(2n)-pi(n)}, по пункту 1 (число делится на произведение всех простых, каждое из которых больше n, а их количество в точности pi(2n)-pi(n) ), откуда вновь по пункту 1
n^{pi(2n)-pi(n)}<2^{2n}, откуда логарифмируя и совершая тривиальные преобразования, получаем требуемое