Expressing $\sqrt{2}$ as closed form expression based on recurrence.

Question

Knowing that $\sqrt{2}$ can be calculated using this recursive formula with $a_0 = 1$: $$a_{n+1} = \frac{a_n}{2} + \frac{1}{a_n}$$How do i find a closed form expression that satisfies the above recurrence relation? What i mean is, finding a sequence that depends on $n$ and is based on this recurrence relation.

Answer 1

It is possible to work out a closed form expression for the recurrence relation you have: $$a_{n+1} = \frac{a_n}{2} + \frac{1}{a_n}$$ In particular, if you impose the initial condition $a_0 = 1$, one has

$$a_n = \sqrt{2}\frac{(1+\sqrt{2})^{2^n} + (1-\sqrt{2})^{2^n}}{ (1+\sqrt{2})^{2^n} - (1-\sqrt{2})^{2^n}} = \frac{ \sum\limits_{r=0}^{2^{n-1}}\binom{2^n}{2r}2^r }{ \sum\limits_{r=0}^{2^{n-1}-1}\binom{2^n}{2r+1}2^r } \quad\text{ for } n > 0 $$

The key is construct an auxiliary sequence $b_n = \frac{a_n - \sqrt{2}}{a_n + \sqrt{2}}$ and show that it satisfies a much simpler recurrence relation $b_{n+1} = b_n^2$. The actual derivation of above closed form of $a_n$ will be left as an exercise.

Answer 2

There is no need to find an expression for $a_n$ in terms of $n$. The usual argument is:

• $(a_n)$ converges. This is the hard part.

• If $L=\lim a_n$, then $L^2=2$. This is easy.