I know that I've seen an example of a statement of the form ##\forall n~P(n)## (where the scope of the "for all" is the set of positive integers) that can be proved, but can't be proved by induction. I thought I had seen it in one of Roger Penrose's books, but I have looked for it and wasn't able to find it. Maybe I saw it on some web page. I'm pretty sure that Penrose was involved somehow. The example defines a sequence for each positive integer. Each of the sequences starts out growing absurdly fast, and at an increasing rate, and it's clear that each sequence will continue to grow for a long time. But, if I remember correctly, the claim that you can't prove by induction, is that in each sequence, all but a finite number of terms are zero. Does this sound familiar to anyone? I would like to look at that example again. If you know any other fun examples of when induction fails, I'd be interested in them as well.