# Discrete Mathematics/Recursion

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

## What is Recursion?

editRecursion, 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

editWhen 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

editReducing 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

editIn 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* also know as x'to sup with value 0 and so on.

### Linear recurrence relations

editWe 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

edit##### Sum of solutions

editThis 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

editThe 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 which we can (hopefully) solve.

#### Example

editLet'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}.