|
|
Re: Recurrence problem
Posted:
Jul 19, 2011 5:11 AM
|
|
On Mon, 18 Jul 2011, [ISO-8859-1] José Carlos Santos wrote:
> 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?
>
a1 = 1; a2 = 3; a3 = 7
Let
. . dj = a_2j - a_(2j-1)
. . cj = a_(2j+1) - a_2j
d1 = a2 - a1 = 2; 2^1 | d1
c1 = a3 - a2 = 4; 2^2 | c1
If 2^j | dj, 2^(j+1) | cj, then
d_(j+1) = a_(2j+2) - a_(2j+1
= 2.a_(2j+1) a_2j + 1 - 2.a_2j a_(2j-1) - 1
= 2.a_2j (a_(2j+1) - a_(2j-1)
= 2.a_2j (cj + dj)
2^(j+1) | d_(j+1)
c_(j+1) = a_(2j+3) - a_(2j+2)
= 2.a_(2j+2) a_(2j+1) + 1 - 2.a_(2j+1) a_2j- 1
= 2.a_(2j+1) (a_(2j+2) - a_2j)
= 2.a_2j (d_(j+1) + cj)
2^(j+2) | c_(j+1)
Thus for all j in N, 2^j | dj, 2^(j+1) | cj.
If n is the smallest integer with 2^n | d_n, not 2^(n+1) | d_n,
then 2^(n+2) | d_(n+1).
From above
d_(n+1) = 2.a_2n (c_n + d_n).
Thus 2 | a_2n, which is odd.
Hence for all j, 2^j is the largest power of 2 that divides dj.
|
|
