Loading problem...
The Additive Sequence is a fundamental mathematical series where each term is derived by summing the two immediately preceding terms. The sequence begins with two base values: the first term is 0 and the second term is 1. All subsequent terms are computed using the following recurrence relation:
S(0) = 0, S(1) = 1
S(n) = S(n - 1) + S(n - 2), for n > 1
This creates the sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
Given a non-negative integer n, your task is to compute and return the value of the n-th term in this additive sequence, denoted as S(n).
This problem serves as a foundational exercise in understanding recursive relationships and dynamic programming principles. The additive sequence pattern appears extensively in mathematics, computer science, and natural phenomena, making it an essential concept to master.
n = 21Using the recurrence relation: S(2) = S(1) + S(0) = 1 + 0 = 1. The sequence so far is [0, 1, 1], and we return the value at index 2.
n = 32Continuing the sequence: S(3) = S(2) + S(1) = 1 + 1 = 2. The sequence becomes [0, 1, 1, 2], and the third index contains the value 2.
n = 43Following the pattern: S(4) = S(3) + S(2) = 2 + 1 = 3. The full sequence up to index 4 is [0, 1, 1, 2, 3], so we return 3.
Constraints