An elementary one, but common when we first dealing with asymptotic notations. Consider the following "proof" to the recurrence relation $T(n) = 2T(n/2) + O(n \log n)$ and $T(1) = 1$:

We prove by induction. For the base case it holds for $n=1$. Assume the relation holds for all numbers smaller than $n$,

$\begin{align} T(n) &= 2 \cdot T(n/2) + O(n \log n) \\ &= 2 \cdot O(n/2 \log n/2) + O(n \log n) \\ &= O(n \log n/2) + O(n \log n) \\ &= O(n \log n) \\ \end{align}$

Q.E.D. (is it?)