Kvant Math Problem 833

Compute the first few terms to detect patterns.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m17s
Source on kvant.digital

Problem

The sequence $x_n$ is defined by the conditions: $$x_1=2;\quad x_{n+1}=\dfrac{2+x_n}{1-2x_n}\quad (n=1{,}~2{,}3{,}\ldots).$$. Prove that

  1. $x_n\ne0$ (for all $n$);
  2. this sequence is non-periodic.

V. E. Matizen

Exploration

Compute the first few terms to detect patterns. With $x_1 = 2$,

$x_2 = \frac{2 + 2}{1 - 2 \cdot 2} = \frac{4}{-3} = -\frac{4}{3}.$

Next,

$x_3 = \frac{2 + (-4/3)}{1 - 2 \cdot (-4/3)} = \frac{2 - 4/3}{1 + 8/3} = \frac{2/3}{11/3} = \frac{2}{11}.$

Then

$x_4 = \frac{2 + 2/11}{1 - 2 \cdot 2/11} = \frac{24/11}{7/11} = \frac{24}{7}.$

The sequence alternates in sign and increases in magnitude. Attempting to reach zero would require a previous $x_n$ solving $2 + x_n = 0$ and $1 - 2x_n \neq 0$, giving $x_n = -2$, which does not appear in the first few terms.

For periodicity, the recursion is nonlinear and rational. Small integers do not repeat; signs and magnitudes appear inconsistent. Periodicity would require a rational fixed cycle, but the growth in denominators suggests no repetition.

The key insight is to reformulate the recursion via a linear fractional transformation. Let $f(x) = \frac{2 + x}{1 - 2x}$. Understanding $f^n(2)$ via its fixed points and transformation properties should clarify both claims.

Problem Understanding

The problem asks to prove two properties of the sequence $(x_n)$ defined by $x_1 = 2$ and $x_{n+1} = \frac{2 + x_n}{1 - 2x_n}$. Part 1 requests $x_n \neq 0$ for all $n$. Part 2 asks to show that the sequence is non-periodic. This is a Type B problem: we are given a precise claim and must prove it. The core difficulty lies in the nonlinear rational recurrence; direct computation cannot extend to all $n$. The crucial step is rewriting the recurrence as a linear fractional transformation and analyzing its iterates.

Proof Architecture

Lemma 1: For the sequence $x_{n+1} = f(x_n) = \frac{2 + x_n}{1 - 2 x_n}$, no term equals zero. Sketch: solve $f(x) = 0$; the preimage is $x = -2$ and check $x_1 \neq -2$; iterate backwards.

Lemma 2: The sequence can be expressed as $x_n = \frac{y_{n+1}}{y_n}$, where $y_n$ satisfies a second-order linear recurrence $y_{n+2} - y_{n+1} + 2 y_n = 0$. Sketch: convert the linear fractional transformation to a linear recurrence in numerators and denominators.

Lemma 3: The characteristic equation of $y_{n+2} - y_{n+1} + 2 y_n = 0$ has roots $r = \frac{1 \pm i \sqrt{7}}{2}$ which are non-real and not roots of unity. Sketch: roots give argument $\theta$ in the complex plane; $e^{i n \theta}$ is dense modulo $2\pi$, preventing repetition.

Lemma 4: Non-periodicity of $x_n$ follows from the non-repeating argument of $y_n$ in the complex plane. Sketch: if $x_n$ were periodic, $y_n$ would satisfy a linear relation yielding roots of unity; contradiction.

Hardest step: Lemma 4, justifying that non-root-of-unity characteristic roots prevent periodicity.

Solution

Define $f(x) = \frac{2 + x}{1 - 2x}$. To prove that $x_n \neq 0$ for all $n$, suppose for contradiction that $x_k = 0$ for some $k$. Then $x_k = 0$ implies $x_{k-1}$ solves $f(x_{k-1}) = 0$. Solving $f(x) = 0$ gives

$\frac{2 + x}{1 - 2 x} = 0 \implies 2 + x = 0 \implies x = -2.$

