Explanation and Examples

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 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 x3x3 is the same as x2 × x. We can continue in this fashion up to x= 1. What can we say in general then? Recursively,

xn = x × (xn - 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(- 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

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(- 1) + 12f(- 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

aA1an-1 + A2a- 2 + ... + Ajan - j
with f(t1) = u1f(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

Sum of solutions

This theorem says that:

If f(n) and g(n) are both solutions to a linear recurrence relation aAa- 1 Ba- 2, their sum is a solution also.

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

f(n) - Af(- 1) - Bf(- 2) = 0
g(n) - Ag(- 1) - Bg(- 2) = 0

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

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

On expanding out, we have

f(n) - Af(- 1) - Bf(n - 2) + g(n) - Ag(- 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, an-Aa- 1 Ba- 2 = 0, with supplied initial conditions.

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

xAx = 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

γrAγr- 1 Bγr- 2 = 0

then factor out by γr- 2, the term farthest on the right

γr- 2(rAr B) = 0

and we know that r isn't zero, so r- 2 can never be zero. So rAr B must be zero, and so γrn, with r a solution of rAr = 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(- 1) + B * F(- 2)

We solve : x2 = 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(- 1) + B * F(- 2)

Let's check: Does rn = r- 1 + *r- 2 ? Divide both sides by r- 2 and you get r2 = r + B, which must be true because r is a solution to x2 = Ax + B

Why does γ * rn also satisfy the recurrence relation? If F( n)=rn is a solution, that is, r*r- 1 *r- 2 = 0, then certainly F(n) = γrn is a solution since γr* γr- 1 * γr- 2 = γ( rr- 1 r- 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(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 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(- 1) + 2a(- 2)

The characteristic equation of this recurrence relation is

r- 2 = 0 from above, as A = 1 and B = 2

i.e. (- 2)(+ 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.

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