Explicit formula for recurrence relation by generating function 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! 
 A: 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}$.
A: 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.
