Climbing Stairs - Insight

To reach step $n$, you must come from step $n-1$ (taking 1 step) or step $n-2$ (taking 2 steps). So $ways(n) = ways(n-1) + ways(n-2)$.

This is the Fibonacci recurrence. Base cases: $ways(1) = 1$, $ways(2) = 2$. The sum rule applies because reaching from $n-1$ and from $n-2$ are mutually exclusive paths.