Infinite Binary Tree (Posted on 2013-04-11)

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
{an}, then prove that it can be 
generated by the following formula:

   ak+1 = 1/(2⌊ak⌋ - ak + 1) 

where a1 = 1/1 and ⌊ak⌋ is the integer part of ak.

	Submitted by Bractals
No Rating
Solution:	(Hide)
Preliminary Stuff: In the following the letters a-q will denote natural numbers and the letters r-z will denote nodes in the CW tree ( r will always denote the root node ). The root node is at level 0 in the CW tree, its two children are at level 1, its four grandchildren at level 2, and so on. Thus, there are 2k nodes at level k. f(w) will denote the fraction contained in node w ( f(r) = 1/1 ). The left and right children of node w will be denoted by wL and wR respectively. wLk = w if k=0 = wL if k=1 = (wL)Lk-1 if k>1 Similarly for R. If f(w) = a/b, then a a/b f(w) f(wL) = ----- = ------- = -------- a+b a/b+1 f(w)+1 f(wL) f(w) f(wL2) = f((wL)L) = --------- = ---------- f(wL)+1 2*f(w)+1 f(w) f(wLk) = ---------- (1) k*f(w)+1 a+b f(wR) = ----- = a/b+1 = f(w)+1 b f(wR2) = f((wR)R) = f(wR)+1 = f(w)+2 f(wRk) = f(w)+k (2) Now for the problem If y is the successor node of node x in a breadth first search, then we must show that f(y) = 1/(2⌊f(x)⌋-f(x)+1) (3) There are two cases: Case I: Nodes x and y are at the same level. Let z be the nearest ancestor of x and y. Then x = zLRj and y = zRLj for some j≥0. f(x) = f((zL)Rj) = f(zL)+j f(z) = -------- + j (4) f(z)+1 ⌊f(x)⌋ = j (5) f(zR) f(y) = f((zR)Lj) = ------------ j*f(zR)+1 f(z)+1 = -------------- j*(f(z)+1)+1 1 1/f(y) = -------- + j (6) f(z)+1 Adding (4) and (6) gives 1/f(y)+f(x) = 1+2j = 2⌊f(x)⌋+1 Therefore, f(y) = 1/(2⌊f(x)⌋-f(x)+1) Case II: Node x is the rightmost node at level k and y is the leftmost node at level k+1. Then x = rRk and y = rLk+1. f(x) = f(rRk) = f(r)+k = k+1 (7) ⌊f(x)⌋ = k+1 (8) f(r) f(y) = f(rLk+1) = -------------- (k+1)*f(r)+1 1/f(y) = (k+1)+1/f(r) = k+2 (9) Adding (7) and (9) gives 1/f(y)+f(x) = 2(k+1)+1 = 2⌊f(x)⌋+1 Therefore, f(y) = 1/(2⌊f(x)⌋-f(x)+1). QED Note: If you would like to learn more about the CW tree - google "Calkin Wilf tree"