Consider a sequence $(a_k)_{k \ge 1}$ of natural numbers defined as follows: $a_1=a$ and $a_2=b$ with $a,b>1$ and $\gcd(a,b)=1$ and for all $k>0$, $a_{k+2}=a_{k+1}+a_k$. Prove that for all natural numbers $n$ and $k$, $\gcd(a_n,a_{n+k}) <\frac{a_k}{2}$.
Problem
Source: RMO Delhi 2016, P2
Tags: number theory, greatest common divisor
11.10.2016 12:20
First we can show by induction that $\gcd(a_n,a_{n+1})=1$ . Using this , we can kill $k=1,2$ . So , we can assume that $k\geq 3$ . Let us assume for the time being that $n \geq 3$ and define a sequence $f_1=0,f_2=1,f_{k+2}=f_{k}+f_{k+1}$ . Observe that $a_n=f_{n-1}a+f_nb$ for $n \geq 3$ . Now , $a_{k+n}=f_{k+n-1}a+f_{k+n}b=(f_kf_n+f_{k-1}f_{n-1})a+(f_kf_{n+1}+f_{k-1}f_n)b=a_{n+1}f_{k}+a_nf_{k-1}$ . So , $\gcd(a_n,a_{n+k})=\gcd(a_n,a_{n+1}f_{k})=\gcd(a_n,a_{n+1}f_k)=\gcd(a_n,f_{k}) \leq f_k < \frac{b f_k}{2} < \frac{a_k}{2} $ . Now we just need to separately prove the result for $n=1,2$ under the assumption that $k > 2$ . This is doable by some simple bounding . EDIT: Note that i have used the following well - known result about the fibonacci sequence --- $f_{n+k}=f_nf_{k+1}+f_{n-1}f_k$
12.10.2016 13:27
Sorry for double posting but this sequence is not totally new--- http://www.artofproblemsolving.com/community/c6h366952p2019625
15.09.2018 10:45
Bump//Any other solution?