How to Solve a Second-Order Rational Recurrence Equation:

U(n+2) = a + b/U(n+1) + c/[U(n+1)U(n)]

One class of second-order rational recurrence relations has the form

U(n+2) = a + b/U(n+1) + c/[U(n+1)U(n)],

where a, b, and c are constants. Though this recursion is non-linear, you can find an explicit formula for U(n) by transforming this rational recursive equation into a third-order linear recursion.

How to Solve for U(n)

Given the rational recurrence relation U(n+2) = a + b/U(n+1) + c/[U(n+1)U(n)], we can make the change of variable using U(n) = V(n+1)/V(n). Plugging this into the original recursive equation gives us

V(n+3)/V(n+2) = a + b⋅V(n+1)/V(n+2) + c⋅[V(n+1)/V(n+2)][V(n)/V(n+1)]

= a + b⋅V(n+1)/V(n+2) + c⋅V(n)/V(n+2)

Multiplying both sides by V(n+2) gives us a third-order linear recursion:

V(n+3) = a⋅V(n+2) + b⋅V(n+1) + c⋅V(n)

By solving the characteristic equation z³ - az² + - bz - c = 0 with the cubic formula, you get an explicit formula for V(n):

V(n) = A⋅z₁ⁿ + B⋅z₂ⁿ + C⋅z₃ⁿ,

where z₁, z₂, and z₃ are the polynomial roots and A, B, and C are constants that depend on the values of U(0) and U(1) . If the characteristic equation has a doubly repeated root, i.e., z₁ = z₂, then the equation is

V(n) = A⋅n⋅z₁ⁿ + B⋅z₁ⁿ + C⋅z₃ⁿ

And if the characteristic equation has a triply repeated root, i.e., z₁ = z₂ = z₃, then the general form of V(n) is

V(n) = A⋅n²⋅z₁ⁿ + B⋅n⋅z₁ⁿ + C⋅z₁ⁿ

Once you know the formula for V(n), you can reconstruct the explicit form of U(n) using the original change of variables:

U(n) = [A⋅z₁ⁿ⁺¹ + B⋅z₂ⁿ⁺¹ + C⋅z₃ⁿ⁺¹]/[A⋅z₁ⁿ + B⋅z₂ⁿ + C⋅z₃ⁿ]

Example

Consider the sequence defined by

U(n+2) = 1 + 8/U(n+1) - 12/[U(n+1)U(n)]

with U(0) = 1 and U(1) = 3. The first few terms of this sequence are

1, 3, -1/3, -11, -3, -67/33, -329/67,...

The characteristic equation is z³ - z² - 8z - 12 = 0, which has the roots 2, 2, and -3. Since 2 is a repeated root, the general solution is

U(n) = [A(n+1)2ⁿ⁺¹ + B2ⁿ⁺¹ + C(-3)ⁿ⁺¹]/[An2ⁿ + B2ⁿ + C(-3)ⁿ]

Plugging in n = 0 and n = 1 gives us a set of equations that can be solved for A, B, and C

1 = [2A + 2B - 3C]/[B + C] ⇔ 2A + B - 4C = 0

3 = [8A + 4B + 9C]/[2A + 2B - 3C] ⇔ A - B + 9C = 0

This system does not have a unique solution, but for a rational function this does not matter since the numerator and denominator can be scaled by a common factor without changing the function. One particular solution to the system is A = 5, B = -22, and C = -3. This gives the complete solution of the recursive equation (after some simplification):

U(n) = [(5n - 17)2ⁿ⁺¹ + (-3)ⁿ⁺²]/[(5n - 22)2ⁿ + (-3)ⁿ⁺¹]

© Had2Know 2010