Search All of the Math Forum:

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

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

 Messages: [ Previous | Next ]
 Don Coppersmith Posts: 60 Registered: 2/2/06
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