Recursion, Induction, and Why My Brain Likes Both

Mathematical induction is the proof technique that says: if it works for $n=1$ and $n \Rightarrow n+1$, it works everywhere. Recursion is induction's impatient twin who wants the answer now.

The sum of the first $n$ positive integers:

Inline math works too: $E = mc^2$ is overrated; $O(n \log n)$ is where the real drama lives.