How to Solve a Second Order Linear Recursive Equation
A recurrence relation or recursive equation expresses a discrete function in terms of its preceding values. A common type of recurrence equation is the linear second order recursion, which has the general form
Un+2 = aUn+1 + bUn.
A famous example of a sequence defined by a second order linear recurrence is the Fibonacci sequence, whose numbers are generated by the equation
Fn+2 = Fn+1 + Fn,
where F0 = F1 = 1. The first few Fibonacci numbers are 1, 1, 2, 3, 5, 8, 13, 21, 34...
One difficulty in dealing with recursively defined sequences is finding the value of the nth term for an arbitrary value of n. For large values of n, it is impractical to generate all of the terms leading up to n recursively.
Fortunately however, you can solve second order linear recursive equations explicitly to express Un as a function of n. The basic idea is to assume a solution of the form Un = Crn, which means that rn+2 = arn+1 + brn. This implies that r satisifies the quadratic equation r2 - ar - b = 0.
Since a quadratic equation has two solutions, we can improve the initial assumption to Un = Crn + Ksn.
There are three separate cases of solutions depending on the relation between a and b. The process is similar to solving a second order linear differential equation. You can follow the instructions below, or use the convenient solver on the left.
Case I: a2 + 4b > 0 (b ≠ 0)
When a2 + 4b > 0, the equation for Un has the formUn = C(0.5a + 0.5sqrt(a2+4b))n + K(0.5a - 0.5sqrt(a2+4b))n,
where C and K are coefficients whose values depend on the initial conditions U0 and U1. The values of C and K can be obtained by plugging in 0 and 1 for n and solving a system of linear equations in C and K:
U0 = C + K
U1 = C(0.5a + 0.5sqrt(a2+4b)) + K(0.5a - 0.5sqrt(a2+4b))
Case II: a2 + 4b = 0 (b ≠ 0)
When a2 + 4b = 0, the equation has the formUn = C(0.5a)n + Kn(0.5a)n.
As before, the values of the constants C and K can be determined from the initial conditions and by plugging in 0 and 1 for n. The equations to be solved are:
U0 = C
U1 = 0.5a(C + K)
Case III: a2 + 4b < 0
When a2 + 4b < 0, the equation has the formUn = C(0.5a + 0.5sqrt(-a2-4b)i)n + K(0.5a - 0.5sqrt(-a2-4b)i)n,
where i is the imaginary constant equal to sqrt(-1), and C and K are (possibly complex) coefficients. Because complex bases are cumbersome to work with, there is an equivalent form of Un:
Un = (sqrt(-b))n[Pcos(n*tan-1(sqrt(-1-4b/a2))) + Qsin(n*tan-1(sqrt(-1-4b/a2)))],
where sqrt(-b) is the magnitude of 0.5a ± 0.5sqrt(-a2-4b)i, and tan-1(sqrt(-1-4b/a2)) is the argument (angle) of 0.5a ± 0.5sqrt(-a2-4b)i. The constants P and Q can be determined from the values of U0 and U1 and by plugging in 0 and 1 for n as before.
Case IV: b = 0
When b = 0, the equation reduces to a first order linear recurrence whose solution is of the form Un = Can, where C = U0.© Had2Know 2010