Maths Olympiad Prep

Library / /275 of 377

Algebra Difficulty 5.4 AIME, harder Prove it United States

Problem:
A sequence {an}n0\{a_{n}\}_{n \geq 0} of real numbers satisfies the recursion an+1=an33an2+3a_{n+1} = a_{n}^{3} - 3 a_{n}^{2} + 3 for all positive integers nn. For how many values of a0a_{0} does a2007=a0a_{2007} = a_{0}?

Solution

Solution:
Answer: 32007\mathbf{3}^{\mathbf{2007}}. If xx appears in the sequence, the next term x33x2+3x^{3} - 3x^{2} + 3 is the same if and only if 0=x33x2x+3=(x3)(x1)(x+1)0 = x^{3} - 3x^{2} - x + 3 = (x-3)(x-1)(x+1). Moreover, that next term is strictly larger if x>3x > 3 and strictly smaller if x<1x < -1. It follows that no values of a0a_{0} with a01>2|a_{0} - 1| > 2 yield a0=a2007a_{0} = a_{2007}.

Now suppose a0=a2007a_{0} = a_{2007} and write a0=1+eαi+eαia_{0} = 1 + e^{\alpha i} + e^{-\alpha i}; the values a0a_{0} we seek will be in bijective correspondence with solutions α\alpha where 0απ0 \leq \alpha \leq \pi. Then
a1=(a01)33a0+4=e3αi+3eαi+3eαi+e3αi3eαi3eαi3+4=e3αi+e3αi+1 a_{1} = (a_{0} - 1)^{3} - 3a_{0} + 4 = e^{3\alpha i} + 3e^{\alpha i} + 3e^{-\alpha i} + e^{-3\alpha i} - 3e^{\alpha i} - 3e^{-\alpha i} - 3 + 4 = e^{3\alpha i} + e^{-3\alpha i} + 1
and an easy inductive argument gives a2007=e32007αi+e32007αi+1a_{2007} = e^{3^{2007} \alpha i} + e^{-3^{2007} \alpha i} + 1. It follows that a0=a2007a_{0} = a_{2007} is equivalent to cos(α)=cos(32007α)\cos(\alpha) = \cos(3^{2007} \alpha). Now,
cos(32007α)cos(α)=2sin(32007+12α)sin(3200712α) \cos(3^{2007} \alpha) - \cos(\alpha) = 2 \sin\left(\frac{3^{2007} + 1}{2} \alpha\right) \sin\left(\frac{3^{2007} - 1}{2} \alpha\right)
so since sin(kx)=0\sin(kx) = 0 for a positive integer kk if and only if xx is a multiple of πk\frac{\pi}{k}, the solutions α\alpha are {0,2π320071,4π320071,,π}{0,2π32007+1,,π}\{0, \frac{2\pi}{3^{2007} - 1}, \frac{4\pi}{3^{2007} - 1}, \ldots, \pi\} \cup \{0, \frac{2\pi}{3^{2007} + 1}, \ldots, \pi\}. Because our values kk are consecutive, these sets overlap only at 00 and π\pi, so there are 320073^{2007} distinct α\alpha.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.