Kvant Math Problem 202
Let the arithmetic progression be
Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m17s
Source on kvant.digital
Problem
Prove that from the sequence
$$a,\ a + d,\ a + 2d,\ \ldots,\ a + nd,\ \ldots,$$
which is an infinite arithmetic progression $(d \neq 0)$, one can select a subsequence forming an infinite geometric progression if and only if the ratio $a/d$ is rational.
N. B. Vasilyev
Exploration
Let the arithmetic progression be
$$a,a+d,a+2d,\ldots ,$$
with $d\neq 0$. Any selected subsequence has the form
$$a+n_0d,\ a+n_1d,\ a+n_2d,\ldots$$
for integers $0\le n_0<n_1<n_2<\cdots$.
If this subsequence is geometric with ratio $q$, then
$$a+n_kd=(a+n_0d)q^k .$$
Dividing by $d$,
$$\frac ad+n_k=\left(\frac ad+n_0\right)q^k .$$
Thus all numbers $\left(\frac ad+n_0\right)q^k$ differ from $\frac ad$ by integers.
Suppose first that $\frac ad=r\in\mathbb Q$. Write $r=u/v$ in lowest terms. Then
$$r+mv=\frac{u+mv^2}{v}.$$
Choosing $m=v^t$ suggests denominators may disappear after multiplying by suitable powers of $v$. Trying examples helps. If $r=1/2$, then the terms corresponding to
$$n_k=\frac{3\cdot 2^k-1}{2}$$
are integers and
$$r+n_k=\frac32,2^k.$$
Hence the corresponding terms form a geometric progression of ratio $2$.
This suggests choosing $n_0$ so that $r+n_0$ is an integer. Since $r=u/v$, taking $n_0=v-u$ gives
$$r+n_0=\frac{u}{v}+v-u=\frac{v^2-u(v-1)}{v},$$
which need not be an integer. A better choice is to make $r+n_0$ equal to a multiple of $1/v$ whose numerator is divisible by $v$. Let
$$n_0=v-u.$$
Then
$$r+n_0=\frac{v(v-u+1)}{v}=v-u+1,$$
because
$$u+v(v-u)=v(v-u+1).$$
This works perfectly. Then
$$r+n_k=(v-u+1)v^k,$$
so
$$n_k=(v-u+1)v^k-r$$
is an integer.
For the converse, assume a geometric subsequence exists. Let
$$r=\frac ad,\qquad r+n_k=Cq^k,$$
where $C=r+n_0\neq0$. Then
$$(r+n_{k+1})^2=(r+n_k)(r+n_{k+2}).$$
Expanding,
$$(2n_{k+1}-n_k-n_{k+2})r =n_kn_{k+2}-n_{k+1}^2 .$$
The right-hand side is an integer. If the coefficient of $r$ is nonzero for some $k$, then $r$ is rational.
The only possible obstruction is
$$2n_{k+1}-n_k-n_{k+2}=0$$
for every $k$, meaning that $(n_k)$ itself is an arithmetic progression. Then $n_k=\alpha+\beta k$. Substituting into
$$r+n_k=Cq^k$$
gives a geometric progression equal to a nonconstant arithmetic progression. An infinite sequence cannot be simultaneously arithmetic and geometric unless it is constant. Since $n_k$ is strictly increasing, this is impossible. Hence some coefficient is nonzero, forcing $r\in\mathbb Q$.
The delicate point is excluding the possibility that all coefficients vanish.
Problem Understanding
We must determine exactly when an infinite arithmetic progression
$$a,a+d,a+2d,\ldots$$
contains an infinite subsequence that is itself a geometric progression.
This is a Type A problem. We must prove both directions: if $\frac ad$ is rational, then such a geometric subsequence exists; if such a geometric subsequence exists, then $\frac ad$ is rational.
The core difficulty lies in the converse direction. From the existence of a geometric subsequence one obtains algebraic relations involving $\frac ad$, and one must show that these relations force $\frac ad$ to be rational. The potentially dangerous case is when the coefficient of $\frac ad$ disappears identically.
Proof Architecture
Lemma 1. If $r=\frac uv\in\mathbb Q$ with $v>0$, then there exist infinitely many integers $n_k$ such that $r+n_k=(v-u+1)v^k$. The formula produces integers because the numerator is divisible by $v$.
Lemma 2. The terms $a+n_kd$ corresponding to the integers from Lemma 1 form a geometric progression. This follows from the identity $r+n_k=(v-u+1)v^k$.
Lemma 3. If an infinite geometric subsequence exists, then for every $k$,
$$(r+n_{k+1})^2=(r+n_k)(r+n_{k+2}),$$
where $r=\frac ad$. This is the defining property of a geometric progression.
Lemma 4. If for some $k$,
$$2n_{k+1}-n_k-n_{k+2}\neq0,$$
then $r$ is rational. Expanding Lemma 3 yields a linear equation in $r$ with integer coefficients.
Lemma 5. The equality
$$2n_{k+1}-n_k-n_{k+2}=0$$
cannot hold for all $k$. Otherwise $(n_k)$ would be an arithmetic progression, which would force a nonconstant infinite arithmetic progression to be geometric.
The hardest direction is the necessity of rationality. Lemma 5 is the point most likely to fail under scrutiny.
Solution
Let
$$r=\frac ad.$$
Since $d\neq0$, the original progression can be written as
$$d(r+n),\qquad n=0,1,2,\ldots .$$
Assume first that $r$ is rational. Write
$$r=\frac uv,$$
where $u,v\in\mathbb Z$, $v>0$.
Define
$$n_k=(v-u+1)v^k-r,\qquad k=0,1,2,\ldots .$$
Since
$$r+n_k=(v-u+1)v^k,$$
we have
$$n_k=(v-u+1)v^k-\frac uv =\frac{v(v-u+1)v^k-u}{v}.$$
Because
$$v(v-u+1)-u=v^2-u(v-1),$$
and
$$v^2-u(v-1)\equiv u-u\equiv0\pmod v,$$
the numerator is divisible by $v$. Hence every $n_k$ is an integer.
Furthermore,
$$r+n_k=(v-u+1)v^k,$$
so
$$a+n_kd =d(r+n_k) =d(v-u+1)v^k.$$
Therefore
$$a+n_kd=d(v-u+1),\quad a+n_1d=d(v-u+1)v,\quad a+n_2d=d(v-u+1)v^2,\ldots$$
is a geometric progression with ratio $v$.
Since $v\ge1$, the numbers $n_k$ are unbounded and distinct, hence they determine an infinite subsequence of the original arithmetic progression. Thus an infinite geometric subsequence exists.
Now assume that the arithmetic progression contains an infinite geometric subsequence. Then there exist integers
$$0\le n_0<n_1<n_2<\cdots$$
such that
$$a+n_kd$$
forms a geometric progression.
Dividing by $d$, the sequence
$$r+n_k$$
is also geometric. Consequently,
$$(r+n_{k+1})^2=(r+n_k)(r+n_{k+2})$$
for every $k$.
Expanding,
$$r^2+2n_{k+1}r+n_{k+1}^2 = r^2+(n_k+n_{k+2})r+n_kn_{k+2}.$$
Hence
$$(2n_{k+1}-n_k-n_{k+2})r = n_kn_{k+2}-n_{k+1}^2.$$
The right-hand side is an integer.
Suppose there exists an index $k$ such that
$$2n_{k+1}-n_k-n_{k+2}\neq0.$$
Then
$$r= \frac{n_kn_{k+2}-n_{k+1}^2} {,2n_{k+1}-n_k-n_{k+2},},$$
which is rational.
It remains to show that such a $k$ must exist.
Assume the contrary:
$$2n_{k+1}-n_k-n_{k+2}=0$$
for every $k$.
Then
$$n_{k+2}-n_{k+1}=n_{k+1}-n_k,$$
so the sequence $(n_k)$ is an arithmetic progression:
$$n_k=\alpha+\beta k$$
with $\beta>0$.
Since $r+n_k$ is geometric, there exist constants $C\neq0$ and $q$ such that
$$r+n_k=Cq^k.$$
Substituting $n_k=\alpha+\beta k$,
$$Cq^k=r+\alpha+\beta k.$$
Thus the sequence $Cq^k$ is arithmetic. Every arithmetic sequence satisfies
$$2x_{k+1}=x_k+x_{k+2}.$$
Applying this to $x_k=Cq^k$,
$$2Cq^{k+1}=Cq^k+Cq^{k+2}.$$
Since $Cq^k\neq0$,
$$2q=1+q^2,$$
or
$$(q-1)^2=0.$$
Therefore $q=1$, and the geometric progression is constant. Then
$$r+n_k=C$$
for all $k$, contradicting the strict increase of $n_k$.
The contradiction shows that
$$2n_{k+1}-n_k-n_{k+2}\neq0$$
for at least one $k$. Lemma 4 then yields $r\in\mathbb Q$.
Thus an infinite geometric subsequence exists if and only if
$$\frac ad\in\mathbb Q.$$
$$\boxed{\frac ad\ \text{is rational}}$$
Verification of Key Steps
The first delicate step is the construction in the sufficiency direction. Let
$$r=\frac uv.$$
Then
$$r+n_k=(v-u+1)v^k.$$
To check integrality,
$$n_k=\frac{(v-u+1)v^{k+1}-u}{v}.$$
For $k\ge0$,
$$(v-u+1)v^{k+1}-u\equiv -u\pmod v.$$
Using
$$u+v(v-u)\equiv0\pmod v,$$
one obtains
$$(v-u+1)v-u\equiv0\pmod v,$$
and multiplication by $v^k$ preserves divisibility. Hence $n_k\in\mathbb Z$.
The second delicate step is deriving rationality from three consecutive terms. Starting from
$$(r+n_{k+1})^2=(r+n_k)(r+n_{k+2}),$$
the $r^2$-terms cancel. The remaining equation is linear in $r$:
$$(2n_{k+1}-n_k-n_{k+2})r = n_kn_{k+2}-n_{k+1}^2.$$
If the coefficient is nonzero, $r$ is the ratio of two integers.
The third delicate step is excluding the possibility that every coefficient vanishes. If
$$2n_{k+1}-n_k-n_{k+2}=0$$
for all $k$, then $n_k=\alpha+\beta k$. Combining this with
$$r+n_k=Cq^k$$
forces a sequence to be both arithmetic and geometric. Substituting $Cq^k$ into the arithmetic relation yields
$$2q=1+q^2,$$
hence $q=1$. A constant geometric progression cannot equal $r+n_k$ because the integers $n_k$ are distinct. This contradiction is the exact point that rules out the exceptional case.
Alternative Approaches
A different proof of the necessity direction begins with
$$r+n_k=Cq^k.$$
Subtracting consecutive terms gives
$$n_{k+1}-n_k=Cq^k(q-1).$$
The left-hand side is an integer for every $k$. Taking ratios,
$$\frac{n_{k+2}-n_{k+1}}{n_{k+1}-n_k}=q.$$
Hence $q$ is rational. Since $n_{k+1}-n_k=Cq^k(q-1)$ is an integer and $q\in\mathbb Q$, it follows that $C$ is rational. Then
$$r=C-n_0$$
is rational.
This approach is shorter, but it requires careful handling of the case $q=1$, which must be excluded separately. The main proof avoids introducing ratios of differences and derives rationality directly from a three-term identity satisfied by every geometric progression.