# 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 usV(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 charactaristic equation z³ - az² + - bz - c = 0 with the cubic formula, you get an explicit formula for V(n):

V(n) = A⋅z₁

^{n}+ B⋅z₂

^{n}+ C⋅z₃

^{n},

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₁

^{n}+ B⋅z₁

^{n}+ C⋅z₃

^{n}

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₁

^{n}+ B⋅n⋅z₁

^{n}+ C⋅z₁

^{n}

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

U(n) = [A⋅z₁

^{n+1}+ B⋅z₂

^{n+1}+ C⋅z₃

^{n+1}]/[A⋅z₁

^{n}+ B⋅z₂

^{n}+ C⋅z₃

^{n}]

### Example

Consider the sequence defined byU(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

^{n+1}+ B2

^{n+1}+ C(-3)

^{n+1}]/[An2

^{n}+ B2

^{n}+ C(-3)

^{n}]

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

^{n+1}+ (-3)

^{n+2}]/[(5n - 22)2

^{n}+ (-3)

^{n+1}]

© *Had2Know 2010
*