О числе e и n!

14

О числе e и n!
Л. Г. ЛИМАНОВ

В этой заметке мы разберем задачи из статьи М. И. Башмакова «О поступление Бертрана» (см. «Квант» № 5, 1971).

Напомним, что поступатом Бертрана называется следующей итерацией: если $x > 1$, то существует простое число, заключенное между $x$ и $2x$.

Это утверждение формировал французский математик Бертран, но отыскать доказательства для него не сумел. Это удалось сделать Чебышеву, причем сделать совершенно элементарно. Правда, он воспользовался одной не элементарной формулой — формулой Стирлинга:

$$n! = \sqrt{2\pi n} \left(\frac{n}{e}\right)^n e^{\theta_n/12n},$$

где $0 < \theta_n < 1$.

В эту формулу входят два едва ли не самых замечательных числа. Первое — это всем вам известное число $n$ — отношение длины окружности к ее диаметру. второе число — это число $e$ — предел последовательности $\left(\frac{n+1}{n}\right)^n$ при $n$, стремящемся к бесконечности. Формула эта понадобилась Чебышеву для того, чтобы оценить величины $n! = 1 \cdot 2 \cdot \dots \cdot n$.

На самом же деле, чтобы доказать поступат Бертрана, можно использовать существенное менее точные оценки величины $n$!

Именно такие оценки и предлагалось доказать читателю в статье Башмакова (задача 3). С разбора этой задачи мы и научем.

Вот ее формулировка:

Докажите, что существует такое действительное число $e$, что при всех натуральных $n$, больших некоморозо $n_0$,

$$\left(\frac{n+1}{e}\right)^n < n! < n \left(\frac{n}{e}\right)^n.$$

Неравиенства $\left(\frac{n+1}{e}\right)^n < n! < n \left(\frac{n}{e}\right)^n$ можно использовать вместе формулы Стирлинга. Они, конечно, менее точны, но это и доказать их намного проще.

Остальные задачи из статьи — это, по сути дела, леммы из Чебышевского доказательства поступата Бертрана. Решить их намного проще, чем задачу 3. Заслуга Чебышева не в том, что он их решил — сделать это нетрудно, — а в том, что он их формулировал и нашел, как с помощью этих утверждений получить оценки для произведения (и, тем самым, для количества) простых чисел, не превосходящих $x$, и доказать поступат Бертрана.

Решение задачи 3. Прием пока без доказательства, что такое число $e$, что при всех натуральных $n$,

$$\left(\frac{n+1}{n}\right)^n < e < \left(\frac{n+1}{n}\right)^{n+1},$$

действительно существует. (Доказательство существования будет приведено чуть ниже.)

15

Мы хотим доказать, что $\left(\frac{n+1}{e}\right)^n < n! < n \left(\frac{n}{e}\right)^n$ или (что то же самое)
$\frac{(n+1)^n}{n!} < e^n < \frac{n^n}{(n-1)!}$ при $n$, бóльших неокоторого $n_0$.

Пусть для неокоторого $k$ доказано, что $\frac{(k+1)^k}{k!} < e^k$. Но
$\frac{(k+2)^{k+1}}{(k+1)!} / \frac{(k+1)^k}{k!} = \left(\frac{k+2}{k+1}\right)^{k+1} < e$. Поэтому $\frac{(k+2)^{k+1}}{(k+1)!} < e^{k+1}$.

Таким образом, наше утверждение верно и для $k+1$, а значит, и для $k+2, k+3$ и т. д. Точно так же из предположения

$$e^k < \frac{k^k}{(k-1)!}$$

выводится, что

$$e^{k+1} < \frac{(k+1)^{k+1}}{(k)!}.$$

Действительно,

$$\frac{(k+1)^{k+1}}{k!} / \frac{k^k}{(k-1)!} = \left(\frac{k+1}{k}\right)^{k+1} > e.$$

Остается доказать, что $e$ существует, и найти начальные значения для $n$ в каждом из неравенств

