Recursive Rules
We have been concentrating mostly on using explicit rules to specify a sequence so far. You can use the explicit formula to determine the value of each term of the sequence directly based on its position index, n, without reference to the values of any of the terms that precede it. However, many mathematical sequences are related to one another in another way, which is that each term is created by using some or all of the earlier (preceding) terms.
To specify a sequence by relating the current term to the terms that occurred before it is called a recursive rule or a recursive formula. An explicit formula can be evaluated on its own; however, the evaluation of a recursive rule is a kind of mathematical chain reaction, since to find an additional value, you will need to have performed all the steps prior to that.
1.0The Operational Anatomy of a Recursive Formula
To be useful, a recursive formula requires two main components:
The Initial Base State
You must state the exact value of the first term (t₁) (or multiple starting terms) to anchor the sequence. Without this starting value, the formula has no baseline to calculate from.
The Recurrence Equation
This algebraic statement defines how the nᵗʰ term (tₙ) links to its preceding values, such as tₙ₋₁ (the term right before it) or tₙ₋₂ (the term two steps back).
Let's look at a basic example:
t₁ = 5, and tₙ = tₙ₋₁ + 4 for n ≥ 2
To find t₂, substitute n = 2 into the equation:
t₂ = t₁ + 4 = 5 + 4 = 9
To find t₃, use the value of t₂:
t₃ = t₂ + 4 = 9 + 4 = 13
This step-by-step process generates the sequence:
5, 9, 13, 17, 21, ...
2.0The Virahānka-Fibonacci Sequence: Real History and Analysis
The most famous multi-step recursive sequence in mathematical history is the Virahānka-Fibonacci sequence. This sequence is defined by a recursive rule where each term is the sum of the two terms directly preceding it:
V₁ = 1, V₂ = 2
and
Vₙ = Vₙ₋₁ + Vₙ₋₂ for n ≥ 3
Let's calculate the first few terms step-by-step:
V₃ = V₂ + V₁ = 2 + 1 = 3
V₄ = V₃ + V₂ = 3 + 2 = 5
V₅ = V₄ + V₃ = 5 + 3 = 8
This gives us the sequence:
1, 2, 3, 5, 8, 13, 21, 34, ...
The True History Behind the Numbers
While Western text repositories often call this the "Fibonacci sequence" after the Italian mathematician Leonardo Fibonacci (c. 1200 CE), it was discovered much earlier in India.
Virahānka, an Indian mathematician, documented this sequence for the first time in Vṛttajātisamuccaya, a work from the 7th century CE. In his research of the poetic structure of both the Sanskrit and Prakrit languages, he found how long (Guru) syllables could combine with short (Laghu) syllables to make meter, so he was able to determine this relationship.
Later, linguist-mathematicians such as Gopāla (approx. 1135 CE) and Hemachandra (approx. 1150 CE) also studied this relationship before it appeared in Europe.
3.0Converting Standard Progressions into Recursive Formats
Any standard progression can be rewritten in a recursive format.
Arithmetic Progression (AP)
Explicit AP Form:
tₙ = a + (n − 1)d
Recursive AP Form:
t₁ = a
tₙ = tₙ₋₁ + d for n ≥ 2
Geometric Progression (GP)
Similarly, a Geometric Progression (GP) can be converted into a recursive format.
Explicit GP Form:
tₙ = a × r⁽ⁿ⁻¹⁾
Recursive GP Form:
t₁ = a
tₙ = r × tₙ₋₁ for n ≥ 2
This flexibility allows us to build complex mathematical loops, which serve as a foundational concept for designing modern computer algorithms and software programs.
4.0Solved Examples
Example 1 Find the first four terms of the sequence defined by the recursive rule:
u₁ = 2, and
uₙ = 3uₙ₋₁ − 1 for n ≥ 2
Solution: Calculate each term sequentially using the previous value:
u₁ = 2
u₂ = 3(u₁) − 1 = 3(2) − 1 = 6 − 1 = 5
u₃ = 3(u₂) − 1 = 3(5) − 1 = 15 − 1 = 14
u₄ = 3(u₃) − 1 = 3(14) − 1 = 42 − 1 = 41
Final Answer: The first four terms of the sequence are:
2, 5, 14, and 41
Example 2: A sequence is generated by the recursive rule:
t₁ = 1, t₂ = 3 and tₙ = tₙ₋₁ × tₙ₋₂ for n ≥ 3
Find the value of t₅.
Solution
Substitute the terms step-by-step:
t₁ = 1
t₂ = 3
t₃ = t₂ × t₁ = 3 × 1 = 3
t₄ = t₃ × t₂ = 3 × 3 = 9
t₅ = t₄ × t₃ = 9 × 3 = 27
Final Answer: The fifth term of the sequence is 27.