This tree represent the set of the interval [0,1], and the number of nodes of rank n is a(n). The number nodes with index 2^2k is a(2^2k) = (2^(2k+1) + 1)/3= 2^A007583.
Proof :
Let n(k) such that a(2^2k) = 2^n(k). By recurrence we have n(k) = 2^2k - 2^2k-1 + n(k-1) = 2^2k-1 + n(k-1). With n(1) = 3 = 2+1 we obtain : n(k) = 1 + 2(1 + 2^2 + ... + 2^(2k-2)) = (2^(2k+1) + 1)/3.
Graphic representation :
0....................^
1............l.................l
2............^.................^
3.......^........^........^........^
4.....l...l... l...l... l...l... l...l
5.....l...l... l...l... l...l... l...l
6.....l...l... l...l... l...l... l...l
7.....l...l... l...l... l...l... l...l
8.....^...^... ^...^... ^...^... ^...^
9....^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
10..^^^^^^^^ ^^^^^^^^ ^^^^^^^^ ^^^^^^^^
|