AFAIK there is no real

official name for these types of

recurrence relations which are similar to the

recursive definition of the

Fibonacci numbers.

That is:

F(n) = F(n-1) + F(n-2)

where F(0) = 0 F(1) = 1

These are a particularly difficult class of recurrence relations to solve. By solving, I mean writing a closed form

equation, of course.

For example:

let T(0) = 6

let T(1) = 13

where T(n) = 5T(n-1) - 6T(n-2) for n > 1

Previous

math experience dictates that these types of functions usually have behavior matching c*a^n. In order to solve this problem, we will employ what is known as the

characteristic equation, which is:

a^2 - d

_{1}a - d

_{2} = 0

where d1 = (in this case) 5 (from 5T(n-1))

and d2 = (in this case) 6 (from 6T(n-2))

Assume the characteristic equation is known, proving it is beyond the scope of this node.

in our case, this would be 0 = a^2 + 5a + 6

after using the

quadratic formula to factor this equation, we determine that a = 2 or 3.

Thus our present

general solution is:

T(n) = c

_{1}2^n + c

_{2}3^n.

At this point we use the initial conditions to determine the following:

T(0) = c

_{1} + c

_{2} = 6

T(1) = 2c

_{1} + 3c

_{2} = 13

Solving these equations using some algebra yields:

c

_{1} = 5

c

_{2} = 1

And finally, we can use all these results to obtain the final closed solution of:

T(n) = (5)2^n + 3^n

Observe that using the recursive definition

T(2) = 5T(1) - 6T(0) = 5(13)-6(6) = 29

and using our closed form yields

T(2) = (5)2^2 + 3^2 = 5(4)+9 = 29

Math is power folks.