MathDB

Sequence generating all pairs of coprime positive integers

Source: 2021 Macedonian Balkan MO TST - Problem 2

August 18, 2021

number theorySequences

Problem Statement

Define a sequence:

x_0=1

and for all

n\ge 0

x_{2n+1}=x_{n}

and

x_{2n+2}=x_{n}+x_{n+1}

. Prove that for any relatively prime positive integers

a

and

b

, there is a non-negative integer

n

such that

a=x_n

and

b=x_{n+1}