|
|
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
|
|
