Recurrence relations
Discrete Mathematics · Engineering
Study notes
Tower of Hanoi: T(n) = 2T(n-1) + 1 with T(1) = 1. Unfolding gives T(n) = 2^n - 1. For 64 disks that is about 1.8 times 10^19 moves; at one move per second this needs 585 billion years. Recurrences expose such explosions.