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:
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}