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

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

## 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)=2f(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

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)=3f(x-1)+12f(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 nth 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

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)+2a(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$.