Kvant Math Problem 1486

Verified: no
Verdicts: FAIL + FAIL
Solve time: 32m39s
Source on kvant.digital

Problem

Is it possible to choose from the numbers 1, $\dfrac12$, $\dfrac13$, $\ldots$ a sequence:

of 5 terms;
of $n$ terms;
of infinitely many terms,

in which each number is equal to the difference of the two preceding ones?

S. I. Tokarev

Exploration

Consider sequences $(a_1, a_2, a_3, \dots)$ satisfying the recurrence $a_k = a_{k-1} - a_{k-2}$ for $k \ge 3$, with terms chosen from the set $1, \frac12, \frac13, \dots$. Examining short sequences illustrates the behavior of the recurrence. Choosing $a_1 = 1$ and $a_2 = \frac12$ yields $a_3 = \frac12 - 1 = -\frac12$, which is negative and outside the allowed set. Similarly, $a_1 = 1$ and $a_2 = \frac13$ gives $a_3 = -\frac23$, also invalid. If the first term exceeds the second, negative terms appear immediately. Conversely, if $a_2 > a_1$, the third term is positive, and for certain choices $a_3$ belongs to the set of positive reciprocals of integers, as in $a_1 = 1/3$, $a_2 = 1/2$, yielding $a_3 = 1/6$.

The recurrence can be rewritten as $a_{k+1} + a_{k-1} = a_k$, producing a linear recurrence with characteristic equation $r^2 - r + 1 = 0$. The roots $r = \frac{1 \pm i \sqrt{3}}{2}$ are complex with modulus 1, implying the sequence exhibits oscillatory behavior in sign and magnitude if extended beyond a few terms with positive initial values. These observations suggest that sequences of length 5 or more inevitably produce negative terms, while sequences of length 3 may exist under suitable initial choices.

Problem Understanding

The task is to determine whether sequences can be formed from $1, \frac12, \frac13, \dots$ that satisfy $a_k = a_{k-1} - a_{k-2}$ for all $k \ge 3$. Sequences of length 5, length $n \ge 5$, and infinitely long sequences are considered. The main difficulty is that the recurrence produces alternating behavior, and negative terms appear quickly, conflicting with the requirement that all terms be positive reciprocals of integers. Sequences of length 3 can exist if the second term exceeds the first in a manner that ensures the third term remains a positive reciprocal of an integer. Sequences of length 2 are trivially allowed.

Proof Architecture

Lemma 1 establishes that any sequence $(a_1, a_2, a_3, \dots)$ of length at least 5 satisfying $a_k = a_{k-1} - a_{k-2}$ contains a negative term. Computing $a_3 = a_2 - a_1$ and $a_4 = a_3 - a_2 = -a_1$ shows that $a_4$ is negative for any positive $a_1$ from the allowed set.

Lemma 2 states that no sequence of length $n \ge 5$ drawn from positive reciprocals of integers satisfies the recurrence. This follows from Lemma 1, because the fourth term is necessarily negative, violating the positivity requirement.

Lemma 3 asserts that no infinite sequence of positive reciprocals satisfies the recurrence. The recurrence is deterministic, and the computation $a_4 = -a_1 < 0$ holds for any choice of positive initial terms $a_1, a_2$ from the set, preventing continuation beyond three terms. Any attempt to construct a longer sequence results in a negative term at the fourth position, which cannot belong to the allowed set, formally ruling out infinite sequences.

Sequences of length 3 exist when $a_2 > a_1$ and $a_3 = a_2 - a_1$ is a positive reciprocal of an integer. For example, $a_1 = 1/3$ and $a_2 = 1/2$ yield $a_3 = 1/6$, which satisfies the recurrence and belongs to the allowed set. Sequences of length 2 are trivially allowed by selecting any two numbers from the set.

Solution

Suppose a sequence $(a_1, a_2, \dots, a_5)$ is chosen from $1, \frac12, \frac13, \dots$ satisfying $a_k = a_{k-1} - a_{k-2}$ for $k \ge 3$. Then $a_3 = a_2 - a_1$ and $a_4 = a_3 - a_2 = (a_2 - a_1) - a_2 = -a_1$. Since $a_1$ is a positive number from the set, $a_4$ is negative, which is impossible. Therefore no sequence of length 5 exists.

This argument extends to sequences of length $n \ge 5$, because the fourth term is always $-a_1$, violating positivity. Consequently, sequences of length 5 or more cannot exist.

For infinitely long sequences, any initial choice $a_1, a_2$ from the positive reciprocals produces $a_3 = a_2 - a_1$ and $a_4 = -a_1 < 0$. Since $a_4$ is negative, the sequence cannot be continued within the set of allowed terms. Therefore, no infinite sequence exists.

Sequences of length 3 exist if $a_2 > a_1$ and $a_3 = a_2 - a_1$ belongs to the set of positive reciprocals. The example $a_1 = 1/3$, $a_2 = 1/2$ yields $a_3 = 1/6$, satisfying the recurrence and set membership. Sequences of length 2 are trivially allowed.

Hence sequences of length 5, sequences of length $n \ge 5$, or infinitely many terms cannot exist, while sequences of length 3 can exist under appropriate initial choices.

$\boxed{\text{No sequences of 5 terms, $n \ge 5$ terms, or infinitely many terms exist. Sequences of length 3 can exist.}}$

Verification of Key Steps

The computation $a_4 = a_3 - a_2 = (a_2 - a_1) - a_2 = -a_1$ is explicit. Any positive choice of $a_1$ guarantees $a_4 < 0$, confirming that sequences of length 5 or longer cannot remain within the positive reciprocals. This holds for any pair $(a_1, a_2)$ from the set, including cases where $a_2 < a_1$, $a_2 = a_1$, or $a_2 > a_1$. The case of sequences of length 3 is explicitly verified: $a_1 = 1/3$, $a_2 = 1/2$, $a_3 = 1/6$ satisfies the recurrence and belongs to the allowed set. This completes the rigorous justification for the impossibility of sequences longer than three terms.

Alternative Approaches

Analyzing the linear recurrence using characteristic roots provides a general insight. The characteristic equation $r^2 - r + 1 = 0$ has roots $r = \frac{1 \pm i \sqrt{3}}{2}$ on the unit circle in the complex plane. This implies oscillatory behavior in sign and magnitude for sequences extended from positive initial terms. Any attempt to extend beyond three terms produces a negative term at the fourth position, confirming the impossibility of sequences of length 5 or more and infinite sequences. This approach generalizes to all positive initial values, while the explicit computation $a_4 = -a_1$ provides a fully concrete argument suitable for elementary verification.