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.

user288409
  • 11
  • Jsut a bit nitpicky, but I believe you should write $$x_n = x_0 + \sum_{i=1}^{n-1} \frac{1}{x_i}$$ As for the line $2x_0 = x_0 + \sum$, it is unlikely that we will have equality in this situation. – Joel Jun 05 '14 at 19:03
  • You probably won't find a closed-form expression of $x_i$, let alone the sum, although there is a nice closed form expression for the recursion $y_i=\frac{1}{2}\left(y_{i-1}+\frac{1}{y_{i-1}}\right)$ involving $\tanh\left( 2^i \tanh^{-1}(y_0) \right)$, which is the guess sequence of Newton's algorithm for $\sqrt{1}$. – Mark Fischler Jun 05 '14 at 19:41
  • By brute force computation, I find $n = \left\lfloor \frac32 x_0^2\right\rfloor$ for positive integer $x_0 \le 1000$. – achille hui Jun 05 '14 at 20:43

2 Answers2

1

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$.

achille hui
  • 122,701
0

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.

Calvin Lin
  • 68,864