$$\left(\frac{n+1}{e}\right)^n < n!, n! < n \left(\frac{n}{e}\right)^n.$$

Доказательство существования $e$

Условия называть совокупность действительных чисел $x$, удовлетворяющих неравенству $a \leqslant x \leqslant b$, отрезком с концами $a$ и $b$ (отрезок с концами $a$ и $b$ обозначается через $[a, b]$).

При доказательстве существования числа $e$ мы будем пользоваться следующим свойствам действительных чисел: если есть последовательность отрезков $[a_i, b_i]$, где $a_i \leqslant a_{i+1} < b_{i+1} \leqslant b_i$ ($i=1, 2, \dots$) (о такой последовательности говорят, что она является последовательностью вложенных отрезков), то существует точка $\alpha$, общая для всех этих отрезков.

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

Упражнения

1. Проверьте, что следующие свойства действительных чисел эквивалентны; если принять любое из них без доказательства, то остальные из него выводятся.
   a) У всякой последовательности вложенных отрезков есть хотя бы одна общая точка.
   b) Всякая ограниченная monotонно возрастающая последовательность имеет предел.
   b) Всякая последовательность $\{a_i\}(i=1, 2, \dots)$, в которой для любого $\varepsilon > 0$ можно указать такое $N$ (зависшее, разумется, от $\varepsilon$), что $|a_n - a_m| < \varepsilon$ при $m, n > N$ имеет предел. (Такие последовательности называются последовательностями Коши.)
   r) Всякое ограниченное сверху множество действительных чисел имеет точную версию граны, то есть можно указать такое число $\alpha$, что все принадлежшие этому множеству числа не больше $\alpha$, но для всякого числа $\beta$, меньше $\alpha$, найдет число из этого множества, больше $\beta$.
   d) Из всякого семейства отрезков, покрывающих отрезок $[a, b]$, можно выделить конечное семейство отрезков, покрывающих отрезок $[a, b]$. (Мы говорим, что система $M$ отрезков покрывает отрезок $[a, b]$, если для всякого $x$, принадлежшее отрезку $[a, b]$, найдется отрезок из системы $M$, содержащий $x$.)

16

Покажем теперь, что последовательность $\left(\frac{n+1}{n}\right)^n$ — монотонно возрастищая. Для этого нужно, чтобы при любом $n\left(\frac{n+1}{n}\right)^n$ было меньше $\left(\frac{n+2}{n+1}\right)^{n+1}$.

$$\left(\frac{n+1}{n}\right)^n < \left(\frac{n+2}{n+1}\right)^{n+1}$$

С помощью несложных преобразований это неравенство можно привести к такому виду:

$$[(n^2+2n+1)^n - (n^2+2n)^n](n+1) < (n^2+2n)^n.$$

