Текст статьиКузьмин Е. Н., Ширшов А. И. О числе e // Квант. — 1979. — № 8. — С. 3—8.
1. Что такое e?
В школе вы ещё в пятом классе знакомитесь с числом $\pi$, имеющим очень длинную историю, начало которой теряется в глубине веков, в античном мире. Затем вы встречаетесь с ним в восьмом, девятом, десятом классах. С числом $e$ вы сталкиваетесь только в конце десятого класса. Однако это замечательное число, вошедшее в обиход в XVIII веке вместе с развитием математического анализа, играет в современной математике едва ли не более важную роль.
В школьном учебнике для числа $e$ даются два определения. Во втором (первое нам не понадобится) числом $e$ называется предел последовательности $x_n=\left(1+\dfrac1n\right)^n$. Докажем, что этот предел существует.
Лемма 1. Для любых $m$, $n$
$$
\left(1+\dfrac1n\right)^n\lt\left(1+\dfrac1m\right)^{m+1}.\tag1
$$
Неравенство (1) очень легко доказывается при помощи знаменитого неравенства Коши:
$$
\sqrt[\scriptstyle n~]{a_1\cdot a_2\cdot\ldots\cdot a_n}\lt\dfrac{a_1+a_2+\ldots+a_n}n,\tag2
$$
где $a_1$, $a_2$, $\ldots$, $a_n$ — положительные числа, среди которых есть различные. Из (2)
$$
\sqrt[\scriptstyle m+n+1~]{\left(1+\dfrac1n\right)^n\left(1-\dfrac1{m+1}\right)^{m+1}}\lt\dfrac{n\left(1+\dfrac1n\right)+(m+1)\left(1-\dfrac1{m+1}\right)}{m+n+1}=1,
$$
откуда $\left(1+\dfrac1n\right)^n\left(1-\dfrac1{m+1}\right)^{m+1}\lt1$ и $\left(1+\dfrac1n\right)^n\lt\left(1+\dfrac1m\right)^{m+1}$.
Доказательство. Обозначим $\left(1+\dfrac1n\right)^{n+1}$ через $y_n$. Согласно лемме 1, $x_{n(n+2)}\lt y_{n+1}$, т. е.
$$
\left(1+\dfrac1{n(n+2)}\right)^{n(n+2)}\lt\left(1+\dfrac1{n+1}\right)^{n+2}.
$$
Значит,
$$
\left(1+\dfrac1{n(n+2}\right)^n\lt1+\dfrac1{n+1}.
$$
Следовательно, $\left(1+\dfrac1{n(n+2)}\right)^n=\dfrac{(n+1)^{2n}}{n^n(n+2)^n}\lt\dfrac{n+2}{n+1}$. Поэтому $\left(\dfrac{n+1}n\right)^n\lt\left(\dfrac{n+2}{n+1}\right)^{n+1}$ или $x_n\lt x_{n+1}$.
Из лемм 1, 2 и теоремы Вейерштрасса вытекает, что последовательность $(x_n)$ имеет предел. Обозначение $e$ для этого предела было введено Л. Эйлером (1707—1783).
Упражнение. Докажите, что $\lim\limits_{n\to\infty}y_n=e$ и что для любых $m$, $n$
$$x_n\lt e\lt y_m.$$
Число $e$ можно определить ещё и как предел последовательности $s_n=1+\dfrac1{1!}+\dfrac1{2!}+\ldots+\dfrac1{n!}$. Докажем это. По формуле Ньютона
$$
\begin{gather*}
x_n=1+n\cdot\dfrac1n+\dfrac{n(n-1)}{2!}\cdot\dfrac1{n^2}+\ldots+\dfrac{n(n-1)\cdot\ldots\cdot(n-k+1)}{k!}\cdot\dfrac1{n^k}+\ldots+\dfrac1{n^n}=\\
=1+1+\dfrac1{2!}\left(1-\dfrac1n\right)+\ldots+\dfrac1{k!}\left(1-\dfrac1n\right)\left(1-\dfrac2n\right)\cdot\ldots\cdot\left(1-\dfrac{k-1}n\right)+\ldots\\
\ldots+\dfrac1{n!}\left(1-\dfrac1n\right)\left(1-\dfrac2n\right)\cdot\ldots\cdot\left(1-\dfrac{n-1}n\right).\tag3
\end{gather*}
$$
(Из (3) тоже видно, что последовательность $(x_n)$ — возрастающая.) Отбрасывая множители в круглых скобках, мы увеличим каждое слагаемое в правой части равенства (3). Следовательно, $x_n\lt s_n$ (при $n\gt1$).
Фиксируем теперь произвольное $k\gt1$. Считая, что $n\gt k$, отбросим в правой части равенства (3) все слагаемые, начиная с $(k+2)$-го. Получим
$$
x_n\gt1+1+\dfrac1{2!}\left(1-\dfrac1n\right)+\ldots+\dfrac1{k!}\left(1-\dfrac1n\right)\left(1-\dfrac2n\right)\cdot\ldots\cdot\left(1-\dfrac{k-1}n\right).\tag4
$$
При $n\to\infty$ (и фиксированном $k$) правая часть неравенства (4) стремится к $s_k$. Переходя в неравенстве (4) к пределу, получим $e\ge s_k$. Итак, $x_n\lt s_n\le e$. Из $\lim\limits_{n\to\infty}x_n=e$ получаем $\lim\limits_{n\to\infty}s_n=e$. Таким образом,
$$
e=1+\dfrac1{1!}+\dfrac1{2!}+\ldots+\dfrac1{n!}+{\ldots}.\tag5
$$
Последовательностью $(s_n)$ гораздо удобнее пользоваться для вычисления приближённых значений числа $e$, чем последовательностью $(x_n)$. Оценим разность $e-s_n$. Из (5)
$$
\begin{gather*}
e-s_n=\dfrac1{(n+1)!}+\dfrac1{(n+2)!}+\ldots=
\dfrac1{(n+1)!}\left[1+\dfrac1{n+2}+\dfrac1{(n+2)(n+3)}+\ldots\right]\lt\\
\lt\dfrac1{(n+1)!}\left[1+\dfrac1{n+2}+\dfrac1{(n+2)^2}+\ldots\right]=
\dfrac1{(n+1)!}\cdot\dfrac1{1-\dfrac1{n+2}}=\dfrac{n+2}{(n+1)^2\cdot n!}\lt\dfrac1{n\cdot n!}.
\end{gather*}
$$
Полученный результат можно записать в виде равенства
$$
e=s_n+\dfrac{\theta_n}{n\cdot n!}\quad(0\lt\theta_n\lt1).\tag6
$$
Из (6) легко получить иррациональность числа $e$. Действительно, предположим, что $e=\dfrac pq$. Тогда $q!\,e$ — целое число. Из (6) при $n=q$
$$
q!\,e=q!+q!+\dfrac{q!}{2!}+\ldots+\dfrac{q!}{q!}+\dfrac{\theta_q}{q}.
$$
Получается, что и $\dfrac{\theta_q}q$ — целое число, что, очевидно, неверно. Вот первые десятичные знаки числа $e$:
$$
e=2{,}718281828459045{\ldots}.
$$
2. Задача о разбиениях
Число $e$, баловень математического анализа и теории функций, довольно неожиданно возникает в некоторых комбинаторных задачах. Рассмотрим одну такую задачу.
Начнём с примера. Двухэлементное множество $\{a_1,a_2\}$ можно разбить на непересекающиеся подмножества (говоря о разбиениях, их называют классами) двумя способами: это — «поэлементное» разбиение $\{a_1\}$, $\{a_2\}$ и вырожденное «целое» разбиение $\{a_1,a_2\}$. Аналогичные разбиения имеются (при $n\gt2$) у любого $n$-элементного множества. При $n=3$ к ним добавляются ещё три разбиения (рис. 1).
Рис. 1
Обозначим число разбиений $n$-элементного множества через $\tau(n)$. Очевидно, $\tau(0)=\tau(1)=1$. Как мы только что отметили, $\tau(2)=2$, $\tau(3)=5$. А чему равно $\tau(n)$ для произвольного $n$? Нельзя ли для $\tau(n)$ указать какую-нибудь простую формулу.
Как это часто бывает в комбинаторных задачах, легко найти рекуррентное соотношение, связывающее $\tau(n)$ со значениями $\tau(k)$ для $k\lt n$.
Пусть $M=\{a_1,a_2,\ldots,a_n\}$. Paccopтируем все разбиения множества $M$ в зависимости от того, чему равно число $k$ элементов класса, в который попадает при данном разбиении элемент $a_1$. Число $k$ может быть равно 1, 2, $\ldots$, $n$. При фиксированном $k$ число таких разбиений равно, очевидно, $C_{n-1}^{k-1}\tau(n-k)$. Таким образом, $\tau(n)=\sum\limits_{k=1}^nC_{n-1}^{k-1}\tau(n-k)$. Легко проверить, что
$$
\textstyle\sum\limits_{k=1}^nC_{n-1}^{k-1}\tau(n-k)=\sum\limits_{k=0}^{n-1}C_{n-1}^k\tau(k).
$$
Окончательно,
$$
\tau(n)=\textstyle\sum\limits_{k=0}^{n-1}C_{n-1}^k\tau(k).\tag7
$$
При помощи формулы (7) нетрудно подсчитать, что $\tau(4)=15$, $\tau(5)=52$, $\tau(6)=203$, $\tau(7)=877$, $\tau(8)=4140$ — с ростом $n$ числа $\tau(n)$ быстро возрастают.
Рекуррентной формулой (7) мы воспользуемся для доказательства любопытного утверждения, в котором неожиданно появляется число $e$:
$$
e\cdot\tau(n)=\dfrac{1^n}{1!}+\dfrac{2^n}{2!}+\ldots+\dfrac{k^n}{k!}+\ldots\quad(n\ge1).\tag8
$$
Доказательство. Применим метод математической индукции. При $n=1$ (8) верно в силу (5). Предположим теперь, что (8) верно для всех чисел, меньших некоторого $n$; докажем, что тогда оно верно и для $n$. По (5) и по предположению индукции справедливы равенства
$$
\colsep{0pt}{\begin{array}{lcccccccccccc}
e\cdot\tau(0)&{}={}&1&{}+{}&\dfrac1{1!}&{}+{}&\dfrac1{2!}&{}+{}&\ldots&{}+{}&\dfrac1{k!}&{}+{}&\ldots\\[8pt]
e\cdot\tau(1)&{}={}&&&\dfrac1{1!}&{}+{}&\dfrac2{2!}&{}+{}&\ldots&{}+{}&\dfrac k{k!}&{}+{}&\ldots\\[8pt]
e\cdot\tau(2)&{}={}&&&\dfrac{1^2}{1!}&{}+{}&\dfrac{2^2}{2!}&{}+{}&\ldots&{}+{}&\dfrac{k^2}{k!}&{}+{}&\ldots\\
&&&&&\mathclap{.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\quad.}\\
e\cdot\tau(n-1)&{}={}&&&\dfrac{1^{n-1}}{1!}&{}+{}&\dfrac{2^{n-1}}{2!}&{}+{}&\ldots&{}+{}&\dfrac{k^{n-1}}{k!}&{}+{}&\ldots
\end{array}}
$$
(Бесконечные суммы в правых частях надо, естественно, понимать как пределы частичных сумм.) Сложим почленно эти равенства с коэффициентами, соответственно, $C_{n-1}^0$, $C_{n-1}^1$, $C_{n-1}^2$, $\ldots$, $C_{n-1}^{n-1}$. В левой части, согласно (7), мы получим $e\cdot\tau(n)$, в правой
$$
1+\dfrac{\phi(1)}{1!}+\dfrac{\phi(2)}{2!}+\ldots+\dfrac{\phi(k)}{k!}+\ldots
$$
где $\phi(t)=C_{n-1}^0+C_{n-1}^1t+C_{n-1}^2t^2+\ldots+C_{n-1}^{n-1}t^{n-1}=(1+t)^{n-1}$. Следовательно,
$$
e\cdot\tau(n)=1+\dfrac{2^{n-1}}{1!}+\dfrac{3^{n-1}}{2!}+\ldots+\dfrac{(k+1)^{n-1}}{k!}+\ldots=
\dfrac{1^n}{1!}+\dfrac{2^n}{2!}+\dfrac{3^n}{3!}+\ldots+\dfrac{(k+1)^n}{(k+1)!}+{\ldots}.
$$
что и требовалось доказать. Из (8) получается красивая формула
$$
\tau(n)=\dfrac1e\sum\limits_{k=1}^\infty\dfrac{k^n}{k!}
$$
неудобная, однако, для вычисления $\tau(n)$. Ниже мы получим прямые (в смысле «не рекуррентные») конечные (не через ряд) формулы для вычисления $\tau(n)$.
Назовём рангом данного разбиения число классов, из которых оно состоит. Обозначим через $c_{n,k}$ число разбиений ранга $k$ $n$-элементного множества. Очевидно, ранг может принимать только значения 1, 2, $\ldots$, $n$; поэтому
$$
\tau(n)=\textstyle\sum\limits_{k=1}^nc_{n,k}.\tag9
$$
При $k\gt n$ положим $c_{n,k}=0$.
Для чисел $c_{n,k}$ легко получить рекуррентное соотношение. Пусть $M=\{a_1,a_2,\ldots,a_n\}$, $M'=\{a_2,\ldots,a_n\}$. Разделим разбиения множества $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\gt1$, $k\gt1$
$$
c_{n,k}=c_{n-1,k-1}+k\cdot c_{n-1, k}.\tag{10}
$$
Докажем, что при $n\ge1$, $k\ge1$
$$
c_{n,k}=\sum\limits_{s=0}^{k-1}\dfrac{(-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\gt1$ и $n=1$, то
$$
b_{1,k}=\sum\limits_{s=0}^{(k-1)!}\dfrac{(-1)^s}{s!\,(k-s-1)!}=\dfrac1{(k-1)!}\sum\limits_{s=0}^{k-1}(-1)^sC_{k-1}^s=\dfrac1{(k-1)!}(1-1)^{k-1}=0=c_{1,k}.
$$
Если, наконец, $k\gt1$ и $n\gt1$, то
$$
\begin{gather*}
b_{n,k}=\sum\limits_{s=0}^{k-1}\dfrac{(-1)^s(k-s)^{n-1}}{s!\,(k-s-1)!}=\sum\limits_{s=0}^{k-1}\dfrac{(-1)^s(k-s)^{n-2}\cdot(k-s)}{s!\,(k-s-1)!}=\\
=k\sum\limits_{s=0}^{k-1}\dfrac{(-1)^s(k-s)^{n-2}}{s!\,(k-s-1)!}+\sum\limits_{s=0}^{k-1}\dfrac{(-1)^{s+1}(k-s)^{n-2}\cdot s}{s!\,(k-s-1)!}=k\cdot b_{n-1,k}+\sum\limits_{s=1}^{k-1}\dfrac{(-1)^{s+1}(k-s)^{n-2}\cdot s}{s!\,(k-s-1)!}=\\
=k\cdot b_{n-1,k}+\sum\limits_{s=1}^{k-1}\dfrac{(-1)^{s+1}(k-s)^{n-2}}{(s-1)!\,(k-s-1)!}=k\cdot b_{n-1,k}+\sum\limits_{s=0}^{k-2}\dfrac{(-1)^{s+2}(k-s-1)^{n-2}}{s!\,(k-s-2)!}=\\
=k\cdot b_{n-1,k}+\sum\limits_{s=0}^{k-2}\dfrac{(-1)^s(k-s-1)^{n-2}}{s!\,(k-s-2)!}=k\cdot b_{n-1,k}+b_{n-1,k-1}.
\end{gather*}
$$
Таким образом, числа $c_{n,k}$ и $b_{n,k}$ удовлетворяют одному и тому же peкуррентному соотношению вида (10); кроме того, их «начальные значения»: при $k=1$ (и любом $n\ge1$) и при $n=1$ (и любом $k\ge1$) совпадают. Следовательно (рис. 2), $c_{n,k}=b_{n,k}$ для любых $n\ge1$ и $k\ge1$.
Рис. 2
Из (9) и (11)
$$
\tau(n)=\sum\limits_{k=1}^n\sum\limits_{s=0}^{k-1}\dfrac{(-1)^s(k-s)^{n-1}}{s!\,(k-s-1)!}.\tag{12}
$$
Обозначим $k-s$ через $t$; тогда $1\le t\le n$. При фиксированном $t$ в двойной сумме (12) $s$ может изменяться от 0 до $n-t$. Собирая коэффициенты при $t^{n-1}$, можно формулу (12) преобразовать к виду
$$
\tau(n)=\sum\limits_{t=1}^n\left(\sum\limits_{s=0}^{n-t}\dfrac{(-1)^s}{s!}\right)\dfrac{t^{n-1}}{(t-1)!}.
$$
Числа $c_{n,k}$, имеющие ясный комбинаторный смысл, неожиданно возникают в одной алгебраической задаче, связанной с многочленами.
Положим $x^{(1)}=x$, $x^{(2)}=x(x-1)$, $x^{(3)}=x(x-1)(x-2)$ и т. д. Многочлены 1, $x^{(1)}$, $x^{(2)}$, $\ldots$, $x^{(n)}$ имеют, соответственно, степени 0, 1, 2, $\ldots$, $n$. Поэтому любой многочлен от $x$ степени не выше $n$ единственным образом представляется в виде суммы этих многочленов (с некоторыми коэффициентами). В частности,
$$
x^n=a_{n,1}x^{(1)}+a_{n,2}x^{(2)}+\ldots+a_{n,n}x^{(n)}\tag{13}
$$
для некоторых чисел $a_{n,k}$ ($n\ge1$, $1\le k\le n$). Для $k\gt1$ положим $a_{n,k}=0$. Оказывается, $a_{n,k}=c_{n,k}$. Докажем это.
Полагая в (13) $x=1$, получаем $a_{n,1}=1=c_{n,1}$. Если $k\gt1$ и $n=1$, то $a_{1,k}=0=c_{1,k}$. Пусть теперь $k\gt1$ и $n\gt1$.
$$
\begin{gather*}
\textstyle x^n=\sum\limits_{k=1}^na_{n,k}x^{(k)}=x\cdot x^{n-1}=x\cdot\sum\limits_{i=1}^{n-1}a_{n-1,i}x^{(i)}=\sum\limits_{i=1}^{n-1}a_{n-1,i}x^{(i)}[(x-i)+i]=\\
\textstyle=\sum\limits_{i=1}^{n-1}a_{n-1,i}[x^{(i)}(x-i)+ix^{(i)}]=\sum\limits_{i=1}^{n-1}a_{n-1,i}[x^{(i+1)}+ix^{(i)}]=\sum\limits_{i=1}^{n-1}a_{n-1,i}x^{(i+1)}+\sum\limits_{i=1}^{n-1}a_{n-1,i}ix^{(i)}.
\end{gather*}
$$
Сравнивая коэффициенты при $x^{(k)}$, получаем $a_{n,k}=a_{n-1,k-1}+k\cdot a_{n-1,k}$. Как и выше, из этого вытекает, что $a_{n,k}=c_{n,k}$ при всех $n$, $k$.
