Let the sequence $(a_{n})$ be deļ¬ned by $a_{1} = t$ and $a_{n+1} = 4a_{n}(1 - a_{n})$ for $n \geq 1$. How many possible values of t are there, if $a_{1998} = 0$?
Problem
Source: Turkey TST 1998 Problem 2
Tags: induction, trigonometry, algebra proposed, algebra
10.01.2012 17:55
Let $P(x)= 4x(1-x)$. Define $P_2(x) = P(x),\, P_{n+1}=P(P_n(x)),\, n=2,3,\cdots$. Apparently the problem may be restated as to find the number of different real roots of $P_{1998}(x)=0$. First to note some properties of $P(x)$. (1) When $x$ takes values from $-\infty$ to $0$, $P$ increases from $-\infty$ to $0$. (2) When $x$ takes values from $0$ to $1$, $P$ first increases from $0$ to $1$ and then decreases from $1$ to $0$. Now we will prove by induction the following assertion. (3) $P_n(x)= 0$ has $m$ roots $x_1 < x_2 < \cdots < x_m,\, m=2^{n-2} +1$. Moreover, there exist $y_i,\, i=1,2,\cdots, m-1,\, y_i \in (x_i, x_{i+1})$, such that: when $x\in (\infty, x_1)$, $P_n$ increases from $(-\infty,0)$; when $x \in [x_i, y_i]$, $P_n$ increases from $0$ to $1$; when $x \in [y_i, x_{i+1}]$, $P_n$ decreases from $1$ to $0$; when $x \in [x_m, \infty]$, $P_n$ decreases from $0$ to $-\infty$. (3) is true for n=2, let it is true for some n, we will prove (3) for n+1. $P_{n+1} = P(P_n)$, and having in mind (1) and (2), we get: $ x\in (-\infty,x_1),\, P_n \in (-\infty, 0) \, \Rightarrow P_{n+1}= P(P_n) \in (-\infty,0)$; $ x \in[x_i,y_i], \, P_{n+1}$ goes from $0$, increases to $1$ in some point $z_{i,1} \in (x_i, y_i)$ and decreses back to $0$ at $y_1$; $ x \in [ y_i, x_{i+1}] ,\, P_{n+1}$ goes from $0$, increases to $1$ in some point $z_{i,2} \in (y_i, x_{i+1})$ and decreases back to $0$ at $x_{i+1}$; $x \in (x_m, \infty),\, P_{n+1} \in (0, -\infty)$. Hence $P_{n+1}$ has $m+m-1=2.(2^{n-2}+1)-1 = 2^{n+1-2}+1$ roots: $x_1, y_1,x_2,y_2,\cdots, x_{m-1},y_{m-1},x_{m}$. Moreover, in points $z_{i,1},\, z_{i,2}$ between roots, $P_{n+1}$ reaches $1$, as described in (3). Thus, this completes the induction step. Finally, there are $2^{1998-2} +1$ real values of $t$, such that $a_{1998} = 0$.
28.02.2012 07:35
I'll use the same notation as above. $x(1-x)$ reminds us of $\sin, \cos$ ratios. Note that as $P(x)$ varies in $[0,1]$, $x$ varies in the same interval. As $P_{1998}(t)=0$, $t$ lies in $[0,1]$. So we may take $t=\sin^2{\theta}$ for some $\theta \in [0,\frac{\pi}{2}]$. Now note that $P(t)=4\sin^2 \theta (1-\sin^2 \theta)=4 \sin^2 \theta(\cos^2 \theta)=\sin^2 2\theta$. Continuing this way, $P_{1998}(t)=\sin^2 2^{1997} \theta=0$. So $\theta = \frac{k\pi}{2^{1997}}$. Hence $t=\sin^2(k\pi/2^{1997})$ where $k$ ranges over the integers. And some roots-of-unity book-keeping gives us $2^{1996}+1$ distinct values of $t$. In general, as $1998\mapsto n$, $1996\mapsto n-2$, as above. $\blacksquare$