A006336 - Unexpected Relation to Golden Ratio?

[Alec Mihailovs]

From: "Max Alekseyev" <maxale at gmail.com>
Sent: Monday, July 23, 2007 12:29 PM

> On 7/22/07, Paul D. Hanna <pauldhanna at juno.com> wrote:
>>      Consider the nice sequence A006336:
>> a(n) = a(n-1) + a(n-1 - number of even terms so far).
>> http://www.research.att.com/~njas/sequences/A006336
>> -----------------------------------------------------------
>> It seems that A006336 can be generated by a rule using the golden ratio:
>> a(n) = a(n-1) + a([n/Phi]) for n>1 with a(1)=1  where Phi = 
>> (sqrt(5)+1)/2,
>
> Lemma. The sets { [n*p] : n=1,2,3,... } and { [n*p^2] : n=1,2,3,... }
> are disjoint, and every positive integer belongs to one (and only
> one!) of these sets.
> I leave the proof of this Lemma to the reader as a challenge.
>
> Theorem. The number of even terms in A006336 up to position n-1 equals
> n-1 - [n/p].

Another proof is based on the fact that A006336 mod 2 is A005614.

The proof is rather simple, but I don't have time to write it in a simple 
way at the moment.

I hope that Max can write a simple version of it based on his proof of the 
Theorem above.

By the way, looking at that, and searching for the initial terms of A001950, 
I found that A090909 seems to be a duplicate of A001950. Again, I don't have 
much of free time at the moment and I live it to Max to prove that.

Alec