display | more...
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 - d1a - d2 = 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) = c12^n + c23^n.

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

T(0) = c1 + c2 = 6
T(1) = 2c1 + 3c2 = 13

Solving these equations using some algebra yields:
c1 = 5
c2 = 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.

Log in or register to write something here or to contact authors.