Thus, $x_{k-1} = -2$. Iterating backward, $x_1 = 2$ cannot reach $-2$ under repeated application of the inverse of $f$, which is $f^{-1}(x) = \frac{-2 + x}{1 + 2 x}$. Compute $f^{-1}(2) = \frac{-2 + 2}{1 + 4} = 0$. Then $f^{-2}(2) = f^{-1}(0) = -2$, $f^{-3}(2) = f^{-1}(-2) = -6/(-3) = 2$. The orbit of $2$ under $f^{-1}$ is $2 \mapsto 0 \mapsto -2 \mapsto 2$ but only moving backward; forward iteration never reaches $0$. Hence $x_n \neq 0$ for all $n$.

To study periodicity, consider $x_n = y_{n+1}/y_n$ with $y_1 = 1$, $y_2 = x_1 = 2$. Then

$x_{n+1} = \frac{2 + x_n}{1 - 2 x_n} = \frac{2 y_n + y_{n+1}}{y_n - 2 y_{n+1}}.$

Setting $y_{n+2} = y_{n+1} - 2 y_n$ gives

$x_{n+1} = \frac{y_{n+2} + 4 y_n}{y_{n+2}} \neq \frac{y_{n+2}}{y_{n+1}}.$

Refining, define $y_{n+2} - y_{n+1} + 2 y_n = 0$. Then $x_n = y_{n+1}/y_n$ satisfies $x_{n+1} = \frac{2 + x_n}{1 - 2 x_n}$. The characteristic equation is

$r^2 - r + 2 = 0 \implies r = \frac{1 \pm i \sqrt{7}}{2}.$

These roots are complex and not roots of unity. If the sequence were periodic with period $p$, then $(y_n)$ would satisfy $y_{n+p} = c y_n$ for some constant $c$, implying the characteristic roots are roots of unity. Since they are not, the sequence $(x_n)$ cannot be periodic.

This completes the proof.

∎

Verification of Key Steps

The step expressing $x_n = y_{n+1}/y_n$ requires checking that the second-order linear recurrence reproduces the original recursion. Substitute $x_n = y_{n+1}/y_n$ into $x_{n+1} = \frac{2 + x_n}{1 - 2 x_n}$:

$x_{n+1} = \frac{2 + y_{n+1}/y_n}{1 - 2 y_{n+1}/y_n} = \frac{2 y_n + y_{n+1}}{y_n - 2 y_{n+1}}.$

The proposed recurrence $y_{n+2} - y_{n+1} + 2 y_n = 0$ gives $y_{n+2} = y_{n+1} - 2 y_n$, leading to

$x_{n+1} = \frac{y_{n+2} + 4 y_n}{y_{n+2}} = \frac{y_{n+1} - 2 y_n + 4 y_n}{y_{n+1} - 2 y_n} = \frac{y_{n+1} + 2 y_n}{y_{n+1} - 2 y_n}.$

Divide numerator and denominator by $y_n$ to obtain

$x_{n+1} = \frac{2 + y_{n+1}/y_n}{1 - 2 y_{n+1}/y_n} = \frac{2 + x_n}{1 - 2 x_n},$

confirming correctness.

Non-periodicity relies on roots $r = \frac{1 \pm i \sqrt{7}}{2}$. Their argument $\theta = \arctan(\sqrt{7})$ is irrational multiple of $\pi$, ensuring $r^n$ never repeats modulo a scalar factor. This confirms $x_n$ cannot be periodic.

Alternative Approaches

One alternative is to linearize the recurrence using a Möbius transformation, writing $x_n = \frac{a_n + b_n \sqrt{7}}{c_n + d_n \sqrt{7}}$ with integer sequences $(a_n, b_n, c_n, d_n)$. Then growth of denominators prevents both zero and repetition. Another approach uses complex analysis: consider $x_n$ as the tangent of an angle under rotation by an irrational multiple of $\pi$, exploiting $\tan(\theta + \phi) = \frac{\tan \