My favorite example in discrete mathematics is the sequence $1,2,4,8,16,31,..$. That is, number of regions in a circle 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.
