О числе e

3

О числе e

1. Что такое e?

В школе вы еще в пятом классе знакомпесь с числом π, имеющим очень длинную историю, начало которого теряется в глубине веков, в античном мире *). Затем вы встречаете с ним в восемом, девятом, десятом классах. С числом e вы стalkиваете только в конце десятого класса. Однако это замечательное число, вошедшее в обиход в XVIII века вместе с развитием математического анализа, играет в современной математике едва ли не более важную роль.

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

Лемма 1. Для любых m, n

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

(1)

неравенство (1) очень легко доказывается при помощи знаменного неравенства Коши:

$$\sqrt[n]{a_1 \cdot a_2 \cdot \dots \cdot a_n} < \frac{a_1 + a_2 + \dots + a_n}{n},$$

(2)

где $a_1, a_2, \dots, a_n$ — положительные числа, среди которых есть различные**). Из (2)

$$\sqrt[n]{1 + \frac{1}{n}} \left(1 - \frac{1}{m+1}\right)^{m+1} < \frac{n \left(1 + \frac{1}{n}\right) + (m+1) \left(1 - \frac{1}{m+1}\right)}{m+n+1} = 1,$$

откуда $$\left(1 + \frac{1}{n}\right)^n \left(1 - \frac{1}{m+1}\right)^{m+1} < 1$$ и $$\left(1 + \frac{1}{n}\right)^n < \left(1 + \frac{1}{m}\right)^{m+1}.$$

Лемма 2. Последовательность $(x_n)$ – возрастаюшая.

Доказательство. Обозначим $\left(1 + \frac{1}{n}\right)^n+1$ через $y_n$. Согласно лемме 1, $x_{n(n+2)} < y_{n+1}$, то есть

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

*) Много интересных подробностей о числе π можно найти в книге Ф. Кымен а и «История числа π» (М., «Наука», 1971). См. также статью А. Звонкина «Что такое π?» («Квант», 1978, № 11).

**) Постраайтесь доказать его самостояльно. Можно также прочитать его доказательство на с. 26.

4

Значит,

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

Следовательно, $$\left(1 + \frac{1}{n(n+2)}\right)^n = \frac{(n+1)^2n}{n^n(n+2)^n} < \frac{n+2}{n+1}.$$

Поэтому $$\left(\frac{n+1}{n}\right)^n < \left(\frac{n+2}{n+1}\right)^{n+1}$$ или $$x_n < x_{n+1}.$$

Из лемм 1, 2 и теоремы Вейерштраса вытекает, что последовательность $(x_n)$ имеет предел. Обозначение $e$ для этого предела было введено Л. Эйлером (1707—1783).

Упражнение. Докажите, что $$\lim_{n \to \infty} y_n = e$$ и что для любых $m, n$

$$x_n < e < y_m.$$

Число $e$ можно определить еще и как предел последовательности $s_n = 1 + \frac{1}{1!} + \frac{1}{2!} + \dots + \frac{1}{n!}$. Докажем это. По формуле Ньютона

$$x_n = 1 + n \cdot \frac{1}{n} + \frac{n(n-1)}{2!} \cdot \frac{1}{n^2} + \dots + \frac{n(n-1) \cdot \dots \cdot (n-k+1)}{k!} \cdot \frac{1}{n^k} + \dots + \frac{1}{n^n} = 1 + 1 + \frac{1}{2!} \left(1 - \frac{1}{n}\right) + \dots + \frac{1}{k!} \left(1 - \frac{1}{n}\right) \times \left(1 - \frac{2}{n}\right) \dots \dots \left(1 - \frac{k-1}{n}\right) \times \left(1 - \frac{2}{n}\right) \dots \dots \left(1 - \frac{n-1}{n}\right).$$

(Из (3) тоже видно, что последовательность $(x_n)$ — возрастоящая.) Отбрасывая множители в круглых скобках, мы увеличим каждое слагаемое в правой части равенства (4). Следовательно, $x_n < s_n$ (при $n > 1$).

