Let CW be an infinite binary tree where each node
has exactly two child nodes designated left and
right. If a node contains the fraction i/j, then
the left child node contains the fraction i/(i+j)
and the right child node contains the fraction
(i+j)/j. The root node contains the fraction 1/1.
If we did a breadth first search of CW, then we
would encounter the fractions
1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, ...
in that order. If we designate this sequence as
{a_{n}}, then prove that it can be
generated by the following formula:
a_{k+1} = 1/(2⌊a_{k}⌋ - a_{k} + 1)
where a_{1} = 1/1 and ⌊a_{k}⌋ is the integer part of a_{k}.

There are no comments yet.