How do I find $\sum_{i=1}^n\frac{1}{x_i}$ where $x_i = x_{i-1} + \frac{1}{x_{i-1}}$ I have a recurrence: $x_n = x_{n-1} + \frac{1}{X_{n-1}}$. I need the value of n for which $x_n$ IS CLOSEST TO $2*x_0$, where $x_0$ is a positive integer.
I tried the following:
$x_1 = x_0 + \frac{1}{x_0}$
$x_2 = x_1 + \frac{1}{x_1}$
..
$x_n = x_{n-1} + \frac{1}{x_{n-1}}$
Adding, $x_n = x_0 + \sum_{i=1}^n\frac{1}{x_i}$
or, $2x_0 = x_0 + \sum_{i=1}^n\frac{1}{x_i}$
or, $x_0 = \sum_{i=1}^n\frac{1}{x_i}$
I might be horribly wrong in my approach, because I lack the required skills.
 A: Let $x_0 = m \in \mathbb{Z}_{+}$. By brute force computation, we know for $m \le 1000$, the optimal $n$ which minimize $|x_n - 2x_0|$ is given by the formula
$$N_{optimal}(m) = \left\lfloor \frac{3m^2}{2} \right\rfloor\tag{*1}$$
Let $\displaystyle\;N = \left\lfloor \frac{3m^2}{2} \right\rfloor\;$ and consider the case $m \ge 1000$. Notice
$$x_n = x_{n-1} + \frac{1}{x_{n-1}} \quad\implies\quad
x_n^2 - x_{n-1}^2 = 2 + \frac{1}{x_{n-1}^2}$$
This implies
$$x_n^2 = m^2 + 2n + \sum_{k=0}^{n-1} \frac{1}{x_k^2}\tag{*2}$$
and leads to a trivial lower bound $x_n^2 \ge m^2 + 2n$. Substitute this into $(*2)$, 
we obtain an upper bound
$$x_n^2 \le m^2 + 2n + \sum_{k=0}^{n-1}\frac{1}{m^2+2k}$$
Since $\displaystyle\;\frac{1}{x}\;$ is a convex function, we have
$$\frac{1}{m^2+2k} \le \frac12 \int_{m^2+2k-1}^{m^2+2k+1} \frac{dx}{x}$$
and hence
$$x_n^2 \le m^2 + 2n + \frac12\int_{m^2-1}^{m^2+2n-1} \frac{dx}{x}
= m^2 + 2n + \frac12 \log\left(\frac{m^2+2n-1}{m^2-1}\right)\tag{*3}$$
For $n \le N$, we can bound the logarithm term in $(*3)$ from above:
$$\frac12 \log\left(\frac{m^2+2n-1}{m^2-1}\right)
\le \frac12 \log\left(\frac{m^2+2N-1}{m^2-1}\right)
\le \frac12 \log\left(\frac{4m^2-1}{m^2-1}\right)\\
\approx \log 2 + O\left(\frac{1}{m^2}\right) < 1$$
This gives us a simplified upper bound 
$\displaystyle\;x_n^2 \le m^2 + 2n + 1\;$ for $n \le N$. Plug this new upper bound into $(*2)$ for $n = N$, we can improve the lower bound of $x_N^2$ to
$$x_N^2 
\ge m^2 + 2N + \sum_{k=0}^{N-1}\frac{1}{m^2 + 2k + 1}
\ge m^2 + 2N + \frac12\int_{m^2+1}^{m^2+2N+1}\frac{dx}{x}\\
=  m^2 + 2N + \frac12\log\left(\frac{m^2+2N+1}{m^2+1}\right)\tag{*4}
$$
Combine $(*3)$ and $(*4)$, we obtain
$$x_N^2 = m^2 + 2N + \log 2 + O\left(\frac{1}{m^2}\right)$$
Since $m \ge 1000$, up to $O(10^{-6})$, we get
$$X_N^2 - 4m^2 \;\;\approx_{O(10^{-6})}\;\; \begin{cases} 
\log 2 \sim 0.69,& m \text{ even }\\
\log 2 - 1 \sim - 0.31,&m \text{ odd }
\end{cases}$$
Using the fact $|x_{N+1}^2 - x_N^2|, |x_{N-1}^2 - x_N^2| > 2$, it is obvious the optimal $n$ that minimize $|x_n - 2x_0|$ is once again given by $N$. i.e. the formula $(*1)$ 
actually works for all positive integer $m$.
A: Hint: Square the equation, you get
$$x_i ^2 = x_{i-1}^2 + 2 + \frac{1}{x_{i-1} ^2 } $$
Suppose we want the smallest $n$ such that $x_n \geq 2 x_0 $. Since $ x_i ^2 \geq  x_{i-1} ^2 + 2$, this tells us  that $ n \leq \frac{ 3x_0^2}{2}$.
Now, you need to find a lower bound, to show that $n = \lfloor \frac{ 3x_0^2}{2} \rfloor$ is indeed the answer that we want.
You can read solutions to this question if you need further help.
