# Recurrence relation

Printable View

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

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

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

but how is this formally derived?

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

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

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

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

Prove this by induction on n.
• Oct 15th 2011, 11:27 PM
chisigma
Re: Recurrence relation
Quote:

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

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

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

but how is this formally derived?

Can someone offer a quick insight?

The difference equation...

$\displaystyle \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...

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

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

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

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$