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
1a - 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
12^n + c
23^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.