Terms of Stanley Sequences

Question

Stanley Sequences (named after R. P. Stanley) are integer sequences beginning with 0, k where k is an integer bigger than 0, and where every following member is chosen to be the smallest integer bigger than the previous term so that no three terms (not necessarily consecutive) form an arithmetic sequence. Another way of saying this is that we want to lexicographically the first three-terms-arithmetic-sequence-free sequence beginning with 0, k. An even simpler way to put is that we search for the smallest integer bigger than the former term so that no three terms x, y, and z construct the equation x + z = 2y.

Let's look at the sequence where k = 1. The first few terms of this sequence are: 0, 1, 3, 4, 9, 10, 12, 13, 27, 28.

We notice an interesting thing if we write the indexes of the terms of S(1) (the sequence where k=1), where a a_0=0, a_1=1, and so on in binary.

We get 0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001. Now let's write the values for these indexes in ternary => 0, 1, 10, 11, 100, 101, 111, 1000, 1001. This goes on forever. Another way of putting it is that each term of S(1) is obtained by writing the index in binary and reading it in ternary. Another way to look at this is to collect all the numbers in ternary without a '2' in their representation.

What is an easy way to prove this? Also, can we suggest other numerical systems we can use that give us a similar relationship when k is different than 1?

What I've tried doing is proving that since the only way to obtain a '2' when we multiply by 2 in ternary is by starting with a '1' (without carrying over, I mean) there are only a few cases which we should aim to avoid and then form a case by case analysis to prove that these are in fact the smallest remaining options but that is both unclear and tedious. Do you have any suggestions?

Thank you in advance, and please excuse any language mistakes I may have made...

(If someone wonders I'm researching the topic for fun. It's not for school work or sth like this)

Answer 1

The $k=1$ case is not hard.

a) The sequence of ternary-2-free numbers is free of solutions to $x+z=2y$ with $x\ne z$: Since $x,z$ are $2$-free, adding produces no carries, hence $x+z$ has at least one digit $1$, namely at a place where $x$ and $z$ differ. The addition in $y+y$ alo produces no carries, hence $y+y$ consists only of digits $0$ and $2$. Therefore $x+y\ne 2z$

b) Any lexically smaller sequence has a solution to $x+z=2y$: Let $b_0, b_1, b_2,\ldots $ be lexically smaller than our ternary-2-free sequence $a_0,a_2,a_2,\ldots$. Let $n$ be minimal with $b_n\ne a_n$ (and hence with $b_n<a_n$). Since the ternary-2-free numbers $<a_n$ are precisely $a_0,\ldots, a_{n-1}$, we conclude that $b_n$ is not 2-free. Let $x$ be the number that has ternary digit $0$ where $b_n$ has digit $0$ and has digit $1$ where $b_n$ has digit $1$ or $2$. Let $y$ be the number that has ternary digit $1$ where $b_n$ has digit $1$ and has digit $0$ where $b_n$ has digit $0$ or $2$. Then $x,y$ are $<b_n$ and 2-free, hence occur among $b_0,\ldots, b_{n-1}$. Also, we verify that $b_n+y=2x$ because adding $y$ turns every $1$ of $b_n$ into a $2$.