Recurrence relations
Counting and combinatorics (advanced) · Mathematics
Study notes
Q: A sequence: a₁ = 1, aₙ = 2aₙ₋₁ + 1 for n > 1. Find a₂, a₃, a₄. a₂ = 2(1)+1 = 3. a₃ = 2(3)+1 = 7. a₄ = 2(7)+1 = 15. Pattern: 1, 3, 7, 15 = 2ⁿ-1! (Prove by induction.)