Фиксируем теперь произвольное $k > 1$. Считая, что $n > k$, отбросим в правой части равенства (3) все слагаемые, начиная с $(k+2)$-го. Получим

$$x_n > 1 + 1 + \frac{1}{2!} \left(1 - \frac{1}{n}\right) + \dots + \frac{1}{k!} \left(1 - \frac{1}{n}\right) \left(1 - \frac{2}{n}\right) \dots \dots \left(1 - \frac{k-1}{n}\right).$$

При $n \to \infty$ (и фиксированном $k$) правачасть неравенства (4) стремится к $s_k$. Переходя в неравенстве (4) к пределу, получим $e \geqslant s_k$. Итак, $x_n < s_n \leqslant e$. Из $$\lim_{n \to \infty} x_n = e$$ получаем $$\lim_{n \to \infty} s_n = e.$$ Таким образом,

$$e = 1 + \frac{1}{1!} + \frac{1}{2!} + \dots + \frac{1}{n!} + \dots.$$

Последовательность $(s_n)$ гораздо удобнее пользоваться для вычисления приближенных значений числа $e$, чем последовательность $(x_n)$. Оценим разность $e - s_n$. Из (5)

$$e - s_n = \frac{1}{(n+1)!} + \frac{1}{(n+2)!} + \dots =$$

$$= \frac{1}{(n+1)!} \left[ 1 + \frac{1}{n+2} + \frac{1}{(n+2)(n+3)} + \dots \right] <$$

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

$$= \frac{1}{(n+1)!} \cdot \frac{1}{1 - \frac{1}{n+2}} = \frac{n+2}{(n+1)^2 \cdot n!} < \frac{1}{n \cdot n!}.$$

Полученный результат можно записать в виде равенства

$$e = s_n + \frac{\theta_n}{n \cdot n!} \quad (0 < \theta_n < 1).$$

Из (6) легко получить irrationalность числа $e$. Действительно, предположим, что $e = \frac{p}{q}$. тогда $q!e$ — целое число. Из (6) при $n=a$

$$q!e = q! + q! + \frac{q!}{2!} + \dots + \frac{q!}{q!} + \frac{\theta_q}{q}.$$

Получается, что и $\frac{\theta_q}{q}$ — целое число, что, очевидно, неверно. Вот первые десятичные знаки числа $e$.

$$e = 2,718281828459045\dots$$

2. Задча о разбиениях

Число $e$, баловень математического анализа и теории функций, довольно неожиданно возникает в некоторых комбинаторных задачах. Рассмотрим одну такую задачу.

Начнем с примера. Двухlementное множество $\{a_1, a_2\}$ можно разбить на непересекающийся подмножества (говора о разбиениях, их называют классами) двумя способами: это — «позелемное» разбиение $\{a_1\}, \{a_2\}$ и вырожденное «целое» разбиение $\{a_1, a_2\}$. Аналогичные разбиения имеются (при $n>2$) у любого $n$-элементного множества. При $n=3$ к ним добавляются еще три разбиения (рис. 1).

Обозначим число разбиения $n$-элементного множества через $\tau(n)$ *).

Очевидно, $\tau(0) = \tau(1) = 1$. Как мы только что отметили, $\tau(2) = 2$, $\tau(3) = 5$. А чему равно $\tau(n)$ для произвольного $n$? Нельзя ли для $\tau(n)$ указывать какую-нибудь простую формулу?

Как это часто бывают в комбинаatorных задачах, легко найти рекуррентное соотношение, связывающее $\tau(n)$ со значениями $\tau(k)$ для $k < n$.

Пусть $M = \{a_1, a_2, \dots, a_n\}$. Рассортируем все разбиения множества $M$ в зависимости от того, чем равно число $k$ элементов класса, в котором попадает при данном разбиении элемент $a_1$. Число $k$ может быть равно 1,2,…,$n$. При фиксированном $k$ число таких разбиений равно, очевидно, $C_{n-1}^{k-1}\tau(n-k)$.

