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$

Sorry for double posting but this sequence is not totally new--- http://www.artofproblemsolving.com/community/c6h366952p2019625

Bump//Any other solution?