
Re: Recurrence problem
Posted:
Jul 18, 2011 1:05 PM


It helps to consider n mod 4 (not just mod 2).
With the usual notation "2^k  m" meaning 2^k divides m but 2^{k+1} does not divide m:
2^{2n}  a_{4n}  a_{4n1} 2^{2n}  a_{4n1}  a_{4n2} 2^{2n1}  a_{4n2}  a_{4n3} 2^{2n}  a_{4n3}  a_{4n4}
These four statements can then be proven (together) by induction.
Don Coppersmith > Hi all, > > Consider the sequence a_n of natural numbers such > that a_1 = 1, a_2 = 3 > and that a_n = 2 a_{n  1}a_{n  2} + 1 otherwise. > Empirical data > suggests that the greatest power of 2 that divides > a_{2n}  a_{2n  1} > is always 2^n, but I am unable to prove it. Any > ideas? > > Best regards, > > Jose Carlos Santos

