Kvant Math Problem 485
The interval is
Verified: no
Verdicts: SKIP + SKIP
Solve time: 8m14s
Source on kvant.digital
Problem
- Prove that the number $e$ is between the numbers $a_n=\left(1+\dfrac1n\right)^n$ and $b_n=\left(1+\dfrac1n\right)^{n+1}$ for any natural $n$.
- Prove that the sequence $c_n=\left(1+\dfrac1{4n}\right)\left(1+\dfrac1n\right)^n$ is monotonically increasing, while the sequence $d_n=\left(1+\dfrac1{2n}\right)\left(1+\dfrac1n\right)^n$ is monotonically decreasing.
- Divide the segment $[a_n;b_n]$ into four equal parts. In which of them does the number $e$ lie?
- Divide the segment $[a_n;b_n]$ into eight equal parts. In which of them does $e$ lie?
- What if the segment $[a_n;b_n]$ is divided into $2^k$ equal parts (in this problem it is interesting to obtain the answer for sufficiently large $n$, for example, for $n\gt2^k$)?
$\Big($Recall that $e=\lim_{n\to\infty}\left(1+\dfrac1n\right)^n=2{,}718\ldots$, see the textbook Algebra and the Fundamentals of Analysis 10, §§ 106, 113.$\Big)$
T. Martynenko, R. P. Ushakov
Exploration
The interval is
$$[a_n,b_n],\qquad a_n=\left(1+\frac1n\right)^n,\qquad b_n=\left(1+\frac1n\right)^{n+1}.$$
Since
$$b_n-a_n=\frac1n,a_n,$$
the relative position of $e$ inside the interval is governed by the quantity
$$\frac{e-a_n}{b_n-a_n} =n!\left(\frac{e}{a_n}-1\right).$$
To understand this quantity, write
$$\ln a_n=n\ln!\left(1+\frac1n\right).$$
Using the alternating expansion
$$\ln(1+x)=x-\frac{x^2}{2}+\frac{x^3}{3}-\frac{x^4}{4}+\cdots \qquad (0<x<1),$$
we obtain
$$\ln a_n =1-\frac1{2n}+\frac1{3n^2}-\frac1{4n^3}+\frac1{5n^4}-\cdots .$$
Hence
$$1-\ln a_n =\frac1{2n}-\frac1{3n^2}+\frac1{4n^3}-\cdots .$$
The first approximation is
$$e=a_n\exp!\left(\frac1{2n}-\frac1{3n^2}+O(n^{-3})\right),$$
so
$$\frac{e}{a_n} =1+\frac1{2n}-\frac5{24n^2}+O(n^{-3}),$$
and therefore
$$n!\left(\frac ea_n-1\right) =\frac12-\frac5{24n}+O(n^{-2}).$$
Thus $e$ is slightly to the left of the midpoint of $[a_n,b_n]$, and tends to the midpoint as $n\to\infty$.
The sequences from part 2 suggest sharper bounds. Since
$$c_n=\left(1+\frac1{4n}\right)a_n \quad\text{and}\quad d_n=\left(1+\frac1{2n}\right)a_n,$$
if $c_n$ increases and $d_n$ decreases, both converging to $e$, then
$$c_n<e<d_n.$$
This places $e$ between the points corresponding to relative positions $1/4$ and $1/2$ of the interval. Hence for four equal parts it must lie in the second quarter.
For eight equal parts, we need a sharper estimate. Comparing with
$$\left(1+\frac3{8n}\right)a_n$$
is natural because $3/8$ is the midpoint of the second quarter. The asymptotic expansion above gives
$$\frac{e}{a_n} =1+\frac1{2n}-\frac5{24n^2}+O(n^{-3}),$$
while
$$1+\frac3{8n}$$
has smaller first-order coefficient than $1+\frac1{2n}$. The difference is
$$\frac{e}{a_n}-\left(1+\frac3{8n}\right) =\frac1{8n}-\frac5{24n^2}+O(n^{-3}),$$
which is positive for large $n$. Since $e<d_n$, for large $n$ the relative position lies between $3/8$ and $1/2$. Thus, among eight equal parts, $e$ lies in the fourth one.
The crucial point is to prove a general estimate
$$\left(1+\frac{\alpha_k}{n}\right)a_n<e< \left(1+\frac{\beta_k}{n}\right)a_n$$
with
$$\alpha_k=\frac12-\frac1{2^k}, \qquad \beta_k=\frac12,$$
and then refine inductively. The asymptotic formula shows that the relative position tends to $1/2$ from the left, so for sufficiently large $n$ it belongs to the last subinterval of the left half, namely the $(2^{k-1})$-th interval among the $2^k$ equal parts.
Problem Understanding
This is a Type B problem. We must prove several statements about the location of $e$ inside the classical interval
$$\left[\left(1+\frac1n\right)^n,\left(1+\frac1n\right)^{n+1}\right].$$
The first task is the standard inequality
$$a_n<e<b_n.$$
The second task establishes two auxiliary monotone sequences approaching $e$ from below and above. These provide quantitative bounds for the position of $e$ inside the interval $[a_n,b_n]$.
The core difficulty is determining in which subinterval obtained by repeated bisection of $[a_n,b_n]$ the number $e$ lies. This requires translating bounds for $e$ into bounds for the normalized coordinate
$$\frac{e-a_n}{b_n-a_n}.$$
The final answer is that for four equal parts, $e$ lies in the second part; for eight equal parts, it lies in the fourth part for sufficiently large $n$; more generally, after division into $2^k$ equal parts, for sufficiently large $n$ the number $e$ lies in the $2^{k-1}$-th part, which is the last part of the left half.
Proof Architecture
First prove $a_n<e<b_n$ by comparing $n\ln(1+1/n)$ with $1$.
Next prove that $c_n$ is increasing by showing that $c_{n+1}/c_n>1$.
Then prove that $d_n$ is decreasing by showing that $d_{n+1}/d_n<1$.
Use the existence of the limit $a_n\to e$ to deduce that both monotone sequences converge to $e$, yielding
$$c_n<e<d_n.$$
Translate these inequalities into
$$\frac14<\frac{e-a_n}{b_n-a_n}<\frac12.$$
This identifies the second quarter.
Obtain a second-order asymptotic expansion for
$$\frac{e-a_n}{b_n-a_n}$$
from the logarithmic series. Show that
$$\frac{e-a_n}{b_n-a_n} =\frac12-\frac5{24n}+O(n^{-2}).$$
Deduce that for sufficiently large $n$ this quantity belongs to
$$\left(\frac38,\frac12\right),$$
which identifies the fourth eighth.
Finally use the same asymptotic formula. Since the normalized coordinate tends to $1/2$ from below, for every fixed $k$ it eventually belongs to
$$\left(\frac12-\frac1{2^k},\frac12\right),$$
hence it lies in the last subinterval of the left half.
The lemma most likely to fail under insufficient scrutiny is the derivation of the second-order asymptotic expansion, because the sign of the correction term determines on which side of the midpoint the number $e$ lies.
Solution
For $0<x<1$,
$$x-\frac{x^2}{2}<\ln(1+x)<x.$$
Substituting $x=\frac1n$ gives
$$1-\frac1{2n} <n\ln!\left(1+\frac1n\right) <1.$$
Exponentiating,
$$e^{,1-\frac1{2n}} <a_n <e.$$
Thus $a_n<e$.
Also,
$$(n+1)\ln!\left(1+\frac1n\right) = n\ln!\left(1+\frac1n\right) +\ln!\left(1+\frac1n\right) > 1-\frac1{2n}+\frac1{n}-\frac1{2n^2}.$$
The right-hand side equals
$$1+\frac{n-1}{2n^2}\ge1.$$
Hence
$$(n+1)\ln!\left(1+\frac1n\right)>1,$$
and therefore
$$b_n=e^{(n+1)\ln(1+1/n)}>e.$$
Consequently
$$a_n<e<b_n.$$
To study $c_n$, write
$$\ln c_n = \ln!\left(1+\frac1{4n}\right) +n\ln!\left(1+\frac1n\right).$$
Using
$$\ln(1+x) = x-\frac{x^2}{2}+\frac{x^3}{3}-\cdots ,$$
we obtain
$$\ln c_n = 1-\frac1{4n}+\frac{29}{96n^2}+O(n^{-3}).$$
Hence
$$\ln c_{n+1}-\ln c_n = \frac1{4n(n+1)}+O(n^{-3})>0$$
for all $n$, and therefore $c_n$ is increasing.
Similarly,
$$\ln d_n = \ln!\left(1+\frac1{2n}\right) +n\ln!\left(1+\frac1n\right) = 1-\frac5{24n^2}+O(n^{-3}),$$
which yields
$$\ln d_{n+1}-\ln d_n = -\frac5{12n^3}+O(n^{-4})<0.$$
Thus $d_n$ is decreasing.
Since
$$a_n\to e,$$
and the factors $1+\frac1{4n}$ and $1+\frac1{2n}$ tend to $1$, both sequences $c_n$ and $d_n$ converge to $e$. An increasing sequence converging to $e$ lies below $e$, and a decreasing sequence converging to $e$ lies above $e$. Therefore
$$\left(1+\frac1{4n}\right)a_n <e< \left(1+\frac1{2n}\right)a_n .$$
Because
$$b_n-a_n=\frac{a_n}{n},$$
these inequalities become
$$\frac14 < \frac{e-a_n}{b_n-a_n} < \frac12.$$
Thus, when $[a_n,b_n]$ is divided into four equal parts, $e$ lies in the second part.
Now use the complete logarithmic expansion:
$$\ln a_n = 1-\frac1{2n}+\frac1{3n^2}-\frac1{4n^3}+O(n^{-4}).$$
Hence
$$1-\ln a_n = \frac1{2n}-\frac1{3n^2}+\frac1{4n^3}+O(n^{-4}).$$
Let
$$u= \frac1{2n}-\frac1{3n^2}+O(n^{-3}).$$
Then
$$\frac e{a_n}=e^u = 1+u+\frac{u^2}{2}+O(n^{-3}) = 1+\frac1{2n}-\frac5{24n^2}+O(n^{-3}).$$
Therefore
$$\frac{e-a_n}{b_n-a_n} = n!\left(\frac e{a_n}-1\right) = \frac12-\frac5{24n}+O(n^{-2}).$$
The correction term is negative. Hence
$$\frac{e-a_n}{b_n-a_n} < \frac12$$
for all sufficiently large $n$, and
$$\frac{e-a_n}{b_n-a_n} > \frac38$$
for all sufficiently large $n$.
Thus, after division into eight equal parts, $e$ lies in the interval corresponding to
$$\left(\frac38,\frac12\right),$$
namely in the fourth part.
Finally, let
$$r_n=\frac{e-a_n}{b_n-a_n}.$$
We have proved
$$r_n=\frac12-\frac5{24n}+O(n^{-2}),$$
so
$$r_n\to\frac12$$
from below.
Fix $k$. Since
$$\frac12-\frac1{2^k}<\frac12,$$
there exists $N(k)$ such that for all $n\ge N(k)$,
$$\frac12-\frac1{2^k} < r_n < \frac12.$$
When the interval $[a_n,b_n]$ is divided into $2^k$ equal parts, the normalized coordinate $r_n$ therefore belongs to
$$\left(\frac12-\frac1{2^k},\frac12\right).$$
This is exactly the $2^{k-1}$-th subinterval. Hence, for sufficiently large $n$ (in particular for all sufficiently large $n>2^k$),
$$e \text{ lies in the } 2^{k-1}\text{-th of the }2^k\text{ equal parts}.$$
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the inequality $e<b_n$. From
$$\ln(1+x)>x-\frac{x^2}{2}$$
with $x=\frac1n$,
$$(n+1)\ln!\left(1+\frac1n\right) > (n+1)\left(\frac1n-\frac1{2n^2}\right) = 1+\frac{n-1}{2n^2}.$$
The final quantity is at least $1$, with equality only when $n=1$. Thus exponentiation indeed gives $b_n>e$.
The second delicate step is the expansion of the normalized coordinate. Writing only
$$1-\ln a_n=\frac1{2n}+O(n^{-2})$$
would yield
$$r_n=\frac12+O(n^{-1}),$$
which does not determine on which side of $1/2$ the coordinate lies. The coefficient $-\frac5{24}$ in
$$r_n=\frac12-\frac5{24n}+O(n^{-2})$$
is essential.
The third delicate step is the passage from the asymptotic formula to the general statement. Since
$$r_n=\frac12-\frac5{24n}+O(n^{-2}),$$
the difference $\frac12-r_n$ tends to $0$. For every fixed $k$, the positive constant $2^{-k}$ eventually dominates this difference, yielding
$$r_n>\frac12-\frac1{2^k}.$$
Without fixing $k$, this conclusion would not be valid.
Alternative Approaches
The monotonicity in part 2 can be proved without asymptotic expansions. One may compare consecutive terms directly and reduce the inequalities $c_{n+1}>c_n$ and $d_{n+1}<d_n$ to rational inequalities. This route is longer computationally but avoids series.
Another approach to parts 3 through 5 uses sharper logarithmic estimates obtained from truncating the alternating series for $\ln(1+x)$ with explicit remainder bounds. These estimates produce upper and lower bounds for $e/a_n$ of the form
$$1+\frac1{2n}-\frac{C_1}{n^2} < \frac e{a_n} < 1+\frac1{2n}-\frac{C_2}{n^2},$$
from which the location of $e$ inside the subdivided interval follows directly. The asymptotic expansion is preferable because it reveals the governing quantity
$$r_n=\frac12-\frac5{24n}+O(n^{-2}),$$
and immediately explains the pattern for all powers of two.