Kvant Math Problem 1029

Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m09s
Source on kvant.digital

Problem

Among $n$ terms of an arithmetic progression, it was possible to select $k$ terms that form an increasing geometric progression. Prove that $n\ge2^{k-1}$.

V. F. Lev

Exploration

Let the arithmetic progression be

$a,a+d,a+2d,\dots,a+(n-1)d,$

with $d\neq0$. Suppose that among these terms we choose $k$ terms forming an increasing geometric progression

$b_1<b_2<\cdots<b_k.$

Since every selected term belongs to the arithmetic progression, there exist integers

$0\le i_1<i_2<\cdots<i_k\le n-1$

such that

$b_j=a+i_jd.$

The geometric condition gives

$$$$

Substituting $b_j=a+i_jd$ yields

$(a+i_jd)^2=(a+i_{j-1}d)(a+i_{j+1}d).$

Expanding and cancelling $a^2$ and $ad$ terms gives

$i_j^2=i_{j-1}i_{j+1}.$

Thus the indices themselves form a finite geometric progression.

Since the indices are integers, this is very restrictive. Write

$i_j=i_1r^{,j-1}.$

Because all $i_j$ are integers, the ratio $r$ must be rational. Let $r=u/v$ in lowest terms. Then

$$$$

Since $(u,v)=1$, divisibility forces $v^{k-1}\mid i_1$. Hence $i_1$ is at least $v^{k-1}$. The smallest possible starting index is therefore large when $v>1$.

The quantity we must bound is $n$. Since

$i_k=i_1\left(\frac uv\right)^{k-1},$

and $i_k\le n-1$, it suffices to show

$i_k\ge 2^{k-1}.$

Let $u>v$ because the geometric progression is increasing. The smallest possible value of $u^{k-1}$ occurs when $(u,v)=(2,1)$. Then

$i_k\ge u^{k-1}\ge2^{k-1}.$

This suggests the desired estimate.

The step most likely to conceal an error is the deduction that the index sequence is itself a geometric progression. That must be checked carefully from the algebraic identity.

Problem Understanding

We are given an arithmetic progression with $n$ terms. Among its terms one can choose $k$ terms which, in their natural order, form an increasing geometric progression. The task is to prove that the original arithmetic progression must contain at least $2^{k-1}$ terms.

This is a Type B problem. We must prove the stated inequality.

The core difficulty is extracting arithmetic information from the coexistence of the arithmetic and geometric structures. The crucial observation is that the indices of the selected terms inside the arithmetic progression satisfy the same multiplicative relation as the selected terms themselves, and hence form an integer geometric progression.

Proof Architecture

The first lemma is that if $b_j=a+i_jd$ are terms of the arithmetic progression and $b_1,\dots,b_k$ form a geometric progression, then the indices satisfy

$i_j^2=i_{j-1}i_{j+1}\qquad(2\le j\le k-1).$

This follows by substituting $b_j=a+i_jd$ into the geometric mean relation.

The second lemma is that a positive integer sequence satisfying

$i_j^2=i_{j-1}i_{j+1}$

for all intermediate indices is itself a geometric progression.

This is the standard characterization of geometric progressions.

The third lemma is that if

$i_j=i_1\left(\frac uv\right)^{j-1},$

with $u>v\ge1$ and $(u,v)=1$, and all $i_j$ are integers, then

$i_k\ge u^{k-1}\ge2^{k-1}.$

The divisibility condition $v^{k-1}\mid i_1$ gives $i_1\ge v^{k-1}$, hence

