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³, we multiply x by itself three times. If we have x⁵, 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⁴ for example, is the same as x³ × x. But what is x³? x³ is the same as x² × x. We can continue in this fashion up to x⁰=1. What can we say in general then? Recursively,

xⁿ = x × (x^n-1)

with the fact that

x⁰=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)=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₁a_n-1 + A₂a_n-2 + ... + A_ja_n-j

with f(t₁)=u₁, f(t₂)=u₂, ..., 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ⁿ is a solution to the recurrence, where r is a solution of the quadratic equation

x²-Ax-B=0

which we call the characteristic equation.
We guess (it doesn't matter why, accept it for now) that γrⁿ may be a solution. We can prove that this is a solution IF (and only if) it solves the characteristic equation ;

We substitute γrⁿ (r not zero) into the recurrence to get

γrⁿ-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²-Ar-B)=0

and we know that r isn't zero, so r^n-2 can never be zero. So r²-Ar-B must be zero, and so γrⁿ, with r a solution of r²-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² = 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ⁿ that satisfies F(n) = A * F(n-1) + B * F(n-2)
Let's check: Does rⁿ = A*r^n-1 + B*r^n-2 ? Divide both sides by r^n-2 and you get r² = A*r + B, which must be true because r is a solution to x² = A* x + B

Why does γ*rⁿ also satisfy the recurrence relation? If F(n)=rⁿ is a solution, that is, rⁿ-A*r^n-1-B*r^n-2=0, then certainly F(n)=γrⁿ is a solution since γrⁿ-A*γr^n-1-B*γr^n-2=γ(rⁿ-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ⁿ)+D(sⁿ) 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²-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ⁿ)+D(-1)ⁿ.

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¹)+D(-1)¹
2 = C(2²)+D(-1)²
Solving these two equations yields: C = 1/3 , D = 2/3, so the solution is 1/3*(2ⁿ)+2/3*(-1)ⁿ.