My favorite example in discrete mathematics is the sequence $1,2,4,8,16,31,..$. That is, [number of regions in a circle][1] after drawing all the chords between $n$ points on the boundary of the circle.

It shows that a simple pattern might be wrong, and that we do need formal proofs, no matter how many examples we've checked.


  [1]: http://mathworld.wolfram.com/CircleDivisionbyChords.html