Recursive Sum of Previous Term and its Inverse

216 Views Asked by At

Can anyone help me with finding a closed form for $F_n$ where $$F_0=x_0$$ $$F_{n+1}=F_n+\frac{1}{F_n}=\frac{F_n^2+1}{F_n}$$ I could imagine this already having been done, in which case I'd appreciate a reference to it. I've tried looking at some of the first terms, but I can't make any sense of them. Thanks for any advice!

(Context: I am making a game where a variable $x$ that starts at $x_0$ changes in this fashion each frame, $F_n$ being the $n$-th frame, this isn't a homework problem.)

1

There are 1 best solutions below

1
On BEST ANSWER

(This was too long for a comment). Suppose $$F_n = \frac{a}b + \frac{b}a$$ where $a,b$ are polynomials in $F_0 = x.$ Then we can easily prove that $$F_{n+1} = \frac{a^2+b^2}{ab} + \frac{ab}{a^2+b^2}.$$ Therefore, the problem boils down the solving the coupled recurrences $$a_n = a_{n-1} b_{n-1}$$ $$b_n = a_{n-1}^2 + b_{n-1}^2$$ where $a_n, b_n$ are polynomials and the initial conditions are $a_1 = 1, b_1 = x.$ Solving any non linear recurrence is practically hopeless (for example, the Mandelbrot set has a non linear recurrence which leads to chaotic behavior) although there maybe some tricks about this particular problem.