This means that the next number is equal to the two times the previous number plus three.  Let's say the first number, a(0), is equal to 0.

If that is the case, the next number, a(1) is equal to 2 times a(0), plus 3.  Since a(0) = 0, we have:

In the same way, the next number is,

This is called a recursive relationship, where a number depends upon the previous numbers.  The question is, how do we figure out the 100th number, without figuring out the previous 99?  If that number isn't big enough, how do you figure out the 1,000,000th number, without figuring out the previous 999,999 recursive numbers?

To solve this first-order recurrence relationship, we will assume two things.  First we will drop the +3 for now because that is the non-homogenous part of the equation, we'll take care of that later.  Next, we'll assume that:

Where c and r are constants that we will solve.  Plugging this into the original equation, we have:

If we divide both sides of the equation by we have:

This is called the characteristic equation.  Now that we know what r is, we can substitute this value into the original equation to get the following:

This is our homogenous solution.  The answer to every problem is always the homogenous solution plus the particular solution.  The particular solution is the extra stuff, in this example the +3.  To solve the particular solution we must substitute a general form of the order into a(n).  Since +3 is a constant, we substitute a constant in for a(n).  For example, if the extra part of the problem was 4^n, we would substitute in B*4^n, and if the extra part was simply not present or zero, the particular solution would be nothing.

Plugging this into the original equation, we have the particular solution to the problem:

Since the solution is always the homogenous plus the particular:

We have a pseudo final answer of:

We didn't solve for c, the homogenous constant.  This is always the last step.  Since we figured out a(0), a(1), and a(2), we can plug any of those into this equation to solve for c.  It's a good idea to keep things as simple as possible, so letting n=0 and plugging in a(0)=0, we have:

Our final solution is below!

This formula gives us answers for any n that we plug in!  Below is a graph of the solution.

That was easy.  Now let's solve a rather famous recurrence relation, called the Fibonacci sequence!  The Fibonacci numbers are defined as the sum of the two previous numbers.  This can be described in two different ways, either approach is correct and yields the same result.

This is called a second-order recurrence relationship.  Second order means that it relies on the previous number, and the previous's-previous number.  The Fibonacci numbers progress as 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, etc. 

To solve this problem we will use the exact same approach as solving first-order recurrence relationships.  We begin by substituting in for F(n).

Dividing this equation by gives us the characteristic equation:

Finally, r can be solved for, yielding two numbers.

We can substitute these two values for r into a homogenous solution.  Since we have two parts to the homogenous solution, we need two constants to solve for: c and d.

Now the particular solution... wait.. there isn't any extra to the equation, so we don't need to find a particular solution... there isn't one!  Now, we solve for c and d.  If we let n=0 and n=1, we can create two equations with two unknowns, a solvable approach to finding our two constants.

Since F(0)=0 and F(1)=1, we can substitute in values as shown below to arrive at answers for both c and d.

Substituting these values into our solution, we have a final equation that will give us any Fibonacci number.

Interestingly enough, our solution just happens to contain the "Golden Number," which is a study on its own.  If we let the following,

Then our Fibonacci formula can be simplified to this rather compact form:

• Golden Ratio (information on the Golden Number)