✦ScienexySCIENCE KNOWLEDGE LIBRARY
General science · SCI-FORM-ALG-049

General Recurrence Relation for a First-Order Sequence

A first-order recurrence relation defines each new term of a sequence using the immediately preceding term and, optionally, the term index.

\(a_(n+1) = f(n, a_{\mathrm{n}}), \text{ with } initial value a_1; common linear form: a_(n+1) = ra_{\mathrm{n}} + c\)

What this formula means

Definition

A first-order recurrence relation defines each new term of a sequence using the immediately preceding term and, optionally, the term index.

Interpretation

The general form states that the next term is obtained by applying a specified function to the current term and its index. A common special case is a linear recurrence with constant coefficients.

Mathematical Significance

Recurrence relations describe sequences generated step by step and are fundamental in discrete mathematics, algorithms, population models, and numerical processes.

Special Cases

  • If a_(n+1) = a_n + d, the sequence is arithmetic.

  • If a_(n+1) = ra_n, the sequence is geometric.

  • If a_(n+1) = ra_n + c, the recurrence is first-order linear with constant coefficients.

  • If r = 1 in the linear form, the sequence increases by the constant c at each step.

Scientific principle

Principle

A recurrence relation generates a sequence by repeatedly applying a rule to previously calculated values.

Derivation

  • Specify an initial value a_1.

  • Define a rule for calculating the next term from the current term.

  • For a general first-order recurrence, write a_(n+1) = f(n, a_n).

  • Apply the rule successively to obtain a_2, a_3, a_4, and later terms.

  • For the linear special case a_(n+1) = ra_n + c, repeatedly substitute the previous term.

  • This gives a_n = r^(n - 1)a_1 + c[1 + r + r² + ... + r^(n - 2)] for n ≥ 2.

  • When r ≠ 1, the resulting closed form is a_n = r^(n - 1)a_1 + c(1 - r^(n - 1))/(1 - r).

  • When r = 1, the closed form becomes a_n = a_1 + (n - 1)c.

Final Result

General form: a_(n+1) = f(n, a_n). Linear constant-coefficient form: a_(n+1) = ra_n + c.

Variables and their meanings

A n

Current term of the sequence.

A (n+1)

Next term.

F

A specified function that determines the next term.

N

Positive integer index.

R

Constant multiplier in the linear recurrence.

C

Constant additive term in the linear recurrence.

A 1

Initial value required to generate the sequence.

SI units and conversions

Si Unit

Depends on the quantities represented by the sequence.

Dimensional Formula

Depends on the sequence. In a_(n+1) = ra_n + c, r must be dimensionless and c must have the same dimension as a_n.

Explanation

A recurrence relation is a mathematical rule rather than a physical quantity. Its units depend on the meaning of the sequence terms.

Conditions of use

  • A first-order recurrence must specify how the next term depends on the current term.

  • An initial value is required to generate a unique sequence.

  • The function must be defined for the values at which it is evaluated.

  • For the linear constant-coefficient form, r and c must remain constant across the sequence.

Limitations and assumptions

  • A recurrence relation without sufficient initial conditions may not determine a unique sequence.

  • The general function form does not necessarily have a simple closed-form solution.

  • The linear closed-form expression applies specifically to a_(n+1) = ra_n + c, not every first-order recurrence.

  • The recurrence may behave differently depending on its function, parameters, and initial value.

Step-by-step worked examples

ProblemGivenSolutionAnswer

A sequence is defined by a_1 = 2 and a_(n+1) = 3a_n + 1. Find its first five terms.

A 1

2

R

3

C

1

  • Start with a_1 = 2.

  • Calculate a_2 = 3(2) + 1 = 7.

  • Calculate a_3 = 3(7) + 1 = 22.

  • Calculate a_4 = 3(22) + 1 = 67.

  • Calculate a_5 = 3(67) + 1 = 202.

The first five terms are 2, 7, 22, 67, 202.

A sequence is defined by a_1 = 10 and a_(n+1) = a_n - 2. Find its sixth term.

A 1

10

R

1

C

-2

N

6

  • This is the linear recurrence a_(n+1) = ra_n + c with r = 1 and c = -2.

  • Use the closed form a_n = a_1 + (n - 1)c.

  • a_6 = 10 + (6 - 1)(-2).

  • a_6 = 10 - 10 = 0.

The sixth term is 0.

Real-world applications

  • Modelling population changes from one time period to the next.

  • Representing compound growth with repeated additions or multiplications.

  • Generating numerical sequences in computer algorithms.

  • Describing iterative calculations and discrete-time mathematical systems.

  • Studying repeated processes in economics, biology, and computational mathematics.

Formula Meaning

Definition

A first-order recurrence relation defines each new term of a sequence using the immediately preceding term and, optionally, the term index.

Interpretation

The general form states that the next term is obtained by applying a specified function to the current term and its index. A common special case is a linear recurrence with constant coefficients.

Mathematical Significance

Recurrence relations describe sequences generated step by step and are fundamental in discrete mathematics, algorithms, population models, and numerical processes.

Special Cases

  • If a_(n+1) = a_n + d, the sequence is arithmetic.

  • If a_(n+1) = ra_n, the sequence is geometric.

  • If a_(n+1) = ra_n + c, the recurrence is first-order linear with constant coefficients.

  • If r = 1 in the linear form, the sequence increases by the constant c at each step.

Sources and further reading

No source has been supplied for this item yet. Treat the claim as needing editorial verification.

← Back to Formula Hub · Suggest a correction or source