2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ I suspect you want to find an $a_n$ which converges to $\sqrt{2}$ and satisfies the above recursion relation? That seemed clear from the question to me, but the answers below suggest perhaps that you should edit your question to make that explicit. $\endgroup$
    – gj255
    Dec 12 '17 at 11:02
  • 1
    $\begingroup$ @g yea - I looked at the answers and didn't read the question that carefully. Deleted my answer. Early in the morning. More coffee! $\endgroup$ Dec 12 '17 at 11:51
8
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ (+1) It might be worth mentioning that the ratios $$ \sqrt{2}\,\frac{(1+\sqrt{2})^m+(1-\sqrt{2})^m}{(1+\sqrt{2})^m-(1-\sqrt{2})^m}$$ give the convergents of the continued fraction $$\sqrt{2}=[1;2,2,2,2,\ldots].$$ $\endgroup$ Dec 12 '17 at 17:59
  • $\begingroup$ @JackD'Aurizio interesting, I don't know about that. $\endgroup$ Dec 12 '17 at 18:14
  • $\begingroup$ This is relevant, too: en.wikipedia.org/wiki/Pell_number $\endgroup$ Dec 12 '17 at 18:20
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.