# 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 *ac* ≠ *b*. 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) = [αx^{n} + β]/[x^{n} + γ]

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

If (*a-c*)² + 4*b* = 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.

### 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 charactaristic 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) = P

^{n}[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 explict 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}+ γ]

= [αx

^{n}+ β]/[x

^{n}+ γ]

### 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 are5/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)⋅1

^{n+1}+ D⋅1

^{n+1}]/[n⋅1

^{n}+ D⋅1

^{n}] -

*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 are5, 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
*