[seqfan] Re: wanted: solution to a recurrence

[hv at crypt.org]

"N. J. A. Sloane" <njas at research.att.com> wrote:
:Dear Seq Fans (and especially Eric Angelini)
:
:I'm looking for a sequence a(1), a(2), ..., not all 1's, 
:that satisfies the forward-looking recurrence
:a(n+1) = a(a(n)+n+1) for n>= 1.
:
:In fact I would like the earliest such sequence.

I think if a(1) = a(2) = 1, then we have all 1s. It looks perfectly valid,
however, to have a(1) = 1, a(n) = 2 for all n > 1.

Setting a(1) = 1, a(2) = 2 requires a(3) = 2. Assume a(1) = 1, a(k) = 2
for 2 <= k < n, n >= 4. Then a(n - 1) = a(n + 1) = 2 and a(n) = a(n + 2).

If we set a(n) = 1, then a(n + 1) = a(n + 2), a contradiction. So we must
have a(n) = 2. Now by induction, the lexically first solution that is not
all 1s is a 1 followed by all 2s.

Hugo