Sum $\text{S} = \sum_{i = 2}^{2008}{\frac{1}{a_i}},$ where $a_1 = \frac{1}{3}$ and $ a_{n + 1} = a_n^2 + a_n.$

Question

Define the sequence $\{a_n\}$ where $n \in \mathbb{Z^+}$ given by $a_1 = \frac{1}{3}$ and $$ a_{n + 1} = a_n^2 + a_n.$$ Let $$\text{S} = \sum_{i = 2}^{2008}{\frac{1}{a_i}},$$ then find $\lfloor S \rfloor$ where $\lfloor X \rfloor$ denotes the greatest integer lesser than or equal to $X$.

P.S.: The obvious approach would be to telescope, but as far as I can see, terms do not cancel at all and the estimation of S becomes cumbersome. I have also tried modifying it by adding $\frac{1}{4}$ to both sides and defining $b_n = a_n + \frac{1}{2}$ gives us $$b_{n + 1} = b_n^2 + \frac{1}{4}$$ but this doesn't help me in any way to estimate S. One can read off that the original sequence is increasing but i am unable to put an upper bound (such as a G.P.) to find [S].

Answer 1

The answer is $5$.

Much thanks to @JohnBentin for pointing out the embarrassing flaw in my previous solution.

We may easily calculate the values of $a_2,a_3$ and $a_4$ by hand, and this gives us $\frac{4}{9}, \frac{52}{81}$ and $ \frac{6916}{6561} > 1$ respectively. Since all the terms in $\{a_n\}$ are positive, $a_{n+1}=a^2_n+a_n>a_n$, so the sequence is strictly increasing, which immediately allows us to conclude that $∀ \ n≥4, a_n>1$.

Claim: $\forall \ n \geq 4,\frac{1}{a_n}-\frac{1}{a_{n}+1} < \frac{1}{a_n}-\frac{1}{a_{n+1}} $.

Proof: Equivalently, we show that $a_{n+1}>a_n+1$. But $a_{n+1}=a_{n}(a_{n}+1)>a_{n}+1$, since $a_n>1 \ \forall \ n \geq 4$, which concludes our proof.

Now, $$S=\sum_{i=2}^{2008}\frac{1}{a_i}=\sum_{k=1}^{2007}\frac{1}{a_{k+1}}$$ Here, we carry out the substitution $i=k+1$.

Thus, $$S=\sum_{k=1}^{2007}\frac{1}{a_{k+1}}=\sum_{k=1}^{2007}\frac{1}{a_k(a_{k}+1)}=\sum_{k=1}^{2007}\left(\frac{1}{a_{k}}-\frac{1}{a_k+1}\right)$$

Next, we derive both a lower and upper bound for $S$.

Lower Bound:

$$S=\left(\frac{1}{a_1}-\frac{1}{a_1+1}\right)+\left(\frac{1}{a_2}-\frac{1}{a_2+1}\right)+\left(\frac{1}{a_3}-\frac{1}{a_3+1}\right)+\left(\frac{1}{a_4}-\frac{1}{a_4+1}\right) + ... + \left(\frac{1}{a_{2007}}-\frac{1}{a_{2007}+1}\right) $$

$$> \left(\frac{1}{a_1}-\frac{1}{a_1+1}\right)+\left(\frac{1}{a_2}-\frac{1}{a_2+1}\right)+\left(\frac{1}{a_3}-\frac{1}{a_3+1}\right)+\left(\frac{1}{a_4}-\frac{1}{a_4+1}\right)+\left(\frac{1}{a_5}-\frac{1}{a_5}\right)+\left(\frac{1}{a_6}-\frac{1}{a_6}\right)+...+\left(\frac{1}{a_{2007}}-\frac{1}{a_{2007}}\right)$$

$$=\left(\frac{1}{a_1}-\frac{1}{a_1+1}\right)+\left(\frac{1}{a_2}-\frac{1}{a_2+1}\right)+\left(\frac{1}{a_3}-\frac{1}{a_3+1}\right)+\left(\frac{1}{a_4}-\frac{1}{a_4+1}\right) \approx 5.22 > 5 $$

Upper Bound: This is where we make use of the above stated claim, and employ the trick of using a telescoping series.

$$S < \left(\frac{1}{a_1}-\frac{1}{a_1+1}\right)+\left(\frac{1}{a_2}-\frac{1}{a_2+1}\right)+\left(\frac{1}{a_3}-\frac{1}{a_3+1}\right)+\left(\frac{1}{a_4}-\frac{1}{a_5}\right)+\left(\frac{1}{a_5}-\frac{1}{a_6}\right)+\left(\frac{1}{a_6}-\frac{1}{a_7}\right)+...+\left(\frac{1}{a_{2007}}-\frac{1}{a_{2008}}\right)$$

$$=\left(\frac{1}{a_1}-\frac{1}{a_1+1}\right)+\left(\frac{1}{a_2}-\frac{1}{a_2+1}\right)+\left(\frac{1}{a_3}-\frac{1}{a_3+1}\right)+\frac{1}{a_4}-\frac{1}{a_{2008}}$$

$$< 5.82-\frac{1}{a_{2008}} < 6 $$

Finally, combining the above, we conclude that $S$ is strictly in-between $5$ to $6$, i.e. $\lfloor S \rfloor =5$, and we are done.

Answer 2

Hint: As you just need to calculate [S], notice that when $a_n$>2, $a_{n+1}>3a_n$, therefore $\frac{1}{a_{n+1}}<\frac{1}{3a_n}$ then use geometric sequence, this sum is less than...

Answer 3

Start from recurrence relation $a_{n+1} = a_n(a_n+1)$, it is clear if we start from any $a_1 > 0$, $a_n$ will be a strictly increasing sequence.

If for some $N$, we have $a_N = \alpha > 1$, then for all $n \ge N$, we have $$a_{n+1} = a_{n}(a_{n}+1) \ge a_n(1+\alpha) \quad\implies\quad \frac{1}{a_{n+1}} \le \frac{1}{a_n(1+\alpha)}$$

This implies for all $k \ge 0$, we have $\displaystyle\;a_{N+k} \le \frac{1}{a_N}\frac{1}{(1+\alpha)^k}$. As a result, $$\sum_{n=N+1}^\infty \frac{1}{a_n} \le \frac{1}{a_N}\sum_{k=1}^\infty\frac{1}{(1+\alpha)^k} = \frac{1}{a_N}\frac{\frac{1}{1+\alpha}}{1 - \frac{1}{1+\alpha}} = \frac{1}{a_N\alpha} = \frac{1}{a_N^2} $$ By brute force, we have $$(a_1,a_2,a_3,a_4,a_5,\ldots) = (\frac13,\frac49,\frac{52}{81},\frac{6916}{6561},\frac{93206932}{43046721},\ldots)$$ Since $a_n > 1$ start at $n = 4$, we can take $N = 5$. By above argument, we have:

$$5.2182 \sim \sum_{n=2}^5 \frac{1}{a_n} \le \sum_{n=2}^{2008} \frac{1}{a_n} < \sum_{n=2}^\infty \frac{1}{a_n} \le \sum_{n=2}^5 \frac{1}{a_n} + \frac{1}{a_5^2} \sim 5.4315$$ So the answer is $5$.