notesonly.in

One notebook for every subject — open it anywhere.

Log in

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.)

← Back to topics for Mathematics