## Explanation and Examples

Read this page to get a sense of recursion from a mathematical basis.

In this section we will look at certain mathematical processes which deal with the fundamental property of * recursion* at its core.

#### What is Recursion?

Recursion, simply put, is the process of describing an action in terms of itself. This may seem a bit strange to understand, but once it "clicks" it can be an extremely powerful way of expressing certain ideas.

Let's look at some examples to make things clearer.

##### Exponents

When we calculate an exponent, say *x*^{3}, we multiply *x* by itself three times. If we have *x*^{5}, we multiply *x* by itself five times.

However, if we want a recursive definition of exponents, we need to define the action of taking exponents in terms of itself. So we note that *x*^{4} for example, is the same as *x*^{3} × *x*.
But what is *x*^{3}? *x*^{3} is the same as *x*^{2} × *x*. We can continue in this fashion up to *x*^{0 }= 1. What can we say in general then?
Recursively,

*x*^{n}=*x*× (*x*^{n - 1})

with the fact that

*x*^{0 }= 1

We need the second fact because the definitions fail to make sense if we continue with negative exponents, and we would continue indefinitely!

##### Recursive definitions

Reducing the problem into same problem by smaller inputs. for example

a power n 2 power 4 the recursion(smaller inputs) of this function is = 2.2.2.2.1 for this we declare some recursive definitions a=2 n=4 f(0)=1 f(1)=2 f(2)=2 f(3)=2 f(4)=2 for this recursion we form a formula f(n)= a.f(n-1) by putting these smaller values we get the same answer.

#### Recurrence relations

In mathematics, we can create recursive *functions*, which depend on its previous values to create new ones. We often call these *recurrence relations*.

For example, we can have the function :*f*(*x*) = 2*f*(*x *- 1), with *f*(1) = 1 If we calculate some of *f*'s values, we get

- 1, 2, 4, 8, 16, ...

However, this sequence of numbers *should* look familiar to you! These values are the same as the function 2^{x}, with x = 0, 1, and so on.

What we have done is found a *non-recursive* function with the same values as the *recursive* function. We call this *solving* the recurrence relation.

##### Linear recurrence relations

We will look especially at a certain kind of recurrence relation, known as *linear*.

Here is an example of a linear recurrence relation:

*f*(*x*) = 3*f*(*x*- 1) + 12*f*(*x*- 2), with f(0) = 1 and f(1) = 1

Instead of writing *f*(*x*), we often use the notation *a*_{n} to represent *a*(*n*), but these notations are completely interchangeable.

Note that a linear recurrence relation should always have stopping cases, otherwise we would not be able to calculate *f*(2), for example, since what would *f*(1) be if we did not define it? These stopping cases when we talk about
linear recurrence relations are known as *initial conditions*.

In general, a linear recurrence relation is in the form

*a*_{n }=*A*_{1}*a*_{n-1}+*A*_{2}*a*_{n - 2}+ ... +*A*_{j}*a*_{n - j}

- with
*f*(*t*_{1}) =*u*_{1},*f*(*t*_{2}) =*u*_{2}, ...,*f*(*t*_{j}) =*u*_{j}as initial conditions.

The number *j* is important, and it is known as the *order* of the linear recurrence relation. Note we always need at least *j* initial conditions for the recurrence relation to make sense.

Recall in the previous section we saw that we can find a nonrecursive function (a *solution*) that will take on the same values as the recurrence relation itself. Let's see how we can solve some linear recurrence relations - we can do so in
a very systematic way, but we need to establish a few theorems first.

##### Solving linear recurrence relations

**Sum of solutions**

This theorem says that:

- If
*f*(*n*) and*g*(*n*) are both solutions to a linear recurrence relation*a*_{n }=*Aa*_{n - 1 }+*Ba*_{n - 2}, their sum is a solution also.

This is true, since if we rearrange the recurrence to have *a*_{n }- *Aa*_{n-1}-*Ba*_{n - 2 }= 0 And we know that *f*(*n*) and *g*(*n*)
are solutions, so we have, on substituting into the recurrence

*f*(*n*) -*Af*(*n*- 1) -*Bf*(*n*- 2) = 0

*g*(*n*) -*Ag*(*n*- 1) -*Bg*(*n*- 2) = 0

If we substitute the sum *f*(*n*)+*g*(*n*) into the recurrence, we obtain