Таким образом, $\tau(n) = \sum_{k=1}^{n} C_{n-1}^{k-1}\tau(n-k)$. Легко проверить, что

$$\sum_{k=1}^{n} C_{n-1}^{k-1}\tau(n-k) = \sum_{k=0}^{n-1} C_{n-1}^{k-1}\tau(k).$$

Okончательно,

$$\tau(n) = \sum_{k=0}^{n-1} C_{n-1}^{k-1}\tau(k).$$

При помощи формулы (7) нетрудно подсчитать, что $\tau(4)=15$, $\tau(5)=52$, $\tau(6)=203$, $\tau(7)=877$, $\tau(8)=4140$ — с ростом $n$ числа $\tau(n)$ быстро возрастает.

*) Числа $\tau(n)$ называются числами Белла («Квант», 1978, № 7).

6

Рекуррентной формулой (7) мы воспользовемся для доказательства любитного утверждения, в котором необходимо проверять число $e$:

$$e \cdot \tau(n) = \frac{1^n}{1!} + \frac{2^n}{2!} + \dots + \frac{k^n}{k!} + \dots \quad (n \geqslant 1)$$

Доказательство. Приимем метод математической индукции. При $n=1$ (8) верно в силу (5). Предположим теперь, что (8) верно для всех чисел, меньше некоторого $n$; доказем, что тогда оно верно и для $n$. По (5) и по предположению индукции справедливо равенства

$$e \cdot \tau(0) = 1 + \frac{1}{1!} + \frac{1}{2!} + \dots + \frac{1}{k!} + \dots$$

$$e \cdot \tau(1) = \frac{1}{1!} + \frac{2}{2!} + \dots + \frac{k}{k!} + \dots$$

$$e \cdot \tau(2) = \frac{1^2}{1!} + \frac{2^2}{2!} + \dots + \frac{k^2}{k!} + \dots$$

$$e \cdot \tau(n-1) = \frac{1^{n-1}}{1!} + \frac{2^{n-1}}{2!} + \dots + \frac{k^{n-1}}{k!} + \dots$$

(Бескочечные суммы в правых частях надо, естественно, понимать как предельные частичных сумм.) Сложим почленно эти равенства с коэффициентами, соответствующими $C_{n-1}^0, C_{n-1}^1, C_{n-1}^2, \dots, C_{n-1}^{n-1}$. В левой части, согласно (7), мы получим $e \cdot \tau(n)$, в правой

$$1 + \frac{\varphi(1)}{1!} + \frac{\varphi(2)}{2!} + \dots + \frac{\varphi(k)}{k!} + \dots$$

где $\varphi(t) = C_{n-1}^0 + C_{n-1}^1 t + C_{n-1}^2 t^2 + \dots + C_{n-1}^{n-1} t^{n-1} = (1+t)^{n-1}$.

Следовательно,

$$e \cdot \tau(n) = 1 + \frac{2^{n-1}}{1!} + \frac{3^{n-1}}{2!} + \dots + \frac{(k+1)^{n-1}}{k!} + \dots = \frac{1^n}{1!} + \frac{2^n}{2!} + \frac{3^n}{3!} + \dots + \frac{(k+1)^n}{(k+1)!} + \dots$$

что и требовалось доказать. Из (8) получается красивая формула

$$\tau(n) = \frac{1}{e} \sum_{k=1}^{\infty} \frac{k^n}{k!}$$

неудобная, однако, для вычисления $\tau(n)$. Ниже мы получим примые (в смысле «не рекуррентные») конечные (не через ряд) формулы для вычисления $\tau(n)$.

Назовем ранgeom данного разбиения число классов, из которых оно состоит. Обозначим через $c_{n,k}$ число разбиения ранга $k$ $n$-элементного множества $^*$. Очевидно, ранг может принимать только значения $1,2,\dots,n$; поэтому

$$\tau(n) = \sum_{k=1}^{n} c_{n,k}.$$

При $k>n$ положим $c_{n,k}=0$.

