Recursive Equations

Definition

Recursion is a method of defining something (usually a sequence or function) in terms of previously defined values .

A sequence a_n \forall {n \ge 0} is said to be a recursive equation , IF a_n is dependant on any number of previous terms of the sequence . For eg. a_n = a_{n-1} + a_{n-2} (Fibonacci!!).

In this post I shall deal with Linear recurences.

Motive

To express a_n in a closed form dependent solely on n and not any previous term of the sequence(linear).

First let us derive the n^{th} term of a Fibonnacci Sequence.

In a Fibonacci sequence the first term is a_1 = 1.

Set x = 1\cdot x

x^2 = 1\cdot x + 1

and equivalently,

x^{3} = x^{2} + x

= 2\cdot x + 1

Thus,

x^2 = a_2\cdot x + C_2

x^3 = a_3\cdot x + C_3

and inductively it could be proved that ,

x^n = a_n \cdot x + C_n

Where C_i is a constant for any i in the i^{th}  equation.

Since the n-1 equations are equivalent to the initial quadratic equation , the root(s) of the quadratic equation are also the roots of all the equations.

Thus solving the quadratic equation – x^2 = 1\cdot x + 1 we get the roots to be – \frac{1+\sqrt{5}}{2} and \frac{1-\sqrt{5}}{2}

Let the roots be \alpha and \beta, Therefore,

{\alpha}^n = a_n \cdot \alpha + C_n

and also,

$latex {\beta}^n = a_n \cdot \beta + C_n$ 

subtracting we get ,

a_n = \frac{{\alpha}^n - {\beta}^n}{\alpha - \beta}

Hence substituting the values of \alpha and \beta we get ,

a_n = \frac{1}{\sqrt{5}} \cdot \left(\frac{1+\sqrt{5}}{2}^n - \frac{1-\sqrt{5}}{2}^n\right)

What is the idea behind setting the first quadratic equation?.. Well , this illustrates the idea –

If a_n = pa_{n-1} +qa_{n-2}

Then set the quadratic seeing the coefficients ,

By mathematical induction , we can show that all the (n-1) equations are linear in x.

Thus, by strong induction assume that the co-efficient of x in the (n-i) th equation is the corresponding term of the recursive sequence then,similarly we can prove it for n using induction again! Thus the validity of the equations.

So , does this mean that for any equation we get this formula  – a_n = \frac{{\alpha}^n - {\beta}^n}{\alpha - \beta} ?

Well the Answer is No.

The idea behind this is that x^{i} contains a_i x’s . Thus x containing only ONE x forces a_1 = 1. But all recursive equations need not start with 1 … thus.. we either have to modify our idea or construct a whole new idea rejecting this .

The modification… is possible.

The initial quadratic shall remain as its contruction did not depend on the the starting terms but their co-efficients..

Thus \alpha and \beta remain..

now, we will make a slight change in the formula..

a_n = Z \cdot {\alpha}^n + X \cdot {\beta}^n

This could be got from the already existing idea.

Since we know \alpha and \beta and the starting terms , we can find Z and X and we will thus have expressed a_n as desired.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: