Fibonacci like recurrence relations (idea)

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₁a - d₂ = 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₁2^n + c₂3^n.

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

T(0) = c₁ + c₂ = 6
T(1) = 2c₁ + 3c₂ = 13

Solving these equations using some algebra yields:
c₁ = 5
c₂ = 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.