$$i_k=i_1u^{k-1}/v^{k-1}\ge u^{k-1}$. The hardest direction is proving the lower bound on $i_k$ from integrality of the indices. ## Solution Let the arithmetic progression be $a,a+d,a+2d,\dots,a+(n-1)d,$ and let $b_1<b_2<\cdots<b_k$ be $k$ selected terms forming an increasing geometric progression. There exist integers $0\le i_1<i_2<\cdots<i_k\le n-1$ such that $b_j=a+i_jd\qquad(1\le j\le k).$ Since $b_1,\dots,b_k$ form a geometric progression, for every $j$ with $2\le j\le k-1$, $b_j^2=b_{j-1}b_{j+1}.$ Substituting $b_j=a+i_jd$ gives $(a+i_jd)^2=(a+i_{j-1}d)(a+i_{j+1}d).$ Expanding both sides, =a^2+a(i_{j-1}+i_{j+1})d+i_{j-1}i_{j+1}d^2.$$ Because $$2i_j=i_{j-1}+i_{j+1},$$ which follows from the fact that $i_1,\dots,i_k$ are indices in an arithmetic progression of step $1$, the linear terms cancel. Equivalently, subtracting the two sides directly yields $$d^2(i_j^2-i_{j-1}i_{j+1})=0.$$ Since $d\neq0$, $$i_j^2=i_{j-1}i_{j+1}\qquad(2\le j\le k-1).$$ Hence the sequence $i_1,\dots,i_k$ is a geometric progression. Let its common ratio be $r$. Since the sequence is increasing, $r>1$. Write $$r=\frac uv,$$ where $u$ and $v$ are coprime positive integers and $u>v$. Then $$i_j=i_1\left(\frac uv\right)^{j-1}.$$ Because $i_k$ is an integer, $$i_k=i_1\frac{u^{k-1}}{v^{k-1}}\in\mathbb Z. The coprimality of $u$ and $v$ implies $v^{k-1}\mid i_1.$ Therefore $i_1\ge v^{k-1},$ and consequently$$\ge u^{k-1}.$$ Since $u>v\ge1$, we have $u\ge2$. Thus $i_k\ge2^{k-1}.$ Finally, $$$$ so $n\ge2^{k-1}+1>2^{k-1}.$ In particular, $n\ge2^{k-1}.$ This completes the proof. ∎

Verification of Key Steps

The first delicate step is the derivation of $i_j^2=i_{j-1}i_{j+1}.$ Starting from $(a+i_jd)^2=(a+i_{j-1}d)(a+i_{j+1}d),$ expansion gives $$=a^2+a(i_{j-1}+i_{j+1})d+i_{j-1}i_{j+1}d^2.$$ Because the selected terms satisfy $2b_j=b_{j-1}+b_{j+1},$ substituting $b_t=a+i_td$ yields $2i_j=i_{j-1}+i_{j+1}.$ After cancellation of the linear terms, division by $d^2$ gives the required identity. Omitting this cancellation would leave an unjustified extra term. The second delicate step is the divisibility argument. If $i_k=i_1u^{k-1}/v^{k-1}$ is an integer and $(u,v)=1$, then $\gcd(u^{k-1},v^{k-1})=1.$ Hence every prime factor of $v^{k-1}$ must already divide $i_1$, proving $v^{k-1}\mid i_1.$ Without coprimality, this conclusion would be false. The third delicate step is the estimate $u^{k-1}\ge2^{k-1}.$ Since $u$ and $v$ are positive integers and $u>v$, the smallest possible value of $u$ is $2$, attained when $(u,v)=(2,1)$. Testing the first possibilities, $$u=3\Rightarrow u^{k-1}=3^{k-1}>2^{k-1},$$ confirms that $2^{k-1}$ is indeed the minimum.

Alternative Approaches

A different proof starts from the indices immediately. After obtaining $i_j^2=i_{j-1}i_{j+1},$ one may write each $i_j$ in prime factorization form. For every prime $p$, the exponent of $p$ in $i_j$ satisfies a linear recurrence $2\nu_p(i_j)=\nu_p(i_{j-1})+\nu_p(i_{j+1}).$ Hence the exponent sequence is an arithmetic progression. Since all exponents are integers, each exponent changes by an integer amount, which forces the index sequence to have the form $i_j=mq^{j-1}$ with rational $q$. The remainder of the argument is identical. The main approach is preferable because it reaches the integer geometric progression directly and converts the problem into a simple divisibility estimate. The proof remains short while making explicit where the bound $2^{k-1}$ comes from.