Recurrence Relations Tutor

A recurrence relation is an equation with the intention of recursively describes a series: each term of the series is defined as a function of the above terms. The difference equations refer to a particular type of recurrence relation. Note but the "difference equation" is commonly used to refer to any recurrence relation. Tutoring is method of teaching. Tutoring is to teaching a single student or a group of students.

An example of a recurrence relation is the logistic map:

x n + 1 = r x n (1-xn)

Recurrence relations tutor – Examples:

Recurrence relations tutor  - Example 1:

Find the limiting ratio `lim_(n->oo) (x_{n+1})/(x_n)` , for the recurrence relation `x_n = x_{n-1}+x_{n-2}.`

Solution:

We find what the limit must be, assuming that it exists.

L = `\lim_{n\rightarrow\infty} \frac{x_{n+1}}{x_n} = \lim_{n\rightarrow\infty} \frac{x_n+x_{n-1}}{x_n} = 1 + \lim_{n\rightarrow\infty} \frac{x_{n-1}}{x_n} = 1+L^{-1}`

L = 1 + `L^{-1}`

`L^2=L+1`

`L^2-L-1=0`

L = `\frac{1 \pm \sqrt{ 5 }}{2}` , via the quadratic formula.
Recurrence relations tutor - Example 2:

Let
`x_n = { x_(n-1) + x_(n-2)`     if n > 1
`x_(1) epsi N`                       if n = 1
`x_(0) epsi N`                       if n = 0
0                                if n < 0

Show that `x_n = x_{1}F_{n-1} + x_{0}F_{n-2} \,\! "where" F_n\!` is the n-th Fibonacci number   (F0 = F1 = 1)

Solution:

Using the principle of induction we have:

BASIS: n=`2 \Rightarrow x_2 = x_1 + x_0 = x_{1}F_{1} + x_{0}F_{0}\!`

INDUCTIVE STEP: We have `x_{n-2} = x_{1}F_{n-3} + x_{0}F_{n-4}\,\! and x_{n-1} = x_{1}F_{n-2} + x_{0}F_{n-3}\!`

By definition we have:


`x_{n} := x_{n-1} + x_{n-2} = x_{1}F_{n-2} + x_{0}F_{n-3} + x_{1}F_{n-3} + x_{0}F_{n-4}`

`= x_{1}\(F_{n-2} + F_{n-3}\) + x_{0}\(F_{n-3}+F_{n-4}\) = x_{1}F_{n-1} + x_{0}F_{n-2} \mbox{ } \!`

Recurrence relations tutor – More Problems:

Recurrence relations tutor - Example 1:

Let  .

`x_n := x_{n-1}*x_{n-2}`  if n>1
`x_1`                        if n=1
`x_0`                        if n=0
0                           if n<0 p="">
Show that `x_n = x_{1}^{F_{n-1}}*x_{2}^{F_{n-2}} \!` where `F_n\!` is the n-th Fibonacci number   (F0 = F1 = 1 and F(n < 0) = 0)

Solution:

As before: induction is da way!

Between, if you have problem on these topics T Score Distribution Table, please browse expert math related websites for more help on fraction of a set worksheet.

BASIS: For n = 2! we have `x_2 = x_1^{F_1}*x_0^{F_{0}} = x_1*x_0 \!`

INDUCTIVE STEP: `x_{n-2} = x_1^{F_{n-3}}*x_0^{F_{n-4}} \,\! and x_{n-1} = x_1^{F_{n-2}}*x_0^{F_{n-3}} \!` and

so `x_n = x_{n-1}*x_{n-2} = (x_1^{F_{n-2}}*x_0^{F_{n-3}}) * (x_1^{F_{n-3}}*x_0^{F_{n-4}}) `

= `x_1^{F_{n-2}+F_{n-3}}*x_0^{F_{n-3}+F_{n-4}}`

= `x_{1}^{F_{n-1}}*x_{2}^{F_{n-2}} !`