Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.
|
|
Math Forum
»
Discussions
»
sci.math.*
»
sci.math
Notice: We are no longer accepting new posts, but the forums will continue to be readable.
Topic:
Recurrence problem
Replies:
13
Last Post:
Jul 19, 2011 6:59 AM
|
 |
|
|
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_{4n-1} 2^{2n} || a_{4n-1} - a_{4n-2} 2^{2n-1} || a_{4n-2} - a_{4n-3} 2^{2n} || a_{4n-3} - a_{4n-4}
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
|
|
|
|