Date: Mon, 23 Jul 2007 10:29:13 -0700 From: Max Alekseyev Subject: Re: A006336 - Unexpected Relation to Golden Ratio? On 7/22/07, Paul D. Hanna 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