Для чисел $c_{n,k}$ легко получить рекуррентное соотношение. Пусть $M=\{a_1,a_2,\dots,a_n\}, M'=\{a_2,\dots,a_n\}$. Разделим разбиения множества

$$^*$$

*) Числа $c_{n,k}$ называются числами Стирлинга.

7

ства $M$ ранга $k$ на две групы — на разбиения, содержащие однозеленное множество $\{a_1\}$ в качестве класса разбиения, и не содержащие. Разбенный первого вида, очевидно, существует столько же, сколько разбиений множества $M'$ ранга $k-1$, то есть $c_{n-1,k-1}$; разбиений второго вида — в $k$ раз больше, чем разбиений множества $M'$ ранга $k$ (элемент $a_1$ можно поместить в любой из $k$ классов разбиения множества $M'$), то есть $k \cdot c_{n-1,k}$. Итак, при $n > 1, k > 1$

$$c_{n,k} = c_{n-1,k-1} + k \cdot c_{n-1,k}. \tag{10}$$

Докажем, что при $n \geqslant 1, k \geqslant 1$

$$c_{n,k} = \sum_{s=0}^{k-1} \frac{(-1)^s (k-s)^{n-1}}{s! (k-s-1)!}. \tag{11}$$

Обозначим правильное частное решение (11) через $b_{n,k}$. Если $k=1$, то $b_{n,1} = 1 = c_{n,1}$. Если $k > 1$ и $n=1$, то

$$b_{1,k} = \sum_{s=0}^{k-1} \frac{(-1)^s}{s! (k-s-1)!} = \frac{1}{(k-1)!} \sum_{s=0}^{k-1} (-1)^s C_{k-1}^s = \frac{1}{(k-1)!} (1-1)^{k-1} = 0 = c_{1,k}.$$

Если, наконец, $k > 1$ и $n > 1$, то

$$b_{n,k} = \sum_{s=0}^{k-1} \frac{(-1)^s (k-s)^{n-1}}{s! (k-s-1)!} = \sum_{s=0}^{k-1} \frac{(-1)^s (k-s)^{n-2} \cdot (k-s)}{s! (k-s-1)!} = k \sum_{s=0}^{k-1} \frac{(-1)^s (k-s)^{n-2}}{s! (k-s-1)!} + \sum_{s=0}^{k-1} \frac{(-1)^s+1 (k-s)^{n-2} \cdot s}{s! (k-s-1)!} = k \cdot b_{n-1,k} + \sum_{s=1}^{k-1} \frac{(-1)^s+1 (k-s)^{n-2}}{s! (k-s-1)!} = k \cdot b_{n-1,k} + \sum_{s=0}^{k-1} \frac{(-1)^s+1 (k-s)^{n-2}}{s! (k-s-1)!} = k \cdot b_{n-1,k} + b_{n-1,k-1}.$$

Таким образом, числа $c_{n,k}$ и $b_{n,k}$ удовлетворяют одному и тому же перерентному соотношению вида (10); кроме того, их «начальные значения»: при $k=1$ (и любом $n \geqslant 1$) и при $n=1$ (и любом $k \geqslant 1$) совпадают. Следовательно (рис. 2), $c_{n,k} = b_{n,k}$ для любых $n \geqslant 1$ и $k \geqslant 1$.

Из (9) и (11)

$$\tau(n) = \sum_{k=1}^{n} \sum_{s=0}^{k-1} \frac{(-1)^s (k-s)^{n-1}}{s! (k-s-1)!}. \tag{12}$$

Обозначим $k-s$ через $t$; тогда $1 \leqslant t \leqslant n$. При фиксированном $t$ в двойной сумме (12) $s$ может изменяться от 0 до $n-t$. Собирая коэффициенты при $t^{n-1}$, можно формулой (12) преобразовать к виду

$$\tau(n) = \sum_{t=1}^{n} \left( \sum_{s=0}^{n-t} \frac{(-1)^s}{s!} \right) \frac{t^{n-1}}{(t-1)!}.$$