Recaman's sequence

[Don Reble]

Dear Seqfans:

NJAS asks,
> %S A064227 1,4,131,99734,181653,328002
> %N A064227 From Recaman's sequence (A005132): record values in A057167.
> %C A064227 Is this sequence infinite?

Yes, it is infinite.

For any sequence S, define the sequence Index(S), so that Index(S)[N] is
the first position where N occurs in S (or zero if it doesn't occur).

For any sequence S, define the sequence Max(S), so that Max(S)[N] is the
largest of S[1] through S[N].

Let S be the original sequence, A005132. Then A057167 is Index(S), and
Max(Index(S)) is like A064227, except that terms may be repeated.
If Max(Index(S)) has no largest element, then A064227 is infinite.

Observe that S does not have a largest element. For any position P, S[P]
is greater than P, or it is not. In the latter case, S[P+1] is greater
than P, because of the way S is constructed. Either way, for any number P,
S has an element greater than P.  

Consider now any element N of Max(Index(S)). S has an element greater
than Max(S)[N]. Call one such element E.
Since E is greater than each of S[1]..S[N], E occurs for the first time
(in S) after position N. Thus Index(S)[E] exists and is greater than N.
And Max(Index(S))[E] is greater than N. Therefore N is not the largest
element of Max(Index(S)).

That is, no element of Max(Index(S)) is the largest element, and so
A064227 is infinite.

	---

I figure, this reasoning applies to any sequence S which is unbounded.

--
Don Reble       djr at nk.ca