Let $(a_1,a_2,\dots)$ be a strictly increasing sequence of positive integers in arithmetic progression. Prove that there is an infinite sub-sequence of the given sequence whose terms are in a geometric progression.
Problem
Source: RMO Mumbai 2016, P6
Tags: arithmetic sequence, number theory, MONT
11.10.2016 10:32
Let the sequence be $ai+b$. Divide the whole sequence by the $gcd$ of $a,b$. Then there is a term congruent to 1 mod $a/gcd(a,b)$. consider the powers of that number. clearly, they are in that progression, whence we are done.
11.10.2016 11:03
Simply consider the subsequence ${a_1(1+d),a_1(1+d)^2,...}$. This completes the problem.
11.10.2016 14:02
Take the sequence as $a_n=a+nb$ and as we can pull the common factor of $a,b$ out, we may assume without loss of generality that $a$ and $b$ are coprime. Now, let $$n_k=\frac{(a+b)^{k\phi(b)+1}-a}{b}$$for any natural number $k$ and see that the sub-sequence $(a_{n_k})_{k \ge 1}$ is in a GP by Euler's Theorem. $\square$
11.10.2016 15:13
TheOneYouWant wrote: Simply consider the subsequence ${a_1(1+d),a_1(1+d)^2,...}$. This completes the problem. Yes, that's exactly what I did in exam.
24.11.2020 14:40
30.04.2021 14:53
26.05.2021 18:14
For any $AP(a,d)$ (first term is $a$ and common difference is $d$) , just take $r=1$ as the common ratio in Z/dZ All of $a , ar, ar^2, ......$ are $ \equiv a \mod(d)$ and hence in the AP Essentially, a[(md+1)^t] , m>0 works
16.05.2022 09:27
Let $m$ be the common difference so $a_1\equiv a_2\equiv\dots\pmod{m}$ Then, $a_i(km+1)\equiv a_i\equiv a_1$ is always in the sequence, so $a_1(km+1),a_1(km+1)^2,\dots$ works. $\square$
11.06.2023 00:40
Consider the sequence \[a_1(1 + d), a_1(1 + d)^2, \dots a_1(1 + d)^n,\]where each of the terms $(b_n) = a_1(1 + d)^n,$ is the $\frac{a_1((1+d)^n - 1)}{d}th$ term of the initial sequence $(a_n)$. $\blacksquare$
01.02.2024 07:17
Consider the sequence $b_n = a_1(1+d)^{n-1}$ for all natural $n$. Clearly this sequence is indeed a geometric progression. We now prove that any element of the sequence lies in $(a_1, a_2, ...)$. The proof is as follows: Observe from the binomial theorem that $(1+d)^n = 1 + d \cdot k$ for some positive integer k. Therefore, $b_n$ can be written as $a_1 + d(a_1k)$, which is of the form $a + (m-1)d$ and therefore part of the given sequence. [Remark: The statement can be proved in many other ways, such as induction or modular arithmetic.]
12.06.2024 14:37
We define $d$ to be the common ratio of the given sequence. We claim that the geometric progression with first term $=a_1$ and common ratio $=d+1$ is a subsequence of the given sequence. Proof 1: We know that \begin{align*} a_1(d+1)^k &= a_1\left(d^{k} + \binom{k}{1}d^{k-1} + \dots + \binom{k}{k-1}d + 1\right)\\ &= a_1 + d \cdot a_1\left(d^{k-1} + \binom{k}{1}d^{k-2} + \dots + \binom{k}{k-1} \right) \end{align*}We know that this of the form $a_1 + d(n-1)$ so $a_1(d+1)^{k}$ is a part of the given sequence for $k \in \textbf{W}$. Proof 2 (Credit to @HoRI_DA_GRe8): We know that $a_i \equiv a_1 \pmod{d}$. Acc to our claim we also know that$$r \equiv 1 \pmod{d}$$where $r$ is the common ratio. So, $r^{k} \equiv 1^{k} \pmod{d}$. Multiplying both sides $a_1$ we get, $$a_1r^{k} \equiv a_1 \pmod{d}$$Hence, $a_1r^{k}$ lies in the given sequence for any $k \in \textbf{W}$.
12.09.2024 21:45
$a_1, a_1(1 + d), a_1(1 + d)^2, \dots$