- (
*f*(*n*) +*g*(*n*)) -*A*(*f*(*n*- 1) +*g*(*n*- 1)) -*B*((*f*(*n*- 2) +*g*(*n*- 2)) = 0

On expanding out, we have

*f*(*n*) -*Af*(*n*- 1) -*Bf*(n - 2) +*g*(*n*) -*Ag*(*n*- 1) -*Bg*(n - 2)

But using the two facts we established first, this is the same as

- 0 + 0 = 0

So *f*(*n*)+*g*(*n*) is indeed a solution to the recurrence.

**General solution**

The next theorem states that:

- Say we have a second-order linear recurrence relation,
*a*_{n}-*Aa*_{n - 1 }-*Ba*_{n - 2 }= 0, with supplied initial conditions.

Then γ*r*^{n} is a solution to the recurrence, where *r* is a solution of the quadratic equation

*x*^{2 }-*Ax*-*B*= 0

which we call the *characteristic equation*.

We guess (it doesn't matter why, accept it for now) that γ*r*^{n} may be a solution. We can prove that this is a solution IF (and only if) it solves the characteristic equation ;

We substitute γ*r*^{n} (*r* not zero) into the recurrence to get

- γ
*r*^{n }-*A*γ*r*^{n - 1 }-*B*γ*r*^{n - 2 }= 0

then factor out by γ*r*^{n - 2}, the term farthest on the right

- γ
*r*^{n - 2}(*r*^{2 }-*Ar*-*B*) = 0

and we know that *r* isn't zero, so *r*^{n - 2} can never be zero. So *r*^{2 }- *Ar *- *B* must be zero, and so γ*r*^{n},
with *r* a solution of *r*^{2 }- *Ar *- *B *= 0, will indeed be a solution of the linear recurrence. Please note that we can easily generalize this fact to higher-order linear
recurrence relations.

**Where did this come from? Why does it work (beyond a rote proof)? Here's a more intuitive (but less mathematically rigorous) explanation.**

Solving the *characteristic equation* finds a function that satisfies the linear recurrence relation, and conveniently doesn't require the summation of all *n* terms to find the *n*^{th} one.

We want : a function F(*n*) such that F(*n*) = *A* * F(*n *- 1) + *B* * F(*n *- 2)

We solve : *x*^{2} = *A ** *x* + *B*, and call the solution(s) *r*. There can be more than one value of *r*, like in the example below!

We get : a function F(*n*) = *r*^{n} that satisfies F(*n*) = *A* * F(*n *- 1) + *B* * F(*n *- 2)

Let's check: Does *r*^{n} = *A ** *r*^{n - 1} + *B ***r*^{n - 2} ? Divide both sides by *r*^{n - 2} and
you get *r*^{2} = *A ** *r* + *B*, which must be true because *r* is a solution to *x*^{2} = *A** *x* + *B*

**Why does γ * r^{n} also satisfy the recurrence relation? **If F(

*n*)=

*r*

^{n}is a solution, that is,

*r*

^{n }-

*A**

*r*

^{n - 1 }-

*B**

*r*

^{n - 2 }= 0, then certainly F(

*n*) = γ

*r*

^{n}is a solution since γ

*r*

^{n }-

*A** γ

*r*

^{n - 1 }-

*B** γ

*r*

^{n - 2 }= γ(

*r*

^{n }-

*A**

*r*

^{n - 1 }-

*B**

*r*

^{n - 2}) = 0.

Because we have a second order recurrence, the general solution is the sum of two solutions, corresponding to the two roots of the characteristic equation. Say these are r and s. The general solution is C(r^{n}) + D(s^{n}) where C, D are
some constants. We find them using the two (there must be two so that we can find C and D) starting values of the relation. Substituting these into the general solution will give two equations that we can (hopefully) solve.

**Example**

Let's work through an example to see how we can use the above theorems to solve linear recurrence relations. Examine the function *a*(*n*) given here

*a*(*n*) =*a*(*n*- 1) + 2*a*(*n*- 2)

The characteristic equation of this recurrence relation is

*r*^{2 }-*r*- 2 = 0 from above, as A = 1 and B = 2

i.e. (*r *- 2)(*r *+ 1) = 0 which has roots 2, -1.

So the general solution is C(2^{n}) + D(-1)^{n}.

To find C and D for this specific case, we need two starting values, let's say *a*(*1*) = 0 and *a*(*2*) = 2. These give a system of two equations

0 = C(2^{1}) + D(-1)^{1}

2 = C(2^{2}) + D(-1)^{2}

Solving these two equations yields: C = 1/3 , D = 2/3, so the solution is 1/3 * (2^{n}) + 2/3 * (-1)^{n}.

Source: Wikibooks, https://en.wikibooks.org/wiki/Discrete_Mathematics/Recursion

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 License.