[seqfan] Re: A120511 a(n) = min{j : A006949(j) = n}
Max Alekseyev
maxale at gmail.com
Fri Sep 11 08:25:51 CEST 2009
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
More information about the SeqFan
mailing list