Floor value of sum whose general term satisfy recursive relation.

Question

Consider the sequence $x_{n}$ given by $\displaystyle x_{1} = \frac{1}{3}$ and $x_{k+1}=x^2_{k}+x_{k}$

and Let $\displaystyle S = \frac{1}{x_{1}}+\frac{1}{x_{2}}+\cdots \cdots +\frac{1}{x_{2008}}$. Then $\lfloor S \rfloor $ is

Try: From $\displaystyle x_{k+1}=x^2_{k}+x_{k}=x_{k}(x_{k}+1)\Rightarrow \frac{1}{x_{k+1}}=\frac{1}{x_{k}}-\frac{1}{x_{k}+1}$

So $\displaystyle S=\sum^{2008}_{k=1}\frac{1}{x_{k+1}} = \sum^{2008}_{k=1}\bigg(\frac{1}{x_{k}}-\frac{1}{x_{k+1}}\bigg)=\frac{1}{a_{1}}-\frac{1}{a_{2009}} = 3-\frac{1}{a_{2009}}$

Could some help me how can i calculate value of $a_{2009},$ Thanks

Answer 1

The hint:

Prove that $x_4>1$ and get the answer.

I got $8$.

Answer 2

Let $y_n=\frac1{x_n}$. Then $$\tag1y_{n+1}=y_n-\frac1{\frac1{y_n}+1}=y_n-\frac{y_n}{y_n+1}=y_n\cdot\left(1-\frac1{y_n+1}\right).$$ Note that this means $0<y_{n+1}\le \frac a{a+b}y_n$ if $0<y_n\le \frac ab $. Thus if $y_n\le \frac ab<1$ then $$\tag2\sum_{k=n}^\infty y_n\le y_n\sum_{k=0}^\infty\left(\frac a{a+b}\right)^{k}=\frac{a+b}{b}y_n\le \frac{(a+b)a}{b^2}. $$ We compute the first few terms $$ \begin{align}y_1&=3\\ y_2&=3-\frac34=\frac{9}{4}\\ y_3&=\frac94-\frac{9}{9+4}=\frac{81}{52}\end{align}$$ Apparently, the exact fractions are beginning to become ugly. We note from $(1)$ that $\alpha<y_n<\beta$ implies $\alpha\cdot\left(1-\frac1{\alpha+1}\right) <x_{n+1}<\beta\cdot\left(1-\frac1{\beta+1}\right)$. Very moderate will turn out to be good enough. Say, if we have $\frac {r_n}{10}\le y_n\le \frac{s_n}{10}$ with integers $r_n,s_n$, then $\frac {r_{n+1}}{10}\le y_{n+1}=\frac{s_{n+1}}{10}$ if we let $$\tag3r_{n+1}\le r_n-\left\lceil \frac{10r_n}{r_n+10}\right\rceil,\qquad s_{n+1}=s_n-\left\lfloor\frac{10s_n}{s_n+10}\right\rfloor.$$ So instead of computing complicated fractions or unreliable numerical approximations, we use $(3)$ to compute exact but manageable bounds, starting over with $r_1=s_1=30$ to find $$\begin{array}tr_2=22&r_3=14&r_4=9&r_5=4\\ s_2=23&s_3=17&s_4=11&s_5=6\end{array} $$ From this we conclude $$8=\frac{30+22+15+9+4}{10} \le y_1+\ldots+y_5<S$$ From $y_5\le \frac 6{10}$ and $(2)$, we find $$\sum_{n=5}^\infty y_n\le\frac{96}{100} $$ so that $$ S=\sum_{n=1}^\infty y_n\le \frac{30+23+17+11}{10}+\frac{96}{100}=9.06.$$ This is a pity. With $8<S\le 9.06$ we cannot yet determine $\lfloor S\rfloor$ with certainty. But recall that we already computed $y_3=\frac{81}{52}$ and this is $<\frac{16}{10}$. Thus we can use $s_3=16$ instead of $s_3=17$ in our upper bound and this is enough to show $S<8.96$ (we could also use this to improve the values for $s_4$, $s_5$ and the tail sum, but we do not need that). We conclude $$ \lfloor S\rfloor = 8.$$