[Вот промежуточные неравенства: $(n+1)^{2n+1} < (n+2)^{n+1}n^n$ и $(n^2+2n+1)^n(n+1) < (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 < n(n^2+2n+1)^{n-1}$. Поэтому неравенство (1) будет доказано, если мы докажем такое неравенство:

$$(n^2+2n+1)^{n-1}(n+1) < (n^2+2n)^{n-1}(n+2).$$

Оно в свою очередь (это оказывается точно так же) следует из неравенства

$$(n^2+2n+1)^{n-2}(n+1) < (n^2+2n)^{n-2}(n+2).$$

Повторяя эти рассудения, мы убеждаемся, что неравенство (1) следует из очевидного неравенства

$$n+1 < n+2.$$

Еще проще показать, что при любом натуральном $n$

$$\left(\frac{n+1}{n}\right)^{n+1} > \left(\frac{n+2}{n+1}\right)^{n+2}.$$

В самом деле, неравенство (2) эквивалентно неравенству

$$(n+1)^{2n+3} > (n+2)^{n+2}n^{n+1}.$$

Позному достаточно показать, что

$$[(n^2+2n+1)^{n+1} - (n^2+2n)^{n+1}](n+1) > (n^2+2n)^{n+1}.$$

Но

$$(n^2+2n+1)^{n+1} - (n^2+2n)^{n+1} > (n^2+2n)^{n+1}(n+1),$$

откуда

$$[(n^2+2n+1)^{n+1} - (n^2+2n)^{n+1}](n+1) > (n^2+2n)^{n+1}(n+1)^2 > (n^2+2n)^{n+1}(n^2+2n) = (n^2+2n)^{n+1},$$

то есть неравенство (3), а значит, и неравенство (2), — доказано.

Итак, мы доказали, что последовательность $a_n = \left(\frac{n+1}{n}\right)^n$ монотонно возрастищая, а последовательность $b_n = \left(\frac{n+1}{n}\right)^{n+1}$ монотонно убивает. Кроме того, $a_n < b_n$, поскольку $\frac{n+1}{n} > 1$. Таким образом последовательность отрезков с концами $a_i$, $b_i$ является последовательностью вложенных отрезков и длина $k$-го отрезка равна $\left(\frac{k+1}{k}\right)^k \cdot \frac{1}{k}$, то есть при росте $k$ она стремится к нулю. Поэтому у всех этих отрезков естьровно одна общая точка. Соответствующей ей число и называется числом $e$.

Можно вычислить сколько угодно десятичных знаков числа $e$. Вот первые несколько: $e=2,71828...$

18

1. Доказать, что
   $$T(x) = \psi(x) + \psi\left(\frac{x}{2}\right) + \psi\left(\frac{x}{3}\right) + \dots$$

2. Доказать, что
   $$\psi(x) = \theta(x) + \theta(\sqrt{x}) + \theta(\sqrt[3]{x}) + \theta(\sqrt[4]{x}) + \dots$$

Воспользовавшись результатом задачи 1, $S(x)$ можно записать так:
$$S(x) = A_1\psi(x) + A_2\psi\left(\frac{x}{2}\right) + A_3\psi\left(\frac{x}{3}\right) + \dots$$

3. Проверить, что коэффициенты $A_1, A_2, A_3, \dots$ меняются с перiodом 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.

4. Докажите, что коэффициенты $A_1, A_2, A_3, \dots$ меняются с перiodом 30 и что для первых тридцати значений $n$ коэффициенты $A_n$ составляют следующую последовательность: 1, 0, 0, 0, 0, —1, 1, 0, 0, —1, 1, —1, 1, —1, 0, 0, 1, —1, 1, —1, 0, 0, 0, 0, 1, —1.

5. Докажите, что
   $$\psi(x) - 2\psi(\sqrt{x}) \leq \theta(y) \leq \psi(x) - \psi(\sqrt{x}).$$

6. Докажите, что
   $$\frac{\psi(x)}{\log x} < \pi(x) < \frac{\psi(x) + \theta(x)}{\log x}.$$

Решение задачи 1. Заметим, что $a_p = [\log_p x]$. Вычисляем, с каким коэффициентом входит $\log p$ в сумму $\psi(x) + \psi\left(\frac{x}{2}\right) + \dots$ В $\psi\left(\frac{x}{i}\right)$ логарифм $p$ входит с коэффициентом $\left[\log_p \frac{x}{i}\right]$, значит, общий коэффициент при $\log p$ равен $\sum_{i=1}^{\infty} \left[\log_p \frac{x}{i}\right]$. Вычитем из каждого слагаемого единицу и преобразуем его: $\left[\log_p \frac{x}{i}\right] - 1 = \left[\log_p \frac{x}{i} - 1\right] = \left[\log_p \frac{x_1}{i}\right]$, где $x_1 = \frac{x}{p}$. Поэтому $\sum \left[\log_p \frac{x}{i}\right] = \left[\frac{x}{p}\right] + \sum \left[\log_p \frac{x_1}{i}\right]$. Повторяя наше преобразование, мы получим такое равенство:
$$\sum \left[\log_p \frac{x}{i}\right] = \sum_{i=1}^{\infty} \left[\frac{x}{p^i}\right].$$

Итак, коэффициент при $\log p$ в сумме $\psi(x) + \psi\left(\frac{x}{2}\right) + \dots$ равен $\sum_{i=1}^{\infty} \left[\frac{x}{p^i}\right]$. Заметим теперь, что $T(x) = \sum_{i \leq x} \log i$ тоже можно представить в таком виде: $T(x) = \sum_{p \leq x} c_p \log p$, где $p$ — простые числа.

Упражнения

12. Докажите, что если $k$ — натуральное число, то $\left[\frac{x}{k}\right] = \left[\frac{x}{k}\right]$ и при $x > 1 [\log_h[x]] = [\log_hx]$.

13. Убедитесь, что коэффициент $c_p$ равен

$$\sum_{i=1} \left[ \frac{[x]}{p^i} \right].$$

Указание. Представьте $T(x)$ в виде $\log([x])$.

Решив упражнения 12 и 13, выполностью решите задачу 1.

Решение задачи 2. Решение этой задачи похож на решение задачи 1: нужно убедиться, что коэффициент при $p$ в сумме $\theta(x) + \theta(\sqrt{x}) + \cdots$ равен $[\log_p x]$. Следать это совсем просто. $\log p$ входит слагаемым в $\theta(\sqrt{x})$, если $\sqrt{x} \geq p$, то есть $\log_p x \geq i$. Поэтому в $\sum \theta(\sqrt{x})$ логарифм $p$ входит слагаемым $k$ раз, где $k$ определяется из неравенства $k + 1 > \log_p x \geq k$, то есть $[\log_p x]$ раз.

Решение задачи 4. Эта задача очень похож на задачу M92 (см. «Квант» № 7, 1971).

Действительно, ее можно формулировать следующим образом:

В первую же поэзду в маазин Петя купил себе много маленьких шоколадок. Он решил, что в скучные дни ему следует съедать три шоколадки, в те дни, когда он занят только одним делом — две, а в остальные — по одной. Тогда $A_i + 2$ равно числу шоколадок, которые Петя съел в $i + 1$ день. (Напомним, что Петя каждый второй день зделил купаться, каждый третий — в маазин и каждый пятый решал математические задачи).

Приведем формулу для $A_i$:

$$A_i = 1 - [2^{[i/2] - i/2}] - [2^{[i/3] - i/3}] - [2^{[i/5] - i/5}] + [2^{[i/30] - i/30}].$$

Упражнения

14. Докажите формулу (4).
15. Выведите формулу для числа дел, которые будет делать Петя в $k$-й день.

Из формулы (4) сразу видно, что $A_{i+30} = A_i$. Вычислить значения первых трицати коэффициентов вы, конечно, сумме сами.

Решение задачи 5. Эта задача следует из задачи 2. Действительно,

$$\psi(x) - \psi(\sqrt{x}) = \theta(x) + \theta(\sqrt{x}) + \cdots \geq \theta(x),$$

$$\psi(x) - 2\psi(\sqrt{x}) = \theta(x) - \theta(\sqrt{x}) + \cdots \leq \theta(x).$$

Решение задачи 6. Поскольку $a_p = [\log_p x]$,

$$a_p \log p \leq \log_p x \log p = \log x, \quad (a_p + 1) \log p > \log x.$$

Позному

$$\psi(x) = \sum_{p \leq x} a_p \log p \leq \sum_{p \leq x} \log x = \pi(x) \log x,$$

$$\psi(x) + \theta(x) = \sum_{p \leq x} (a_p + 1) \log x > \sum_{p \leq x} \log x = \pi(x) \log x,$$

откуда

$$\frac{\psi(x)}{\log x} < \pi(x) < \frac{\psi(x) + \theta(x)}{\log x}.$$