A005228: The Difference Sequence
1, 3, 7, 12, 18, 26, 35, 45, 56, 69, 83, ...

This self-generating sequence from Godel, Escher Bach: An Eternal Golden Braid is fairly cute. It starts with 1 and its terms are those terms whose forward differences are not the terms. The differences in the sequence are exactly the differences of the sequence from the natural numbers. 2 is not in the sequence, for instance, because if it was then 2-1=1 would be one of the differences, but 1 is in the sequence. Furthermore, it is the lexicographically earliest such sequence. Here's one way to construct it:

1. initialize a variable k to 1
2. if adding k to the sequence does not introduce a forward difference that is already in the sequence, add k to the sequence
3. increment k and goto 2.

But there's another, better way. Call the sequence S, and call the sequence of differences (2, 4, 5, 6, 8, ...) T. Then S[n+1]=S[n]+T[n]. In other words, the next term in the sequence is formed by adding the next needed difference to the last term. Neat. The terms grow fast enough that there are always known differences available to add on. How fast do they grow?

1. Consider the first k terms of S. A lower bound on the sum of the first differences is sum(i,i=1..k-1) = k^2/2-k/2, so S is Omega(n^2).
2. Since S and T together make up the positive integers, at least one must be Theta(n).
3. Thus T is Theta(n) and S[n+1]=sum(T[i],i=1..n), so S is Theta(n^2).

Another question is whether there is a monotonic sequence X which has that every positive integer is either in X or a difference of some pair of terms of X, exactly once. The difference sequence, but not limited to differences between consecutive terms. Does anyone know?