# 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}$ ?

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.