Arithmetic and Geometric Sequences
What you'll learn: How to recognize and work with sequences that grow by adding a constant (arithmetic) or multiplying by a constant (geometric), and express them with closed-form formulas.
Core Idea
In the last lesson, you learned that a sequence is an ordered list of numbers. Two special types appear constantly in computer science:
Arithmetic sequences grow by adding the same amount each time. For example:
- 3, 7, 11, 15, 19, ... (adding 4 each step)
- 10, 5, 0, -5, -10, ... (adding -5, which is subtracting 5)
The formula for the nth term is: aₙ = a₁ + (n - 1)d, where a₁ is the first term and d is the common difference.
Geometric sequences grow by multiplying by the same amount each time. For example:
- 2, 6, 18, 54, 162, ... (multiplying by 3 each step)
- 100, 50, 25, 12.5, 6.25, ... (multiplying by 0.5, which is halving)
The formula for the nth term is: aₙ = a₁ · rⁿ⁻¹, where a₁ is the first term and r is the common ratio.
Why This Matters
These patterns appear everywhere in computing:
- Arithmetic: Array indices (0, 1, 2, 3, ...), loop counters, memory addresses
- Geometric: Binary search divides a problem in half each time (geometric with r = 0.5), exponential growth in algorithms, powers of 2 (1, 2, 4, 8, 16, ...)
Example
To find the 10th power of 2 without calculating each term:
- Sequence: 1, 2, 4, 8, ... (geometric with a₁ = 1, r = 2)
- Using
aₙ = 1 · 2ⁿ⁻¹ - The 10th term:
a₁₀ = 1 · 2⁹ = 512
Key Takeaway: Arithmetic sequences have constant differences between terms (use addition), geometric sequences have constant ratios (use multiplication), and closed-form formulas let you jump directly to any term without computing all previous ones.