Mathematics
Solving Recurrences via Generating Functions
Quick fact
One elegant trick: the Fibonacci sequence, defined by the recurrence Fₙ = Fₙ₋₁ + Fₙ₋₂, can be encoded in a single function. From that function, you can read off an exact formula for Fₙ without computing any previous terms.
Why this is interesting
Have you ever seen a pattern like 1, 1, 2, 3, 5, 8… and wondered, 'What comes next?' But could you find the 100th number without adding up all the previous ones?