MathDB

GCD of terms of Fibonacci style sequence

Source: RMO Delhi 2016, P2

October 11, 2016

number theorygreatest common divisor

Problem Statement

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}

.

Back to Problems View on AoPS