В этой заметке мы разберём задачи из статьи М. И. Башмакова «О постулате Бертрана» (см. «Квант» № 5, 1971).
Напомним, что постулатом Бертрана называется следующее утверждение: если $x \gt 1$, то существует простое число, заключённое между $x$ и $2x$.
Это утверждение сформулировал французский математик Бертран, но отыскать доказательства для него не сумел. Это удалось сделать Чебышеву, причём сделать совершенно элементарно. Правда, он воспользовался одной не элементарной формулой — формулой Стирлинга:
$$
n!=\sqrt{2\pi n}\left(\dfrac ne\right)^ne^{\frac{\scriptstyle\theta_n}{\scriptstyle12n}},\quad\text{где}~0\lt\theta_n\lt1.
$$
В эту формулу входят два едва ли не самых замечательных числа. Первое — это всем вам известное число $\pi$ — отношение длины окружности к её диаметру. Второе число — это число $e$ — предел последовательности $\left(\dfrac{n+1}n\right)^n$ при $n$, стремящемся к бесконечности. Формула эта понадобилась Чебышеву для того, чтобы оценить величину $n!=1\cdot2\cdot\ldots\cdot n$.
На самом же деле, чтобы доказать постулат Бертрана, можно использовать существенно менее точные оценки величины $n!$.
Именно такие оценки и предлагалось доказать читателю в статье Башмакова (задача 3). С разбора этой задачи мы и начнём.
Вот её формулировка:
Докажите, что существует такое действительное число $e$, что при всех натуральных $n$, больших некоторого $n_0$,
$$
\left(\dfrac{n+1}e\right)^n\lt n!\lt n\left(\dfrac ne\right)^n.
$$
Неравенства
$\left(\dfrac{n+1}e\right)^n\lt n!\lt n\left(\dfrac ne\right)^n$
можно использовать вместо формулы Стирлинга. Они, конечно, менее точны, но зато и доказать их намного проще.
Остальные задачи из статьи — это, по сути дела, леммы из чебышевского доказательства постулата Бертрана. Решить их намного проще, чем задачу 3. Заслуга Чебышева не в том, что он их решил — сделать это нетрудно, — а в том, что он их сформулировал и нашёл, как с помощью этих утверждений получить оценки для произведения (и, тем самым, для количества) простых чисел, не превосходящих $x$, и доказать постулат Бертрана.
Решение задачи 3. Примем пока без доказательства, что такое число $e$, что при всех натуральных $n$
$$
\left(\dfrac{n+1}n\right)^n\lt e\lt\left(\dfrac{n+1}n\right)^{n+1},
$$
действительно существует. (Доказательство существования будет приведено чуть ниже.)
Мы хотим доказать, что $$
\left(\dfrac{n+1}e\right)^n\lt n!\lt n\left(\dfrac ne\right)^n
$$
или (что то же самое)
$$
\dfrac{(n+1)^n}{n!}\lt e^n\lt\dfrac{n^n}{(n-1)!}
$$
при $n$, бо́льших некоторого $n_0$.
Пусть для некоторого $k$ доказано, что $\dfrac{(k+1)^k}{k!}\lt e^k$. Ho $$
\dfrac{(k+2)^{k+1}}{(k+1)!}\Big/\dfrac{(k+1)^k}{k!}=\left(\dfrac{k+2}{k+1}\right)^{k+1}\lt e.
$$
Поэтому $\dfrac{(k+2)^{k+1}}{(k+1)!}\lt e^{k+1}$.
Таким образом, наше утверждение верно и для $k+1$, а значит, и для $k+2$, $k+3$ и т. д. Точно так же из предположения
$e^k\lt\dfrac{k^k}{(k-1)!}$
выводится, что $e^{k+1}\lt\dfrac{(k+1)^{k+1}}{k!}$.
Действительно,
$$
\dfrac{(k+1)^{k+1}}{k!}\Big/\dfrac{k^k}{(k-1)!}=\left(\dfrac{k+1}k\right)^{k+1}\gt e.
$$
Остаётся доказать, что $e$ существует, и найти начальные значения для $n$ в каждом из неравенств
$$
\left(\dfrac{n+1}e\right)^n\lt n!,\quad n!\lt n\left(\dfrac ne\right)^n.
$$
Доказательство существования $\bm{e}$
Условимся называть совокупность действительных чисел $x$, удовлетворяющих неравенству $a\le x\le b$, отрезком с концами $a$ и $b$ (отрезок с концами $a$ и $b$ обозначается через $[a,b]$).
При доказательстве существования числа $e$ мы будем пользоваться следующим свойством действительных чисел: если есть последовательность отрезков $[a_i,b_i]$, где $a_i\le a_{i+1} \lt b_{i+1} \le b_i$ ($i=1$, 2, $\ldots$) (о такой последовательности говорят, что она является последовательностью вложенных отрезков), то существует точка $\alpha$, общая для всех этих отрезков.
Это свойство мы не будем доказывать. Дело в том, что при чётком определении того, что мы понимаем под множеством действительных чисел, это (или какое-нибудь эквивалентное ему) свойство принимается как аксиома.
Упражнения
- Проверьте, что следующие свойства действительных чисел эквивалентны; если принять любое из них без доказательства, то остальные из него выводятся.
- У всякой последовательности вложенных отрезков есть хотя бы одна общая точка.
- Всякая ограниченная монотонно возрастающая последовательность имеет предел.
- Всякая последовательность $\{ a_i\}$ ($i=1$, 2, $\ldots$), в которой для любого $\eps\gt0$ можно указать такое $N$ (зависящее, разумеется, от $\eps$), что $|a_n-a_m|\lt\eps$ при $m$, $n\gt N$ имеет предел. (Такие последовательности называются последовательностями Коши.)
- Всякое ограниченное сверху множество действительных чисел имеет точную верхнюю грань, т. е. можно указать такое число $\alpha$, что все принадлежащие этому множеству числа не больше $\alpha$, но для всякого числа $\beta$, меньшего $\alpha$, найдутся числа из этого множества, большие $\beta$.
- Из всякого семейства отрезков, покрывающих отрезок $[a,b]$, можно выделить конечное семейство отрезков, покрывающих отрезок $[a,b]$. (Мы говорим, что система $M$ отрезков покрывает отрезок $[a,b]$, если для всякого $x$, принадлежащего отрезку $[a,b]$, найдётся отрезок из системы $M$, содержащий $x$.)
Покажем теперь, что последовательность $\left(\dfrac{n+1}n\right)^n$ — монотонно возрастающая. Для этого нужно, чтобы при любом $n$
число $\left(\dfrac{n+1}n\right)^n$
было меньше $\left(\dfrac{n+2}{n+1}\right)^{n+1}$:
$$
\left(\dfrac{n+1}n\right)^n\lt\left(\dfrac{n+2}{n+1}\right)^{n+1}.
$$
С помощью несложных преобразований это неравенство можно привести к такому виду:
$$
[(n^2+2n+1)^n-(n^2+2n)^n](n+1)\lt(n^2+2n)^n.\tag1
$$
[Вот промежуточные неравенства:
$$
(n+1)^{2n+1}\lt(n+2)^{n+1}n^n\quad\text{и}\quad
(n^2+2n+1)^n(n+1)\lt(n^2+2n)^n(n+2).]
$$
Воспользовавшись формулой
$$
a^k-b^k=(a-b)(a^{k-1}+a^{k-2}b+\ldots+ab^{k-2}+b^{k-1}),
$$
получаем:
$$
(n^2+2n+1)^n-(n^2+2n)^n\lt n(n^2+2n+1)^{n-1}.
$$
Поэтому неравенство (1) будет доказано, если мы докажем такое неравенство:
$$
(n^2+2n+1)^{n-1}(n+1)\lt(n^2+2n)^{n-1}(n+2).
$$
Оно в свою очередь (это доказывается точно так же) следует из неравенства
$$
(n^2+2n+1)^{n-2}(n+1)\lt(n^2+2n)^{n-2}(n+2).
$$
Повторяя эти рассуждения, мы убеждаемся, что неравенство (1) следует из очевидного неравенства
$$
n+1\lt n+2.
$$
Ещё проще показать, что при любом натуральном $n$
$$
\left(\dfrac{n+1}n\right)^{n+1}\gt\left(\dfrac{n+2}{n+1}\right)^{n+2}.\tag2
$$
В самом деле, неравенство (2) эквивалентно неравенству
$$
(n+1)^{2n+3}\gt(n+2)^{n+2}n^{n+1}.
$$
Поэтому достаточно показать, что $$
[(n^2+2n+1)^{n+1}-(n^2+2n)^{n+1}](n+1)\gt(n^2+2n)^{n+1}.\tag3
$$
Но $$
(n^2+2n+1)^{n+1}-(n^2+2n)^{n+1}\gt(n^2+2n)^{n}(n+1),
$$
откуда
$$
\begin{gather*}
[(n^2+2n+1)^{n+1}-(n^2+2n)^{n+1}](n+1)\gt\\
\gt(n^2+2n)^{n}(n+1)^2\gt(n^2+2n)^n(n^2+2n)=(n^2+2n)^{n+1},
\end{gather*}
$$
т. е. неравенство (3), а значит, и неравенство (2), — доказано.
Итак, мы доказали, что последовательность $a_n=\left(\dfrac{n+1}n\right)^n$ монотонно возрастает, a последовательность $b_n=\left(\dfrac{n+1}n\right)^{n+1}$ монотонно убывает. Кроме того, $a_n \lt b_n$, поскольку $\dfrac{n+1}n\gt1$. Таким образом, последовательность отрезков с концами $a_i$, $b_i$; является последовательностью вложенных отрезков и длина $k$-го отрезка равна
$\left(\dfrac{k+1}k\right)^k\cdot\dfrac1k$,
т. е. при росте $k$ она стремится к нулю. Поэтому у всех этих отрезков есть ровно одна общая точка. Соответствующее ей число и называется числом $e$.
Можно вычислить сколько угодно десятичных знаков числа $e$. Вот первые несколько: $e=2{,}71828\ldots$
Поскольку $e\gt2$, неравенство
$\left(\dfrac{n+1}e\right)^n\lt n!$
выполняется уже при $n=1$. Неравенство
$n!\lt n\left(\dfrac ne\right)^n$
при $n=1$, 2, $\ldots$, 6 не выполняется, однако при $n=7$, а следовательно, и при больших $n$, — оно верно. (Мы не будем этого проверять, однако заметим, что это несложно сделать с помощью таблицы натуральных логарифмов — логарифмов по основанию $e$.)
Мы доказали, что $\left(\dfrac{n+1}n\right)^n$ стремится к $e$. На самом деле можно доказать, что $\left(\dfrac{n+x}n\right)^n$ стремится к $e^x$. Именно это и предлагается сделать в следующих упражнениях.
Упражнения
- Докажите, что последовательность $\left(\dfrac{n+x}n\right)^n$‚ где $x$ — положительное число, монотонно возрастает.
- Докажите, что последовательность $\left(\dfrac{n+x}n\right)^{n+l}$‚ где $l$ — натуральное число, большее $x$, монотонно убывает.
- Выведите из утверждений 2 и З, что последовательность $\left(\dfrac{n+x}n\right)^n$ при любом положительном $x$ имеет конечный предел.
- Докажите, что у последовательностей $\left(\dfrac{n+x}n\right)^n$ и $\left(\dfrac{n+x}n+\dfrac y{n^2}\right)^n$ пределы совпадают.
- Предел последовательности $\left(\dfrac{n+x}n\right)^n$ мы обозначим через $e^{x'}$ [здесь $x'$ — некоторое число, зависящее от $x$: $x'=f(x)$]. Выведите из 5, что $$
f(x_1+x_2)=f(x_1)+f(x_2).
$$
- Докажите, что $f(0)=0$ и что $f(x)=x$ при натуральных $x$.
- Докажите, что у последовательности $\left(\dfrac{n+x}n\right)^n$ при отрицательном $x$ также существует предел $e^{f(x)}$, причём $f(-x)=-f(x)$.
- Докажите, что если $m$ и $n$ — целые числа ($n\ne0$), то $f{\left( \dfrac mn\right)}=\dfrac{m}{n}$.
- Докажите, что функция $f(x)$ монотонно возрастает.
- Докажите, что $f(x)=x$.
Разберём теперь остальные задачи из статьи М. И. Башмакова.
Формулировки задач
Напомним обозначения:
$\pi(x)$ — это число простых чисел, не превосходящих $x$;
$\theta(x)$ — логарифм произведения всех простых чисел, не превосходящих $x$:
$$
\theta(x)=\log2+\log3+\log5+\ldots=\textstyle\sum\limits_{p\le x}\log p\quad(\theta(x)=0~\text{при}~x\lt2);
$$
$T(x)$ — логарифм произведения всех натуральных чисел, не превосходящих $x$:
$$
T(x)=\textstyle\sum\limits_{n\le x}\log n;
$$
$\psi(x)$ — логарифм наименьшего общего кратного всех натуральных чисел, не превосходящих $x$:
$$
\psi(x)=\textstyle\sum\limits_{p\le x}a_p\log p,
$$
где $p^{a_p}\le x$, $p^{a_p+1}\gt x$;
$S(x)=T(x)-T{\left(\dfrac x2\right)}-T{\left(\dfrac x3\right)}-T{\left(\dfrac x5\right)}+T{\left(\dfrac x{30}\right)}$.
Задача 1. Доказать, что
$$
T(x)=\psi(x)+\psi{\left(\dfrac x2\right)}+\psi{\left(\dfrac x3\right)}+\ldots
$$
Задача 2. Доказать, что
$$
\psi(x)=\theta(x)+\theta(\sqrt x)+\theta(\sqrt[\scriptstyle3]x)+\theta(\sqrt[\scriptstyle4]x)+\ldots
$$
Воспользовавшись результатом задачи 1, $S(x)$ можно записать так:
$$
S(x)=A_1\psi(x)+A_2\psi{\left(\dfrac x2\right)}+A_3\psi{\left(\dfrac x3\right)}+\ldots
$$
Задача 4. Проверьте, что коэффициенты $A_1$, $A_2$, $A_3$, $\ldots$ меняются с периодом 30 и что для первых тридцати значений $n$ коэффициенты $A_n$ составляют следующую последовательность:
1, 0, 0, 0, 0, $-1$, 1, 0, 0, $-1$, 1, $-1$, 1, 0, $-1$, 0, 1, $-1$, 1, $-1$, 0, 0, 1, $-1$, 0, 0, 0, 0, 1, $-1$.
Задача 5. Докажите, что
$$
\psi(x)-2\psi(\sqrt x)\le\theta(x)\le\psi(x)-\psi(\sqrt x).
$$
Задача 6. Докажите, что
$$
\dfrac{\psi (x)}{\log x}\lt\pi(x)\lt\dfrac{\psi(x)+\theta(x)}{\log x}.
$$
Решение задачи 1. Заметим, что $a_p=[\log_p x]$. Вычисляем, с каким коэффициентом входит $\log p$ в сумму
$\psi(x)+\psi{\left(\dfrac x2\right)}+\ldots$
В $\psi{\left(\dfrac xi\right)}$ логарифм $p$ входит с коэффициентом
$\left[\log_p\dfrac xi\right]$, значит, общий коэффициент при $\log p$ равен
$\sum\limits_{i=1}^{\left[\frac{\scriptstyle x}{\scriptstyle p}\right]} \left[\log_p\dfrac xi\right]$.
Вычтем из каждого слагаемого единицу и преобразуем его:
$$
\left[\log_p\dfrac xi\right]-1=\left[\log_p\dfrac xi-1\right]=\left[\log_p\dfrac{x_1}i\right],
$$
где $x_1=\dfrac xp$. Поэтому
$$
\sum\left[\log_p\dfrac xi\right]=\left[\dfrac x{\smash p\vphantom a}\right]+\sum\left[\log_p\dfrac{x_1}i\right].
$$
Повторяя нaше преобразование, мы получим такое равенство:
$$
\sum\left[\log_p\dfrac xi\right]=\sum\limits_{i=1}^{[\log_px]}\left[\dfrac x{\smash p\vphantom a^i}\right].
$$
Итак, коэффициент пpи $\log p$ в сумме
$\psi(x)+\psi{\left(\dfrac x2\right)}+\ldots$
равен
$\sum\limits_{i=1}^{[\log_px]}\left[\dfrac x{p^i}\right]$.
Заметим теперь, что $T(x)=\sum\limits_{i\le x}\log i$
тоже можно представить в таком виде:
$T(x)=\sum\limits_{p\le x}c_p\log p$,
где $p$ — простые числа.
Упражнения
- Докажите, что если $k$ — натуральное число, то $\left[\dfrac{x\vphantom)}k\right]=\left[\dfrac{[x]}k\right]$
и $[\log_k{[x]}]=[\log_kx]$ при $x\gt1$.
Убедитесь, что коэффициент $c_p$ равен
$\sum\limits_{i=1}^{[\log_p[x]]}\left[\dfrac{[x]}{p^i}\right]$.
Указание. Представьте $T(x)$ в виде $\log([x]!)$.
Решив упражнения 12 и 13, вы полностью решите задачу 1.
Решение задачи 2. Решение этой задачи похоже на решение зaдачи 1: нужно убедиться, что коэффициент при $p$ в сумме
$\theta(x)+\theta(\sqrt x)+\ldots$
равен $[\log_px]$. Сделать это совсем просто. $\log p$ входит слагаемым в $\theta(\sqrt[\scriptstyle i]x)$, если $\sqrt[\scriptstyle i]x\ge p$, т. е. $\log_px\ge i$. Поэтому в $\sum\theta(\sqrt[\scriptstyle i]x)$ логарифм $p$ входит слагаемым $k$ раз, где $k$ определяется из неравенства $k+1\gt\log_px\ge k$, т. е. $[\log_px]$ раз.
Решение задачи 4. Эта задача очень похожа на задачу М92 (см. «Квант» № 7, 1971).
Действительно, её можно сформулировать следующим образом:
В первую же поездку в магазин Петя купил себе много маленьких шоколадок. Он решил, что в скучные дни ему следует съедать три шоколадки, в те дни, когда он занят только одним делом — две, а в остальные — по одной. Тогда $A_i+2$ равно числу шоколадок, которые Петя съел в $(i+1)$-й день. (Напомним, что Петя каждый второй день ездил купаться, каждый третий — в магазин и каждый пятый решал математические задачи.)
Приведём формулу для $A_i$:
$$
\def\sfrac#1#2{\frac{\scriptstyle #1}{\scriptstyle #2}}
A_i=1-\left[2^{\left[\sfrac i2\right]-\sfrac i2}\right]-\left[2^{\left[\sfrac i3\right]-\sfrac i3}\right]-\left[2^{\left[\sfrac i5\right]-\sfrac i5}\right]+\left[2^{\left[\sfrac i{30}\right]-\sfrac i{30}}\right].\tag4
$$
Упражнения
- Докажите формулу (4).
- Выведите формулу для числа дел, которые будет делать Петя в $k$-й день.
Из формулы (4) сразу видно, что $A_{i+30}=A_i$. Вычислить значения первых тридцати коэффициентов вы, конечно, сумеете сами.
Решение задачи 5. Эта задача следует из задачи 2. Действительно,
$$
\begin{aligned}
\psi(x)-\psi(\sqrt x)&=\theta(x)+\theta(\sqrt x)+\ldots\ge\theta(x),\\
\text{а}\quad
\psi(x)-2\psi(\sqrt x)&=\theta(x)-\theta(\sqrt x)+\ldots\le\theta(x).
\end{aligned}
$$
Решение задачи 6. Поскольку $a_p=[\log_px]$,
$$
a_p\log p\le\log_px\log p=\log x,\quad(a_p+1)\log p\gt\log x.
$$
Поэтому
$$
\begin{gathered}
\psi(x)=\textstyle\sum\limits_{p\le x}a_p\log p\le\sum\limits_{p\le x}\log x=\pi(x)\log x,\\
\psi(x)+\theta(x)=\textstyle\sum\limits_{p\le x}(a_p+1)\log x\gt\sum\limits_{p\le x}\log x=\pi(x)\log x,
\end{gathered}
$$
откуда
$$
\dfrac{\psi(x)}{\log x}\lt\pi(x)\lt\dfrac{\psi(x)+\theta(x)}{\log x}.
$$
