Spinoff solution
The target sequence G(n) = F(n)*F(n+1) satisfies an order3 homogeneous linear recurrence:
G(n) = 2*G(n1) + 2*G(n2)  G(n3),
so we need a homogeneous linear system of order at least three to generate it,
which means a dictionary of at least three letters.
Three letters actually suffice; I found three such solutions.
Dictionary 1:
{"A": "BC", "B": "AAB", "C": "ABC"}.
Dictionary 2:
{"A": "AB", "B": "AAAC", "C": "AAC"}.
Dictionary 3:
{"A": "AB", "B": "AABC", "C": "B"}.
In each case, the game starts with letter "A";
letter "C" is always the rarest one, at least for index n>2.
Dieter proved a nice closedform representation for lettercounting functions.
Dictionary 1:
A(n) = F(n+1)*F(n2);
B(n) = F(n)*F(n1);
C(n) = F(n1)^2.
Dictionary 2:
A(n) = F(n)^2;
B(n) = F(n1)^2;
C(n) = F(n1)*F(n2).
Dictionary 3:
A(n) = F(n)*F(n1) + F(n2)^2;
B(n) = F(n)*F(n1);
C(n) = F(n1)*F(n2).
Dictionary 1 seems the most promising one, as letter "C" occurs slightly more often (by a factor F(n1)/F(n2), which converges to the golden ratio phi=1.618...).
We can change the three spellings in 2*3*6 = 36 ways.
We can replace letters "A","B","C" with letters "I","B","M" in 6 ways.
Among the 216 possible variations, I chose the following one:
{"M": "IB", "I": "MIM", "B": "IBM"}
The game starts with letter "M";
letter "B" is the rarest one for n>2, so the upper bound IBM(n) <= B(n) is sharp.
This solution almost reaches such bound:
IBM(n) = B(n) if n is odd,
IBM(n) = B(n)1 if n is even.
Proof.
In each string of the sequence, we can only find the twoletter substrings "BM", "IB", "IM", and "MI".
The sequence starts with a oneletter string, so the claim is trivially true for n=1.
The given list contains all the twoletter substrings of the chosen spellings, so the claim is also true for n=2.
Then, only substrings "BM" and "MI" can arise from a permitted concatenation of spellings:
"BM": "IBMIB",
"IB": "MIMIBM",
"IM": "MIMIB",
"MI": "IBMIM",
so the claim is also true for every index n>2 by induction.
In particular, letter "B" is always preceded by letter "I" and followed by letter "M", unless it occurs at the beginning or at the end of a string, so the lower bound IBM(n) >= B(n)2 holds.
For index n>1, it's easy to check that the first few string characters follow a regular pattern with period 2:
IB... > MIM... > IB... > MIM...
and the same holds for the last few string characters:
...IB > ...IBM > ...IB > ...IBM
so letter "B" never occurs at the begin of a string, but it occurs at the end of evenindexed strings.
For the given solution, the ratio IBM(n)/G(n) converges to the value 1/phi^3 ~ 0.236
Last fiddled with by 0scar on 20200828 at 14:32
