Math Help -> Puzzles -> Semi-periodic sequence -> Answer 

Consider the sequence given by the recursion a₀ = 1, a₁=1/3, a_n+1 = 2/3*a_n - a_n-1 (n ³ 1).  Prove that there exists a positive integer n such that a_n > 0.9999.

I wrote a program, and I found that a₂₄₅ = 0.999969287.  Can anybody give an exact mathematical proof?

Proof, by induction:

True for n = 0 and n = 1, because cos 0=1 and cos q=1/3.

2/3 cos n q - cos (n-1) q  
= 2/3 cos nq - (cos nq cos q + sin nq sin q),  from the sum of cosine identity
= (2/3 - cos q) cos nq - sin nq sin q
= 1/3 cos nq - sin nq sin q,  because cos q = 1/3 
= cos nq cos q - sin nq sin q,  again because cos q = 1/3 
= cos (nq + q),  from the sum of cosine identity 
= cos (n+1)q,
so by induction a_n = cos nq for all n.

If q/p is rational, a_n is periodic, so there exists an n such that a_n=a₀=1;
And if q/p is irrational, nq is dense in the circle so a_n is dense in [-1,1].

This proof doesn't depend on q/p being irrational.  It's not hard to show that q/p is irrational, though.

2 cos nq is a monic polynomial in 2 cos q with integer coefficients (obvious if you think about it, since 2 cos q = e^iq + e^-iq). Hence if 2 cos nq is 2 for any n > 0, 2 cos q has to satisfy a nontrivial monic polynomial equation over , i.e. 2 cos q is an algebraic integer. 2/3 is not an algebraic integer (it's not an integer). So a_n is never equal to 1, and thus q/p is irrational. (Corollary: The only rational multiples of p that have rational cosines are integer multiples of p/3.)

As for the interesting patterns found in the investigation, 

cos^-1 1/3 = q = 1.23095941734077

51q = 62.7789302843795, and 10(2p) = 62.8318530717959, so 51q is just 0.08% less than 10 trips around the circle.
46q = 56.6241331976756, and 9(2p) = 56.5486677646163, so 46q is just 0.13% more than 9 trips around the circle.

By interspersing 54 groups of 46q, (about 9 trips around the circle) with 77 groups of 51q, (about 10 trips around the circle), we get a total of 6411q, which is almost exactly (to within 0.000001%, or one part in 100 million) 1256 trips around the circle.

The ratio of the number of q's to the number of trips around the circle, 6411/1256=5.1043, is the primary observed period of this sequence.