Explicit formula for recurrence relation by generating function

Question

My question concerns the following recurrence relation:

$u_n= \frac{u_{n-1}}{2}+\frac{1}{u_{n-1}} $

and how to find an explicit formula for this expression using generating functions (GF). I so far have only had experience with linear recurrence relations and GFs and can't see how to start on this problem. Any help would be appreciated!

Answer 1

Well, you can't start with the initial condition $u_0=0$ because you get a singularity in the second term. Other initial conditions, however, are valid and approach to the steady state $u_{\infty}=\sqrt{2}$. To see this, the trick is to rewrite the equation as:

$$ \frac{u_n-\sqrt{2}}{u_n+\sqrt{2}}= \bigg(\frac{u_{n-1}-\sqrt{2}}{u_{n-1}+\sqrt{2}}\bigg)^2 $$

(Check that this is in fact true) Therefore you can easily see that as we iterate:

$$ \frac{u_n-\sqrt{2}}{u_n+\sqrt{2}}= \bigg(\frac{u_{n-2}-\sqrt{2}}{u_{n-2}+\sqrt{2}}\bigg)^4 = \bigg(\frac{u_{n-3}-\sqrt{2}}{u_{n-3}+\sqrt{2}}\bigg)^8 = \dots = \bigg(\frac{u_{0}-\sqrt{2}}{u_{0}+\sqrt{2}}\bigg)^{2^{n}}$$

Solving for $u_n$ gives:

$$u_n = \sqrt{2}\bigg(\frac{1+\big(\frac{u_0-\sqrt{2}}{u_0+\sqrt{2}}\big)^{2^n}}{1-\big(\frac{u_0-\sqrt{2}}{u_0+\sqrt{2}}\big)^{2^n}}\bigg) \longrightarrow \sqrt{2} \text{ as } n\to\infty \text{ for }u_{0}\neq 0 $$

From the closed form solution we see that if $u_0=0$ the recurrence diverges. In fact, for an arbitrary number $k$, the recurrence relation:

$$u_{n}=\frac{1}{2}\bigg(u_{n-1}+\frac{k}{u_{n-1}}\bigg)$$ gives as an asymptotic solution the square root $\sqrt{k}$, and the closed form solution can be found in the same way as I did for $\sqrt{2}$.

Answer 2

I write as an answer as my comment was too long:

Well you can do the same trick with an arbitrary number $a$ and write $\frac{u_n-a}{u_{n}+a}$ and you will find that to complete the squares $a$ must be $\sqrt{2}$. On the other hand, the stationary solution of the recurrence can be found by considering the fixed points of the system $$u_n=\frac{u_n}{2}+\frac{1}{u_n}$$ and solve for $u_n$, finding $u_n=\pm\sqrt{2}$. In general, for nonlinear recurrence relations the explicit closed form solution is very difficult to find, often impossible. In this case you expose, for example, changing the $+$ sign to $-$ gives chaotic solutions with no explicit closed form formula. As far as I know you have to do the trick with a clever transformation to turn the equation in a simplified form.