# Recurrence relation

• Oct 15th 2011, 11:02 AM
Dinkydoe
Recurrence relation
Hee, I got a really simple recurrence relation:

$\lambda_n=2-\frac{1}{\lambda_{n-1}}$ with $\lambda_1=2$.

Calculating a few values we easily notice $\lambda_n = \frac{n+1}{n}$,

but how is this formally derived?

Can someone offer a quick insight?
• Oct 15th 2011, 12:19 PM
Moo
Re: Recurrence relation
Hello,

I guess you're a little wrong with your few values, for example, I get $\lambda_3=-1$
• Oct 15th 2011, 12:39 PM
Dinkydoe
Re: Recurrence relation
Yes, that's quite annoying...

It shouldve been $\lambda_n=2-\frac{1}{\lambda_{n-1}}$
• Oct 15th 2011, 01:30 PM
emakarov
Re: Recurrence relation
Quote:

Originally Posted by Dinkydoe
$\lambda_n = \frac{n+1}{n}$

Prove this by induction on n.
• Oct 16th 2011, 12:27 AM
chisigma
Re: Recurrence relation
Quote:

Originally Posted by Dinkydoe
Hee, I got a really simple recurrence relation:

$\lambda_n=2-\frac{1}{\lambda_{n-1}}$ with $\lambda_1=2$.

Calculating a few values we easily notice $\lambda_n = \frac{n+1}{n}$,

but how is this formally derived?

Can someone offer a quick insight?

The difference equation...

$\lambda_{n+1}= 2-\frac{1}{\lambda_{n}}\ ,\ \lambda_{0}=2$ (1)

... is non-linear and in most cases like that an ad hoc solving procedure has to be found. In this particular case it is easy to see that the solution is a continued fraction...

$\lambda_{n}= a_{0} - \frac{1}{a_{1}-\frac{1}{a_{2}-...-\frac{1}{a_{n}}}}$ (2)

... where $a_{0}=a_{1}= ... = a_{n}=2$. Now if You use the standard algorithm to write the rational number $\frac{n+1}{n}$ in term of continued fraction You obtain exactly the expression (2) so that is...

$\lambda_{n}=\frac{n+1}{n}$ (3)

Kind regards

$\chi$ $\sigma$