# 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!

• Is there an initial condition? Nov 7 '17 at 14:07
• Does the initial condition matter? I intend on using u=2 as initial condition, but surely one can write out a formula for any initial condition $u_{0}$
– user489116
Nov 7 '17 at 14:32
• For nonlinear recurrences the initial condition has a dramatic effect on the behavior of the sequence. Nov 7 '17 at 15:40
• Sure ( I mean I didn't know this,but I trust you :) ). But for now I do not care so much about the initial condition, rather about how to solve the problem. Can you help me in that respect or refer me to helpful material?
– user489116
Nov 7 '17 at 15:54
• Maybe multiplying by some function is helpful? Is there a convenient way to rewrite the relation? Am I on the right track? Also can one see before hand whether or not a certain relation even has an explicit formula?
– user489116
Nov 7 '17 at 15:58

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

• Thanks for the reply! I am still thinking about your approach... I (hopefully) will understand it in a minute :D. (Btw my problem derives from considering the equation $x^2-2=0$ and the Newton-Raphson method)
– user489116
Nov 7 '17 at 16:48
• OK I understand your approach now (I think). But this approach already assumes the solution in a sense. Assuming we didn't already know that root 2 is the solution, how could we solve the relation? (Generating functions?) Further is there a good general way to approach this kind of recurrence relation? Anyhow thanks for your answer, it was very helpful!
– user489116
Nov 7 '17 at 17:00

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.

• Ah, OK. You mentioned clever tricks and transformations- Are there any standard tricks/transformations that would help me? Also how would one proceed with a recurrence relation with a fraction with square denominator in $u_n$? Thanks so far!
– user489116
Nov 8 '17 at 16:53