Claim: I can traverse an $n \times n$ matrix in $O(n)$.
"Proof": Clearly, this is true for $n=1$. Now suppose this is true for $n-1$. Then given an $n \times n$ matrix, traverse the upper left $(n-1)\times(n-1)$ matrix in $O(n-1)$ time, and then the remaining row and column in $O(2n)$ time. This gives $O(n-1) + O(2n) = O(n)$ time.
What's wrong with this?
You take a turn for the worst at the first statement.
It just so happens that $n=1$ is the only positive integer for which $n^2=n$. Now that you've seeded our thinking with plausible deniability -- it sure looks like it's $O(n)$ for $n=1$ -- you then run with it in the rest of the proof.