To start, let's discuss what constitutes a mathematical recurrence. It is a mathematical formula that relies on previous cases in the calculations for the current case. Recurrences must have at least one base case where the formula is equivalent to an actual value rather than a previous case. Programatically, this allows for computing the nth term in a recurrence in O(1) time, as the general form equations don't rely on previous cases.
The first step when solving any linear, homogeneous recurrence (or differential equation) is to solve for 0. So for example, given the Fibonacci recurrence: F(n) = F(n-1) + F(n-2), solve so: F(n) - F(n-1) - F(n-2) = 0. An equivalent differential equation might look like: y" - y' - y = 0.
The next step is to set up the characteristic equation, which is simply a polynomial function. To obtain this, take the difference between the highest parameter and the lowest parameter. In the Fibonacci recurrence, the difference is two (n - (n-2)), so the characteristic equation is a quadratic. With differential equations, the difference in the order of derivatives is used to determine the power of the characteristic equation. So y" is a 2nd order derivative, and y is a 0 order derivative, still leaving a quadratic.
Thus the characteristic equation for both the Fibonacci recurrence and the differential equation is: r2 - r - 1 = 0. The next step is to find the roots of the characteristic equation, which are called eigenvalues. Different general forms are used based on whether the eigenvalues are real and distinct, real and repeated, or complex. These equations are similar for linear recurrences and differential equations, with the major difference being that the recurrence solutions have the eigenvalues as the bases, and the differential equation solutions have e as the bases. The formulas are as follows:
Real and Distinct Roots:
- Linear Recurrences: f(n) = A(r1)n + B(r2)n
- Differential Equations: f(t) = Ae(r1)t + Be(r2)t
Real and Repeated Roots:
- Linear Recurrences: f(n) = Arn + Bnrn
- Differential Equations: f(t) = Aert + Btert
Complex Roots (where r = a +- bi):
- Linear Recurrences: f(n) = Dancos(bn) + Gansin(bn)
- Differential Equations: f(t) = Deatcos(bt) + Geatsin(bt)
The equations for the complex roots come from Euler's formula: eit = cos(t) + isin(t). Since r1 = a + bi, and r2 = a - bi, the solution can be written as: f(n) = e(a+bi)n + e(a-bi)n. Further simplification with trig identities will result in the above equations. It is assumed that you have already covered this in a precalculus or calculus course. While the first two equations can be used, it may be easier in many cases to rely on this third equation.
After selecting the appropriate general form equation from above, the final step is to set up a system of equations around the base cases. Given the Fibonacci recurrence, the base cases are: F(0) = 0 and F(1) = 1. Knowing that the Fibonacci eigenvalues are (1 +- sqrt(5))/2, the system of equations can be set up:
0 = A + B
1 = A(1 + sqrt(5))/2 + B(1-sqrt(5))/2
Solving this leaves A = sqrt(5)/5 and B = sqrt(5)/5, and the final recurrence as:
F(n) = sqrt(5)/5 * [(1+sqrt(5))/2]n - sqrt(5)/5 * [(1-sqrt(5))/2]n
Let's look at one final example: f(n) = 2f(n-1) - 2f(n-2), with the base cases f(0) = 1, and f(1) = 1.
The first step is to solve for 0:
f(n) - 2f(n-1) + 2f(n-2) = 0
From here, the characteristic equation (a quadratic) becomes:
r2 - 2r + 2 = 0
Since this cannot be factored, the quadratic equation will have to be used to solve for the eigenvalues:
r = [2 +- sqrt(4 - 4(1)(2))]/2
r = 1 +- i
Since the roots are complex, the equation f(n) = D(1)ncos(n) + G(1)nsin(-n). Or more simply: f(n) = Dcos(n) - Gsin(n).
Setting up the system of equations with the eigenvalues leaves:
f(0) = 1 = Dcos(0) + Gsin(0)
f(1) = 1 = Dcos(1) + Gsin(1)
Since sin(0) = 0 and cos(0) = 1, the f(0) equation cancels out leaving D = 1. From there, solving f(1) equation: 1 = cos(1) + Gsin(1) leaves G = (1-cos(1))/sin(1).
Thus the recurrence solution is: f(n) = cos(n) + (1-cos(1))/sin(1) * sin(n).
Conclusion
While solving recurrences may seem like a lot of work on the front end, it can save a lot of computational time when compared to implementing the recursive or iterative solutions. This math on the front end will allow either human or computer to find the nth term (especially for large values of n) in O(1) time vs. O(n) and greater for the more naive solutions.
MultiQuote
| 