MathDB

sequence that contains all positive rational numbers

Source: Nordic Mathematical Contest 2013 #3

September 23, 2017

Sequencerationalnumber theory

Problem Statement

Define a sequence

{(n_k)_{k\ge 0}}

{n_{0 }= n_{1} = 1}

, and

{n_{2k} = n_k + n_{k-1} }

and

{n_{2k+1} = n_k}

for

{k \ge 1}

. Let further

{q_k = n_k }

{ n_{k-1} }

for each

{k \ge 1}

. Show that every positive rational number is present exactly once in the sequence

{(q_k)_{k\ge 1}}