Discrete Mathematics/Recursion

From Wikibooks, open books for an open world
Jump to: navigation, search

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

What is recursion?[edit]

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[edit]

When we calculate an exponent, say x3, we multiply x by itself three times. If we have x5, 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 x4 for example, is the same as x3 × x. But what is x3? x3 is the same as x2 × x. We can continue in this fashion up to x0=1. What can we say in general then? Recursively,

xn = x × (xn-1)

with the fact that

x0=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[edit]

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(x)= a.f(n-1)
  by putting these samaller values we get the same answer.

Recurrence relations[edit]

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 2x, 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[edit]

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 an 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

an=A1an-1 + A2an-2 + ... + Ajan-j
with f(t1)=u1, f(t2)=u2, ..., f(tj)=uj 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[edit]

This theorem says that:

If f(n) and g(n) are both solutions to a linear recurrence relation an=Aan-1+Ban-2, their sum is a solution also.

This is true, since if we rearrange the recurrence to have an-Aan-1-Ban-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[edit]

The next theorem states that:

Say we have a second-order linear recurrence relation, an-Aan-1-Ban-2=0, with supplied initial conditions.


Then αrn is a solution to the recurrence, where r is a solution of the quadratic equation

x2-Ax-B=0

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

We substitute αrn (r not zero) into the recurrence to get

αrn-Aαrn-1-Bαrn-2=0

then factor out by αrn-2, the term farthest on the right

αrn-2(r2-Ar-B)=0

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

Why does a*rn also satisfy the recurrence relation? If F(n)is a solution to the recurrence relation, so is F(n)+ F(n), based on the "Sum of Solutions" theorem above. One can then take that sum, 2*F(n), and add another F(n) to get 3*F(n), and it will still satisfy the recurrence (and so on...). Thus any whole number multiple of F(n), such as a*F(n) will satisfy the recurrence relation (a can also be any fraction and probably any real number at all, but I'm too lazy to adapt the current explanation). Because rn satisfies the recurrence, so does a*rn.



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 the general solution is C(rn)+D(sn) 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 equtions which we can (hopefully) solve.

Example[edit]

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

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