Kvant Math Problem 1274
Denote
Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m15s
Source on kvant.digital
Problem
Prove that the difference between the numbers $$\dfrac{1}{2+\dfrac{1}{3+\dfrac{1}{\ldots+\dfrac{1}{n-1}}}} \qquad\text{и}\qquad \dfrac{1}{2+\dfrac{1}{3+\dfrac{1}{\ldots+\dfrac{1}{n-1+\dfrac{1}{n}}}}}$$ in absolute value does not exceed $\dfrac{1}{(n-1)!n!}$.
G. A. Halperin
Exploration
Denote
$$x_k=\frac1{k+\frac1{k+1+\frac1{\ddots+\frac1{n-1}}}}, \qquad y_k=\frac1{k+\frac1{k+1+\frac1{\ddots+\frac1{n-1+\frac1n}}}},$$
for $k=2,\dots,n-1$.
The required difference is $|x_2-y_2|$.
Computing the first few values suggests a simple pattern. For $k=n-1$,
$$x_{n-1}=\frac1{n-1},\qquad y_{n-1}=\frac1{n-1+\frac1n} =\frac n{n^2-n+1}.$$
Hence
$$x_{n-1}-y_{n-1} =\frac1{(n-1)(n^2-n+1)}.$$
The denominators occurring in continued fractions often satisfy a recurrence. Let
$$d_k=x_k-y_k.$$
Since
$$x_k=\frac1{k+x_{k+1}},\qquad y_k=\frac1{k+y_{k+1}},$$
we obtain
$$d_k =\frac{y_{k+1}-x_{k+1}} {(k+x_{k+1})(k+y_{k+1})} = -\frac{d_{k+1}} {(k+x_{k+1})(k+y_{k+1})}.$$
Thus
$$|d_k| = \frac{|d_{k+1}|} {(k+x_{k+1})(k+y_{k+1})}.$$
Since all continued fractions are positive, and $x_{k+1},y_{k+1}>0$,
$$(k+x_{k+1})(k+y_{k+1})>k^2.$$
Therefore
$$|d_k|<\frac{|d_{k+1}|}{k^2}.$$
Iterating gives
$$|d_2| < \frac{|d_{n-1}|}{(2\cdot3\cdots(n-2))^2}.$$
Substituting the exact value of $|d_{n-1}|$ produces
$$|d_2| < \frac1{((n-2)!)^2,(n-1)(n^2-n+1)}.$$
The remaining task is a purely algebraic comparison with $1/((n-1)!n!)$.
The delicate point is verifying that the final denominator is indeed at least $(n-1)!n!$.
Problem Understanding
We are given two finite continued fractions. The first ends with $n-1$, while the second has one additional layer and ends with $n-1+\frac1n$.
We must prove that the absolute value of their difference does not exceed
$$\frac1{(n-1)!n!}.$$
This is a Type B problem. The statement to be proved is already specified.
The core difficulty is controlling how a perturbation at the deepest level propagates through the continued fraction. The natural approach is to compare the two continued fractions recursively and estimate the attenuation at each step.
Proof Architecture
Let $x_k$ and $y_k$ be the tails of the two continued fractions beginning at level $k$.
Lemma 1. For $k=2,\dots,n-2$,
$$|x_k-y_k| = \frac{|x_{k+1}-y_{k+1}|} {(k+x_{k+1})(k+y_{k+1})}.$$
This follows from the identity $\frac1a-\frac1b=\frac{b-a}{ab}$.
Lemma 2. For $k=2,\dots,n-2$,
$$|x_k-y_k|<\frac{|x_{k+1}-y_{k+1}|}{k^2}.$$
This follows because $x_{k+1},y_{k+1}>0$.
Lemma 3. The deepest difference satisfies
$$|x_{n-1}-y_{n-1}| = \frac1{(n-1)(n^2-n+1)}.$$
This is obtained by direct computation.
Lemma 4.
$$((n-2)!)^2 (n-1)(n^2-n+1)\ge (n-1)!n!.$$
After cancellation this reduces to $n^2-n+1\ge n(n-1)$.
The most delicate step is the recursive estimate in Lemma 2, because it is the mechanism that propagates the perturbation through all levels.
Solution
For $k=2,\dots,n-1$ define
$$x_k=\frac1{k+\frac1{k+1+\frac1{\ddots+\frac1{n-1}}}},$$
and
$$y_k=\frac1{k+\frac1{k+1+\frac1{\ddots+\frac1{n-1+\frac1n}}}}.$$
The numbers appearing in the statement are $x_2$ and $y_2$.
For $k=2,\dots,n-2$ we have
$$x_k=\frac1{k+x_{k+1}}, \qquad y_k=\frac1{k+y_{k+1}}.$$
Hence
$$\begin{aligned} x_k-y_k &= \frac1{k+x_{k+1}} -\frac1{k+y_{k+1}} \ &= \frac{y_{k+1}-x_{k+1}} {(k+x_{k+1})(k+y_{k+1})}. \end{aligned}$$
Taking absolute values,
$$|x_k-y_k| = \frac{|x_{k+1}-y_{k+1}|} {(k+x_{k+1})(k+y_{k+1})}.$$
All numbers $x_j$ and $y_j$ are positive. Consequently,
$$(k+x_{k+1})(k+y_{k+1})>k^2,$$
and therefore
$$|x_k-y_k| < \frac{|x_{k+1}-y_{k+1}|}{k^2}.$$
Applying this inequality successively for
$$k=2,3,\dots,n-2,$$
we obtain
$$|x_2-y_2| < \frac{|x_{n-1}-y_{n-1}|} {(2\cdot3\cdots(n-2))^2} = \frac{|x_{n-1}-y_{n-1}|}{((n-2)!)^2}.$$
Now
$$x_{n-1}=\frac1{n-1}, \qquad y_{n-1}=\frac1{n-1+\frac1n} =\frac n{n^2-n+1}.$$
Thus
$$\begin{aligned} |x_{n-1}-y_{n-1}| &= \frac1{n-1} -\frac n{n^2-n+1} \ &= \frac{n^2-n+1-n(n-1)} {(n-1)(n^2-n+1)} \ &= \frac1{(n-1)(n^2-n+1)}. \end{aligned}$$
Substituting,
$$|x_2-y_2| < \frac1{((n-2)!)^2 (n-1)(n^2-n+1)}.$$
It remains to compare denominators. Since
$$n^2-n+1\ge n(n-1),$$
we have
$$\begin{aligned} ((n-2)!)^2 (n-1)(n^2-n+1) &\ge ((n-2)!)^2 (n-1),n(n-1) \ &= (n-1)! , n!. \end{aligned}$$
Therefore
$$|x_2-y_2| \le \frac1{(n-1)!n!}.$$
This completes the proof.
∎
Verification of Key Steps
The recursive identity must be checked exactly. Starting from
$$x_k=\frac1{k+x_{k+1}}, \qquad y_k=\frac1{k+y_{k+1}},$$
one gets
$$x_k-y_k = \frac{(k+y_{k+1})-(k+x_{k+1})} {(k+x_{k+1})(k+y_{k+1})} = \frac{y_{k+1}-x_{k+1}} {(k+x_{k+1})(k+y_{k+1})}.$$
A sign mistake here would propagate through the whole argument. Taking absolute values removes the sign and yields the exact formula used later.
The estimate
$$(k+x_{k+1})(k+y_{k+1})>k^2$$
depends only on positivity. Since every denominator in the continued fractions is positive, each $x_j$ and $y_j$ is positive. Replacing the denominator by $k^2$ makes the fraction larger, which gives the correct inequality direction
$$|x_k-y_k| < \frac{|x_{k+1}-y_{k+1}|}{k^2}.$$
The final comparison reduces to
$$n^2-n+1\ge n(n-1).$$
The two sides differ by
$$(n^2-n+1)-n(n-1)=1.$$
Hence the denominator obtained from the recursive estimate exceeds $(n-1)!n!$ by a positive factor, exactly what is needed.
Alternative Approaches
A different method is to represent each finite continued fraction as a ratio of continuants. Let $P_k/Q_k$ be the convergents associated with the tail beginning at $k$. The difference between the two continued fractions can then be expressed through the determinant identity for neighboring convergents. The perturbation introduced by replacing $n-1$ with $n-1+\frac1n$ appears only in the last continuant, and the determinant formula yields an explicit expression whose denominator contains products of the continuant denominators.
That approach is more algebraic and uses standard continued-fraction machinery. The recursive comparison above is preferable because it requires only the elementary identity for the difference of reciprocals and immediately reveals that each level reduces the error by at least a factor $k^2$.