[seqfan] Re: A120511 a(n) = min{j : A006949(j) = n}

[Max Alekseyev]

On Tue, Sep 8, 2009 at 8:55 AM, Georgi Guninski <guninski at guninski.com> wrote:

>> A120511 a(n) = min{j : A006949(j) = n}
>> A006949                A well-behaved cousin of the Hofstadter sequence
>>
>> seems to satisfy:

> a(n)=a(round(n/2)+(n mod 2))+n

I guess you meant a(n) = a(ceil(n/2)) + n.

This can be proved as follows.

Let b=A006949. It is known that
b(n) = b(n-1-b(n-1)) + b(n-2-b(n-2))
and
b(n-1) <= b(n) <= b(n-1)+1.

The following claims are trivial:

Claim 1. For any n, b(a(n))=n.

Claim 2. If m=a(n) for some n, then a(b(m))=m.

Claim 3. Let m=a(n). Then b(m)=n and b(m-1)=n-1, implying that
b(m+1) = b(m-b(m)) + b(m-1-b(m-1)) = 2*b(m-n)
is an even number.

Claim 4. Each even number in A006949 is repeated at least two times
(actually, even number of times), while each odd number in A006949
appears only once.
Proof.
If n is even, then for m=a(n), we have b(m)=n and b(m+1)=n (from Claim
3), i.e., n is repeated at least two times.
If n is odd, then for m=a(n), we cannot have b(m+1)=n since by Claim 3
b(m+1) must be even.
QED

Consider two cases:

1) If n is odd, then b(m+1) = n+1 = 2*b(m-n), i.e., b(m-n) = (n+1)/2.
Claim 4 also implies b(m-2)=n-1. Therefore,
n = b(m) = b(m-1-b(m-1)) + b(m-2-b(m-2)) = b(m-n) + b(m-n-1)
Since n is odd, we have b(m-n-1)<b(m-n) and thus a(b(m-n))=m-n.

2) If n is even, then b(m+1) = n = 2*b(m-n), i.e., b(m-n) = n/2.
Claim 4 also implies b(m-3)=b(m-2)=n-2. Therefore,
n-1 = b(m-1) = b(m-2-b(m-2)) + b(m-3-b(m-3)) = b(m-n) + b(m-n-1)
Since n-1 is odd, we have b(m-n-1)<b(m-n) and thus a(b(m-n))=m-n.

Combining these two cases, we have b(m-n) = ceil(n/2) and furthermore
m-n = a(b(m-n)) = a(ceil(n/2))
or
a(n) = a(ceil(n/2)) + n.
QED

Regards,
Max