**Definition**

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

A sequence is said to be a * recursive equation *,

*IF*is dependant on any number of previous terms of the sequence . For eg. (Fibonacci!!).

In this post I shall deal with Linear recurences.

**Motive**

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

First let us derive the term of a Fibonnacci Sequence.

In a Fibonacci sequence the first term is .

Set

and equivalently,

Thus,

and inductively it could be proved that ,

Where is a constant for any in the equation.

Since the 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 – we get the roots to be – and

Let the roots be and , Therefore,

and also,

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

subtracting we get ,

Hence substituting the values of and we get ,

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

If

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 – ?

Well the Answer is No.

The idea behind this is that contains x’s . Thus containing only ONE forces . 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 and remain..

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

This could be got from the already existing idea.

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