Ratio-Determined Insertion Sequences and the Tree of their Recurrence Types
John W. Layman
Virginia Polytechnic Institute and State University
June 23, 2003


1. Background: An Unrestricted Insertion Sequence.

Start with the (finite) sequence {1,1} and repeatedly form a new longer sequence by inserting between each pair of terms a,b their sum a+b. The first few stages of this process give

{1,1}
{1,2,1}
{1,3,2,3,1}
{1,4,3,5,2,5,3,4,1}
{1,5,4,7,3,8,5,7,2,7,5,8,3,7,4,5,1}
etc.

This sequence of sequences does not converge. However, if these sequences are juxtaposed, with the final 1 omitted from each, we get the sequence {1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,1,5,4,7,3,8,5,7,2,7,5,8,3,7,4,5,1,...} which is Stern's diatomic sequence, A002487 in the Online encyclopedia of Integer Sequences (OEIS), where numerous references and links may be found. This sequence is related to the well-known Stern-Brocot or Farey tree.
 
 

2. A Ratio-Determined Insertion Sequence (RDIS).

Again start with {1,1} and repeatedly form new sequences by inserting between each pair of terms a,b their sum a+b IF AND ONLY IF 0.5b is less than or equal to a. The first few stages are

{1,1}
{1,2,1}
{1,3,2,3,1}
{1,3,5,2,5,3,4,1}
{1,3,8,5,7,2,5,8,3,7,4,5,1}
{1,3,8,13,5,...}
{1,3,8,21,13,...}
etc.

This process clearly converges, and in fact converges to {1,3,8,21,55,144,377,987,...}, which is A001906, a bisection of the Fibonacci sequence A000045 defined by F(1)=1, F(2)=1, and for n>1, F(n)=F(n-1)+F(n-2).

This process of generating a ratio-determined insertion sequence can be carried out for any ratio k where 0<k<=1. It is easy to see that if k=1 the sequence determined is {1,2,3,4,5,6,7,...}, i.e. the sequence of natural numbers. For k=1/3, the process gives

{1,1}
(1,2,1}
(1,3,2,3,1}
{1,4,3,...}
{1,4,7,3,...}
{1,4,11,7,...}
{1,4,15,11,...}
etc.,

converging to {1,4,15,56,209,780,2911,10864,40545,...}=A001353.

Another example is obtained when k=0.376, giving the sequence {1,3,8,29,79,287,782,...} =A080874.

It does not appear that this type of sequence has been studied previously.
 
 

3. Some Conjectures about RDIS.

Numerous computational experiments with RDIS lead to several conjectures. Some of them follow.

(C.1) Each RDIS satisfies a recurrence of the form a(n)=Ca(n-D)-a(n-2D), for some positive integers C and D.

Examples are provided by the sequences given in the previous section which have the following recurrences:
    k=0.33333; {1,4,15,56,209,780,...}; a(n)=4a(n-1)-a(n-2),
    k=0.376; {1,3,8,29,79,287,...}; a(n)=10a(n-2)-a(n-4),
    k=0.5; {1,3,8,21,55,144,...}; a(n)=3a(n-1)-a(n-2),
    k=1; {1,2,3,4,5,6,7,8,...}; a(n)=2a(n-1)-a(n-2).

In the following it will be convenient to denote the RDIS generated using the insertion ratio k by I(k), and to refer to a sequence satisfying the recurrence a(n)=Ca(n-D)-a(n-2D) as having recurrence type (C,D).

(C.2) For each positive integer m there exists a RDIS I(1/(m+1)) with insertion ratio 1/(m+1) and recurrence type (m+1,1).

Examples are the sequences I(1/3), I(0.376), I(1/2), and I(1) with recurrence types (4,1), (10,2), (3,1), and (2,1), respectively, given above.
 

(C.3) If there exists an RDIS with recurrence type (C,D), then there are exactly two distinct RDIS satisfying that recurrence. Furthermore, these two sequences have the same first D terms and (obviously) differ in the (D+1)th term.

For example the recurrence type (4,1) is satisfied by I(0.33333333)={1,4,15,56,209,780,...}, already given above, and also by I(0.33344)={1,3,11,41,153,571,2131,...}.

Another pair of examples is I(0.62048)={1,2,5,13,21,50,129,208,495,...} and I(0.62528)= {1,2,5,8,19,49,79,188,485,...}, both of recurrence type (10,3).

We call such pairs of two RDIS sequences satisfying the same recurrence RDIS "twins".

A survey of the OEIS finds more than forty sequences that are RDIS sequences, almost all of them of recurrence type (m,1).  Many of them occur together with their twin, but in a few cases the twin sequence does not appear (these, and some others, will be submitted to the OEIS soon).
 
 

4. The Insertion Tree of Recurrence Types of RDIS and More Conjectures.

One of the more fascinating aspects of the family of RDIS sequences is the tree structure of their recurrence types, indicated by several additional conjectures.

(C.4) Let m be any integer >1. Then between I(1/m) with rcur type (m+1,1) and I(1/(m-1)) with rcur type (m,1), there exists I(k3) with 1/m<k3<1/(m-1) and rcur type (m(m-1)-2,2).

An example is given by I(1/3) with rcur type (4,1), I(1/2) with rcur type (3,1), and I(0.376) with rcur type(3*4-2,2)=(10,2), all given previously.

Now, given any integer m>1, we will form an insertion tree of recurrence types. In this process it is useful to think of an inserted term as a "child" and the two terms between which a term is inserted as "parents". Start with types {(m-1,1),(m(m-1)-2,2),(m,1)}, of which the first and third are parents and the middle one a child. From this point on repeatedly insert between each pair, consisting of a child and one of its parents, the type (L*R-X,l+r), where L and R are the first members of the pair(C,D) of the types on the left and right of the inserted pair, respectively, X is the first member of the unused parent of the child, and l and r are the second members of the pair of types on the left and right of the inserted pair, respectively.

In order to illustrate this process more clearly, we take the case m=3. The tree then begins:

(2,1)                                                                                                 (3,1)

                                                  (4,2)

                         (5,3)                                               (10,3)

            (6,4)                     (18,5)                   (37,5)                      (26,4)

      (7,5)       (28,7)       (86,8)        (67,7)     (138,7)       (366,8)       (257,7)      (68,5)

etc.

The term (5,3) is given by (L*R-X,l+r) where L=2, R=4, X=3, l=1, and r=2. Similarly, for (18,5) we have L=5, R=4, X=2, l=3, and r=2.

(C.5) For any recurrence (C,D) occurring in the tree above there exists an insertion sequence I(k) satisfying that recurrence, where k lies between the insertion ratios of sequences corresponding to the parent recurrences of (C,D). Furthermore, every insertion sequence has a recurrence type that occurs in such a recurrence tree for some integer m.

As an example, consider

I(0.75008)={1,2,3,4,9,14,19,43,67,91,206,321,436...} with recurrence type (5,3),
I(0.79136)={1,2,3,4,9,14,19,43,67,91,115,254,393,...} with recurrence type (28,7), I(0.79296)={1,2,3,4,9,14,19,24,53,82,111,140,309,,...} with recurrence type (6,4).
 
 

5. Appendix.

Computational routines were written to examine all sequences in the OEIS as of June 3, 2003, to see if they were RDIS sequences I(k) and, if so, to determine their k-value and their recurrence type (C,D), for C<=100 and D<=6.
The list of sequences found is given below.  The fact that several pairs of sequences have the same k-value and recurrence type indicates that these pairs are essentially duplicate entries.

Note that the twins of A078362, A078364, etc. were missing on June 3, 2003 when the OEIS was examined.  Also, it is clear that sequences constituting only a very shallow portion of the tree structure actually appeared in the OEIS when examined.

A-number       k-value         Rcur. type
A082981    0.79538690476   {6,4}
A082630    0.63988095238   {4,2}
A011783    0.60714285714   {3,1}
A001519    0.60714285714   {3,1}
A001906    0.41129032258   {3,1}
A080874    0.37802419355   {10,2}
A001835    0.34475806452   {4,1}
A079935    0.34475806452   {4,1}
A001353    0.28861788618   {4,1}
A004253    0.25508130081   {5,1}
A004254    0.22303921569   {5,1}
A001653    0.20281862745   {6,1}
A001109    0.18196721311   {6,1}
A049685    0.16844262295   {7,1}
A004187    0.15375586854   {7,1}
A070997    0.14407276995   {8,1}
A001090    0.13315696649   {8,1}
A070998    0.12588183422   {9,1}
A018913    0.11744505495   {9,1}
A072256    0.11177884615   {10,1}
A004189    0.10506050605   {10,1}
A078922    0.10052255226   {11,1}
A004190    0.09504504505   {11,1}
A077417    0.09132882883   {12,1}
A004191    0.08677685950   {12,1}
A078362    0.07983460560   {13,1}
A001570    0.07721055980   {14,1}
A007655    0.07392253137   {14,1}
A078364    0.06882686850   {15,1}
A077412    0.06438923395   {16,1}
A078366    0.06048976608   {17,1}
A007805    0.05898209064   {18,1}
A049660    0.05703607410   {18,1}
A078368    0.05395578825   {19,1}
A075839    0.05275596277   {20,1}
A075843    0.05119141136   {20,1}
A077421    0.04643395820   {22,1}
A077423    0.04248601840   {24,1}
A029548    0.03170535625   {32,1}
A077420    0.03030884158   {34,1}
A029547    0.02981427175   {34,1}
A078987    0.02663687309   {38,1}
A078988    0.01538573469   {66,1}