First-Order Rational Recurrence Sequence Calculator

A first-order rational recurrence relation has the form

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

where acb. Though this recursion is non-linear, you can find an explicit formula for U(n) by transforming the rational recursion into a second-order linear recursion. The general form of the solution is

U(n) = [αxn + β]/[xn + γ]

so long as (a-c)² + 4b ≠ 0.

If (a-c)² + 4b = 0, then the general form of the solution is

U(n) = [αn + β]/[n + γ]

where α, β, γ, and x are parameters (possibly complex) that depend on the values of a, b, c, and the initial value U(0). You can use the calculator below to find an explicit formula for U(n). The method of solution is explained below the calculator.

First-Order Rational Recurrence Sequence Calculator: U(n+1) = [aU(n) + b]/[U(n) + c]

Coefficients:
  a =
  b =
  c =
Initial Value:
  U(0) =

Explicit Formula for U(n)

Given the rational recurrence relation U(n+1) = [a⋅U(n) + b]/[U(n) + c], we can make the change of variable

U(n) = V(n+1)/V(n) - c

Plugging this into the original recursive equation gives us

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

which simplifies to

V(n+2) = (a + c)V(n+1) + (b - ac)V(n)

By solving the quadratic characteristic equation z² - (a+c)z + ac-b = 0, you get an explicit formula for V(n):

V(n) = A⋅z₁n + B⋅z₂n

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

V(n) = A⋅n⋅z₁n + B⋅z₁n

If the roots are complex (complex conjugates), the solution can be written in the alternative form

V(n) = Pn[A⋅cos(Qn) + B⋅sin(Qn)]

where P is the modulus and Q is the argument of 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₁n+1 + B⋅z₂n+1]/[A⋅z₁n + B⋅z₂n] - c

= [z₁n+1 + D⋅z₂n+1]/[z₁n + D⋅z₂n] - c, where D = B/A

= [z₁(z₁/z₂)n + Dz₂]/[(z₁/z₂)n + D] - c

= [α(z₁/z₂)n + β]/[(z₁/z₂)n + γ]

= [αxn + β]/[xn + γ]

Example 1

Consider the sequence defined by U(n+1) = [3U(n) - 4]/[U(n) - 1], with U(0) = 5/4. The first few terms in this sequence are

5/4, -1, 7/2, 13/5, 19/8, 25/11, 31/14,...

Since a = 3, b = -4, and c = -1, the characteristic equation is z² - 2z + 1 = 0, which has the repeated root z = 1. This means

U(n) = [(n+1)⋅1n+1 + D⋅1n+1]/[n⋅1n + D⋅1n] - c

= [n + 1 + D]/[n + D] + 1

And since U(0) = 5/4, we find D = -4/3. Thus the complete solution, after some simplification, is

U(n) = (6n - 5)/(3n - 4) = (2n - 5/3)/(n - 4/3)

Example 2

Consider the sequence defined by U(n+1) = [3U(n) - 5]/[U(n) - 1], with U(0) = 5. The first few terms of this cyclic sequence are

5, 5/2, 5/3, 0, 5, 5/2, 5/3, 0,...

Since a = 3, b = -5, and c = -1, the characteristic equation is z² - 2z + 2 = 0, which has the roots z₁ = 1 + i and z₂ = 1 - i. This means P = sqrt(2) and Q = π/4. The general form of U(n) is



U(n) =

sqrt(2)[cos(π(n+1)/4) + D⋅sin(π(n+1)/4)]/[cos(πn/4) + D⋅sin(πn/4)] + 1



And since U(0) = 5, we have D = 3. Thus the complete solution is



U(n) =

sqrt(2)[cos(π(n+1)/4) + 3⋅sin(π(n+1)/4)]/[cos(πn/4) + 3⋅sin(πn/4)] + 1


© Had2Know 2010