Examples of algorithms and proofs that seem correct, but aren't
2D local maximum

input: 2-dimensional $n \times n$ array $A$

output: a local maximum -- a pair $(i,j)$ such that  $A[i,j]$ has no neighboring cell in the array that contains a strictly larger value.  

(The neighboring cells are those among $A[i, j+1], A[i, j-1], A[i-1, j], A[i+1, j]$ that are present in the array.)  So, for example, if $A$ is

$$\begin{array}{cccc}
0&amp;1&amp;3&amp;\mathbf{4}\\
\mathbf{3}&amp;2&amp;\mathbf{3}&amp;1\\
2&amp;\mathbf{5}&amp;0&amp;1\\
\mathbf{4}&amp;0&amp;1&amp;\mathbf{3}\end{array}$$

then each bolded cell is a local maximum.  Every non-empty array has at least one local maximum.  

Algorithm. There is an $O(n^2)$-time algorithm: just check each cell.  Here's an idea for a faster, recursive algorithm.

Given $A$, define cross $X$ to consist of the cells in the middle column, and the cells in the middle row.  First check each cell in $X$ to see if the cell is a local maximum in $A$.  If so, return such a cell.  Otherwise, let $(i, j)$ be a cell in $X$ with maximum value.  Since $(i, j)$ is not a local maximum, it must have a neighboring cell $(i', j')$ with larger value.

Partition $A \setminus X$ (the array $A$, minus the cells in $X$) into four quadrants -- the upper left, upper right, lower left, and lower right quadrants -- in the natural way.  The neighboring cell $(i', j')$ with larger value must be in one of those quadrants.  Call that quadrant $A'$.  

Lemma. Quadrant $A'$ contains a local maximum of $A$.

Proof.  Consider starting at the cell $(i', j')$.  If it is not a local maximum, move to a neighbor with a larger value.  This can be repeated until arriving at a cell that is a local maximum.  That final cell has to be in $A'$, because $A'$ is bounded on all sides by cells whose values are smaller than the value of cell $(i', j')$.  This proves the lemma. $\diamond$

The algorithm calls itself recursively on the $\frac{n}{2}\times\frac{n}{2}$ sub-array $A'$ to find a local maximum $(i, j)$ there, then returns that cell.

The running time $T(n)$ for an $n\times n$ matrix satisfies $T(n) = T(n/2) + O(n)$, so $T(n) = O(n)$.  

Thus, we have proven the following theorem:

Theorem. There is an $O(n)$-time algorithm for finding a local-maximum in an $n\times n$ array.

Or have we?