Drexel dragonThe Math ForumDonate to the Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.

Math Forum » Discussions » sci.math.* » sci.math

Topic: Recurrence problem
Replies: 13   Last Post: Jul 19, 2011 6:59 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Don Coppersmith

Posts: 58
Registered: 2/2/06
Re: Recurrence problem
Posted: Jul 18, 2011 1:05 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2015. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.