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 ]
 William Elliot Posts: 1,948 Registered: 5/30/08
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.