# Show that $45<x_{1000}<45.1$

If $$x_0 = 5$$ and $$x_{n+1} = x_n + \frac {1}{x_n},$$ show that

$$45

This problem is taken from the list submitted for the $$1975$$ Canadian Mathematics Olympiad (but not used on the actual exam).

SOURCE : CRUX(Page Number 3 ; Question Number 162)

I tried writing out the first few terms :

$$x_1 = 5+ \frac{1}{5}$$

$$x_2 = \big(5+\frac{1}{5}\big) + \big(5+\frac{1}{5}\big)^{-1} = \frac{x_0^2 + 1}{x_0} + \frac{x_0}{x_0^2 + 1} = \frac{(x_0^2 + 1)^2+x_0^2}{x_0(x_0^2+1)}$$

$$x_3 = \frac{(x_0^2 + 1)^2+x_0^2}{x_0(x_0^2+1)} + \frac{x_0(x_0^2+1)}{(x_0^2 + 1)^2+x_0^2} = Messy$$

I tried a lot but could not find any general formula for the $$n$$th term. Does there even exist any?

Also it is clear that $$\big(x_n + \frac{1}{x_n}\big)$$ is an increasing function. So I think sequence diverges, but how can the $$1000th$$ term be calculated or aprroximated?

Any help would be gratefully acknowledged :).

• Do you mean $x_{n}+\frac{1}{x_{n}}$ or $x_{n}+\frac{1}{n}$? Commented Jan 28, 2017 at 13:26
• @S.C.B. OH sorry...just a typo .. edit on its way...
– user399078
Commented Jan 28, 2017 at 13:30
• This sounds like something you can probably do using an approximation by the continuous version of this problem, i.e. $f'(x)=\frac{1}{f(x)}$. A first approximation would be $\sqrt{2\cdot 1000 + 5} \sim 44.78$, so this may still need a little bit of tweaking. Commented Jan 28, 2017 at 13:39
• @Nirbhay, I love your $=Messy$ evaluation. Nice touch. Commented Jan 28, 2017 at 18:52

CLAIM

For all $$n \ge 1$$, then let us prove $$\sqrt{2n+25+\frac{1+\ln (n-1)}{2}} > x_{n} > \sqrt{2n+25}$$ PROOF

This holds for $$n=1$$. This can be checked numerically.

Assume this holds for $$n=m$$. Then, we can prove the left hand inequality through induction as $$x_{m+1}^2=x_{m}^2+2+\frac{1}{x_{m}^2}>2n+27 \implies x_{m+1} > \sqrt{2n+27}$$ Now from $$x_{m+1}^2-x_{m}^2=2+\frac{1}{x_{m}^2}$$, we now have $$x_{m+1}^2-x_{0}^2=\sum_{n=0}^{m-1} \frac{1}{x_{n}^2}<\sum_{n=0}^{m-1}\frac{1}{2n+25}<\sum_{n=1}^{m}\frac{1}{2n}\le \frac{1+\ln m}{2} \tag{1}$$ Thus, our claim is proved. The desired result follows from our Claim.

$$(1)$$: See here

NOTE: My original answer was wrong, which is the reason for this rather large edit.

• Amazing answer. What was the intuition behind the "claim" ??
– user399078
Commented Jan 28, 2017 at 13:48
• @Nirbhay I have often been thinking about radicals, so $x_{n}+\frac{1}{x_n}$ felt like it could be expressed using radicals. Commented Jan 28, 2017 at 13:50
• I would also like to know how one comes up with this kind of bound for a recursive sequence. Commented Jan 28, 2017 at 13:50
• @user1892304 Intuition :) I can't explain it completely myself. Commented Jan 28, 2017 at 13:52
• @S.C.B. You did the question as if you knew its official solution. That's crazy !!!
– user399078
Commented Jan 28, 2017 at 13:55

$x_n^2-x_{n-1}^2=2+\frac{1}{x_{n-1}^2}$ for $n\geq1$.

Thus, $$x_{1000}^2=2\cdot1000+25+\frac{1}{x_0^2}+\frac{1}{x_1^2}+...+\frac{1}{x_{999}^2}>2025$$ and $$x_{1000}^2=2\cdot1000+25+\frac{1}{x_0^2}+\frac{1}{x_1^2}+...+\frac{1}{x_{999}^2}<2025+\frac{100}{x_0^2}+\frac{900}{x_{100}^2}<$$ $$<2025+4+\frac{900}{225}=2033<45.1^2$$

Because $x_{100}^2>225$.