Oh, also

A(n) = (pow(3,n)-pow(-1,n))/4

Magic! :)

Oh, also

A(n) = (pow(3,n)-pow(-1,n))/4

Magic!

I was just driving my car and thinking about the non-recursive solution...

Oh, also

A(n) = (pow(3,n)-pow(-1,n))/4

Magic!

Wow! Holy cow! That is awesome! Strange how my textbook does not have that formula! How did you come up with that formula? That's ingenious.

You start at `a' and then you have three choices at each step. Of the possible paths, only 1/4 of them will end at the right spot, so the formula is pow(3,n)/4. Well, powers of 3 are not usually divisible by 4, so you need to do some rounding. </mostly kidding>

Once you have the recursive formula, you can find the explicit formula by trying to find the numbers x such that pow(x,n) satisfies the recursive formula.

pow(x,n) = 3*pow(x,n-2) + 2*pow(x,n-1)

Dividing by pow(x,n-2), you get

x^2 = 3 + 2*x => x^2 - 2*x - 3 = 0

Solving the quadratic equation, you find out that 3 and -1 are the roots. Now all the sequences that satisfy the recursive formula form a vector space of dimension 2 (because the one that starts (1,0,...) and the one that starts (0,1,...) are a basis), and you just found two independent vectors. If you don't know what on Earth I am talking about, don't worry. It means that any sequence that satisfies the recursive formula can be expressed as a*pow(3,n) + b*pow(-1,n), for appropriate values of a and b. Since we know A(0)=0 and A(1)=1,

a*pow(3,0) + b*pow(-1,0) = 0 => a + b = 0
a*pow(3,1) + b*pow(-1,1) = 1 => 3*a - b = 1

Solving that system of linear equations, you get a=1/4, b=-1/4, and that gives us the explicit formula.

This may look like magic if you haven't seen it before, but it's just a procedure you learn.

It's called a recurrence relation http://en.wikipedia.org/wiki/Recurrence_relation

They are also called "difference equations". They are the discrete version of differential equations.