Mathwords logoMathwords

Recursive Sequence — Definition, Formula & Examples

A recursive sequence is a sequence where each term is defined by applying a rule to one or more of the terms that came before it. You need at least one starting value (called an initial condition) plus the rule to generate the entire sequence.

A sequence {an}\{a_n\} is recursive if it is defined by specifying one or more initial terms a1,a2,…,aka_1, a_2, \ldots, a_k together with a recurrence relation an=f(an−1,an−2,…,an−k)a_n = f(a_{n-1}, a_{n-2}, \ldots, a_{n-k}) that expresses each subsequent term as a function of the preceding kk terms.

Key Formula

an=f(an−1, an−2, …)with initial term(s) givena_n = f(a_{n-1},\, a_{n-2},\, \ldots)\quad\text{with initial term(s) given}
Where:
  • ana_n = The nth term of the sequence
  • an−1,an−2,…a_{n-1}, a_{n-2}, \ldots = One or more preceding terms used to compute the next term
  • ff = The recurrence rule that relates each term to previous terms

How It Works

To use a recursive sequence, start with the given initial term(s). Plug those values into the recurrence relation to find the next term. Then use that new term to find the one after it, and so on. For example, the Fibonacci sequence uses two initial terms (a1=1a_1 = 1, a2=1a_2 = 1) and the rule an=an−1+an−2a_n = a_{n-1} + a_{n-2}. Every arithmetic sequence can also be written recursively as an=an−1+da_n = a_{n-1} + d, and every geometric sequence as an=r⋅an−1a_n = r \cdot a_{n-1}.

Worked Example

Problem: A recursive sequence is defined by a1=3a_1 = 3 and an=2an−1+1a_n = 2a_{n-1} + 1. Find the first four terms.
Initial term: The first term is given directly.
a1=3a_1 = 3
Find a₂: Substitute n=2n = 2 into the recurrence relation.
a2=2a1+1=2(3)+1=7a_2 = 2a_1 + 1 = 2(3) + 1 = 7
Find a₃: Use the value of a2a_2.
a3=2a2+1=2(7)+1=15a_3 = 2a_2 + 1 = 2(7) + 1 = 15
Find a₄: Use the value of a3a_3.
a4=2a3+1=2(15)+1=31a_4 = 2a_3 + 1 = 2(15) + 1 = 31
Answer: The first four terms are 3, 7, 15, 313,\, 7,\, 15,\, 31.

Why It Matters

Recursive definitions appear throughout computer science (algorithms, loops, data structures) and mathematical modeling. Population models like the logistic map and financial calculations such as compound interest balances are naturally expressed as recursive sequences.

Common Mistakes

Mistake: Forgetting to state the initial condition and writing only the recurrence relation.
Correction: A recurrence relation alone does not define a unique sequence. Without knowing a1a_1 (or other starting values), infinitely many sequences satisfy the same rule. Always specify the initial term(s).