# [seqfan] binary tree sequences

Jeremy Gardiner jeremy.gardiner at btinternet.com
Sat Oct 15 21:22:47 CEST 2011

```Consider an infinite complete binary tree with root node labelled 1 and
child nodes at each fork labelled 0 and 1.

Then a path from the root to any node in the tree corresponds to a (finite)
increasing sequence of (binary representations of) positive integers and
every positive integer corresponds to a unique node in the tree.

Now define a sequence A(n) in terms of some arbitrary binary sequence B(n)
by a(0) = 1, a(n+1) = 2*a(n) + b(n+1) for n >= 0.

Note that A(n) and B(n) have the same parity for n > 0.

I call such a sequence A(n) a binary tree sequence since A(n) corresponds to
some path through the binary tree just described.

Binary tree sequences have the following properties:

Any such A(n) is a "superincreasing" sequence where each term is greater
than the sum of all the preceding terms (see
http://en.wikipedia.org/wiki/Superincreasing_sequence)

Given some term a(n) for n > 0 we can find a(n-1) by removing the least
significant bit of the binary representation of a(n) ("right shift").

All the binary tree sequences are 'squeezed' between 2^n = 1,2,4,8,16, ...
and 2^(n+1)-1 = 1,3,7,15,31, ... in the sense that a(n) >= 2^n and a(n) <=
2^(n+1)-1 for n >= 0.

The first few terms of a binary tree sequence can only be one of the
following:

1,2,4,8,16,
1,2,4,8,17,
1,2,4,9,18,
1,2,4,9,19,
1,2,5,10,20,
1,2,5,10,21,
1,2,5,11,22,
1,2,5,11,23,
1,3,6,12,24,
1,3,6,12,25,
1,3,6,13,26,
1,3,6,13,27,
1,3,7,14,28,
1,3,7,14,29,
1,3,7,15,30,
1,3,7,15,31,

The OEIS contains several examples of binary tree sequences including
A000079(n), A000225(n+1) and A000975(n+1).

I wonder if binary tree sequences are sufficiently interesting, perhaps to
be worth an index entry in the OEIS?

Are these sequences already known by another name?

Jeremy Gardiner

```