Date: Mon, 23 Jul 2007 10:29:13 -0700
From: Max Alekseyev <maxale(AT)gmail.com>
Subject: Re: A006336 - Unexpected Relation to Golden Ratio?

On 7/22/07, Paul D. Hanna <pauldhanna(AT)juno.com> wrote:
>
>
> Seqfans,
>      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
> begins:
> [1,2,3,5,8,11,16,21,29,40,51,67,88,109,138,167,207,258,309,376,...].
>
> -----------------------------------------------------------
> 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,
>
>
> I.e. the number of even terms up to position n-1 equals:
> n-1 - [n/Phi] for n>1 where Phi = (sqrt(5)+1)/2.

To simplify notation, let p = 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].

Proof by induction:

Suppose that the number of even terms in A006336(1..n) equal n -
[(n+1)/p] for every n=2..m. In other words, A006336(n) is even iff n -
[(n+1)/p] = (n-1 - [n/p])  + 1, that is equivalent to:
A006336(n) == [(n+1)/p] - [n/p]  (mod 2).

We will prove that the same statement is true for n=m+1.

By the definition of A006336 and our induction hypothesis, we have
a(m+1) = a(m) + a([(m+1)/p]) == [(m+1)/p] - [m/p] + [([(m+1)/p]+1)/p]
- [[(m+1)/p]/p] (mod 2).
Therefore, we need to prove that
[(m+2)/p] - [(m+1)/p] == [(m+1)/p] - [m/p] + [([(m+1)/p]+1)/p] -
[[(m+1)/p]/p] (mod 2)
or
[(m+2)/p] + [m/p] + [([(m+1)/p]+1)/p] + [[(m+1)/p]/p] == 0 (mod 2).

Let m+1 = q*p + r, where q is integer and 0 < r < p, and q = s*p + t,
where s is integer and 0 < t < p. Then m+1 = (s*p + t)*p + r = s*p^2 +
t*p + r.

It is easy to see that [(m+2)/p] + [m/p] = 0 (mod 2) if and only if
p-1 < r < 1.
Similarly, [([(m+1)/p]+1)/p] + [[(m+1)/p]/p] == 0 (mod 2) if and only
if t < p-1.

There are three cases when [(m+2)/p] + [m/p] and [([(m+1)/p]+1)/p] +
[[(m+1)/p]/p] may have different oddness:

1) If p-1 < r < 1 and t > p-1 then m = [q*p] and m+1 = [(q+1)*p].
We also have
m+1 = s*p^2 + t*p + r > s*p^2 + (p-1)*p + p - 1 = (s+1)*p^2 - 1
and
m+1 = s*p^2 + t*p + r < s*p^2 + p*p + 1 = (s+1)*p^2 + 1,
implying that [(s+1)*p^2] = m+1 or [(s+1)*p^2] = m, a contradiction to Lemma.

2) If t < p-1 and r < p-1 then m = [q*p] and m+2 = [(q+1)*p].
We also have
m+1 = s*p^2 + t*p + r > s*p^2
and
m+1 = s*p^2 + t*p + r < s*p^2 + (p-1)*p + p-1 = (s+1)*p^2 - 1,
implying that either [s*p^2] = m or [(s+1)*p^2] = m+2, a contradiction to Lemma.

3) If t < p-1 and r > 1 then m-1 = [q*p], m+1 = [(q+1)*p].
We also have
m+1 = s*p^2 + t*p + r > s*p^2 + 1
and
m+1 = s*p^2 + t*p + r < s*p^2 + (p-1)*p + p = (s+1)*p^2
implying that either [s*p^2] = m-1 or [(s+1)*p^2] = m+1, a
contradiction to Lemma.

Therefore, [(m+2)/p] + [m/p] = 0 (mod 2) if and only if [(m+2)/p] +
[m/p] = 0 (mod 2), implying that [(m+2)/p] + [m/p] + [([(m+1)/p]+1)/p]
+ [[(m+1)/p]/p] == 0 (mod 2).

Q.E.D.

Max