A sequence in base 3 Take the sequence of numbers such that no two of them average to another:
$$   0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40,\ldots$$
I've discovered through experimentation that if we set the first two terms to $0$ and $1$, the rest of them can be found through the observation that if $n$ is in the sequence, so is $3n$ and $3n+1$.
I don't know how to prove it, though. I'm not even really sure where to start.
How can I prove this?
 A: This is sequence A005836 in the OEIS.
A characterization equivalent to the one you've found experimentally is that when written in base $3$, this sequence is $$0_3, 1_3, 10_3, 11_3, 100_3, 101_3, 110_3, 111_3, 1000_3, 1001_3, \dots$$
and consists precisely of the numbers whose base-$3$ representation does not use the digit $2$. (Going from $n$ to $3n$ and $3n+1$ is the same as adding a $0$ or $1$ to the end of the base-$3$ representation; that's why this is equivalent.)
This sequence does not contain a triple $(a,b,c)$ with $b = \frac{a+c}{2}$ or equivalently $2b = a+c$. If it did, note that $a+c$ can be computed without carrying in base $3$, and at some point where the digits of $a$ and $c$ disagree, we get the digit $1$ in the sum. On the other hand, all the digits of $2b$ are $2$ or $0$, so $2b$ cannot be equal to $a+c$.
It's slightly trickier to prove that this is the sequence we get by going through the integers in order and always adding an element if it can be added without creating a pair $(a,b,c)$ with $b = \frac{a+c}{2}$. By the above argument, we know that, as long as we've never added anything not in the sequence above, its next element can always be added. How do we know that we'll never add a number not in the sequence: whose base $3$ representation does contain a $2$?
I will prove this by example, because otherwise I'd have to make up messy notation, but this argument is fully general. Suppose that we're considering adding the number $x = 1021201_3$, and that so far we've not deviated from the sequence above. Define $$\begin{cases}x_{2\to 1} = 1011101_3 \\ x_{2\to 0} = 1001001_3\end{cases}$$ to be the two numbers we get by replacing every $2$ with a $1$ and a $0$ respectively. Then $x_{2\to 1}$ and $x_{2\to0}$ are both smaller than $x$, and neither contains a $2$, so both are in the sequence. But we have $$x_{2\to 1} = \frac{x_{2\to 0} + x}{2}$$ so we can't add $x$.
Note also that this sequence is not actually the densest sequence that has this property. In this sequence, among the first $3^n$ terms, we've chosen $2^n$, so among the first $N$ we choose an average of $N^{\log_3 2}$. But we can get better constructions by not picking greedily, which contain more than $N^{1-\epsilon}$  of the first $N$ positive integers for any $\epsilon>0$. The most well-known is Behrend's construction, which chooses $$N \cdot e^{- O(\sqrt{\log N})}$$ of the first $N$ positive integers.
