Suppose that a sequence $\{a_n\}_{n=1}^\infty$ satisfies $a_1=1$ and $$a_{n+1}=a_n-\frac13a_n^2,\qquad n=1,2,3,\cdots.$$
Which of the following is true?
(A) $2<100a_{100}<\frac52$
(B) $\frac52<100a_{100}<3$
(C) $3<100a_{100}<\frac72$
(D) $\frac72<100a_{100}<4$
This problem comes from my sister's final exam (she is in high school). I have a solution, but my solution is unsatisfactory since it requires some rather complicated computation, which seems impossible to finish during an exam.
My solution. Note that the recurrence relation can be rewritten as
$$\frac1{a_{n+1}}=\frac1{a_n}+\frac1{3-a_n},\qquad n=1,2,3,\cdots.$$
Therefore,
$$\frac1{a_{100}}=1+\sum_{n=1}^{99}\frac1{3-a_n}.$$
It follows from the original recurrence relation that $a_n$ is decresing and thus $a_n\leq 1$. Using $\frac1{3-a_n}\geq \frac13$, we have $$\frac1{a_{100}}\geq 1+\frac{99}3=\frac{102}3,$$which implies that $100a_{100}\leq \frac{300}{102}<3$. Hence (C) and (D) are excluded. My gut told me that (B) should be the right answer, since $a_n$ will decreasing to $0$ (an exercise for those who are just learning the concept of limits,) in which case $\frac1{3-a_n}$ is almost $\frac13$. Let's check the correctness of (B). After some calculations we have
$$a_1=1,\qquad a_2=\frac23,\qquad a_3=\frac{14}{27},\qquad a_4=\frac{67\times 14}{27^2\times 3}=\frac{938}{2187}.$$
Since $a_n\leq a_4$ for $n\geq 4$, we have
$$\frac1{a_{100}}\leq 1+\frac12+\frac37+\frac1{3-\frac{14}{27}}+\frac1{3-\frac{938}{2187}}\times 96\approx 39.66<40,$$
where I turned to a caculator. Therefore, $100a_{100}>\frac52$. Note: I tried to use $a_3$ rather than $a_4$, which was easier to compute, but it turned out that using only $a_3$ was not enough to get the desired bound.
My question. Is there any other methods to get the upper bound of $1/a_{100}$? I want a method involving not so many caclulations. At least they can be completed in an exam in which calculators are not allowed.
Best Answer
This is pretty similar to a famous exercise about the rate of convergence of the sequence defined by $a_{n+1}=\sin(a_n)$. In your case it is pretty simple to notice that $\{a_n\}$ is positive and decreasing, hence convergent to zero, and by setting $b_n=1/a_n$ (as you cleverly did) we have
$$ b_{n+1} = b_n + \frac{b_n}{3b_n-1}= b_n+\frac{1}{3}+\frac{1}{9b_n-3}\tag{1}$$ where $$ b_{n+1} \geq b_n + \frac{1}{3}$$ implies $$ b_n \geq \frac{n+2}{3} \tag{2}$$ and $a_{100}\leq \frac{3}{102}$, which only leaves options $(A)$ and $(B)$. At this point one might guess that $(2)$ is pretty tight, hence $100 a_{100}$ is less than $3$ but pretty close to $3$ (option $\mathbf{(B)}$). Proving this requires a lower bound for $a_n$, i.e. an upper bound for $b_n$, which we can obtain by plugging $(2)$ back into $(1)$ (bootstrapping): $$ b_{n+1} \leq b_n + \frac{1}{3} + \frac{1}{3}\cdot \frac{1}{n+1} \tag{3}$$ leads to $$ b_n \leq \frac{n+H_n+1}{3} \tag{4}$$ hence $100 a_{100}\geq \frac{300}{101+H_{100}}\geq 2.8 $ and $\mathbf{(B)}$ actually is the correct answer.
An accurate approximation of $H_n=\sum_{k=1}^{n}\frac{1}{k}$ comes from $H_n\approx \log(n)+\frac{1}{\sqrt{3}}$.
A more elementary approximation of $H_{100}$ (a worse one, but still effective for our purposes) can be derived without calculators, using just telescopic series and the Cauchy-Schwarz inequality:
$$\begin{eqnarray*} H_{100} = \frac{25}{12}+\sum_{k=5}^{100}\frac{1}{k} \leq \frac{25}{12}+\sum_{k=5}^{100}\frac{1}{\sqrt{k(k-1)}}\leq \frac{25}{12}+\sqrt{\sum_{k=5}^{100}1 \sum_{k=5}^{100}\frac{1}{k(k-1)}}\end{eqnarray*}$$
leads to
$$ H_{100} \leq \frac{25}{12}+\sqrt{96\sum_{k=5}^{100}\left(\frac{1}{k-1}-\frac{1}{k}\right)}=\frac{25}{12}+\sqrt{96\left(\frac{1}{4}-\frac{1}{100}\right)}\leq \frac{25}{12}+\sqrt{24} \leq 7 $$
then to $100\,a_{100} \geq 3-\frac{1}{4}$.