Here is a very subtly wrong application of induction I came across:

A prisoner has been condemned to death, and the judge tells him he will be executed at some point during the next month, which happens to be January. However, the judge refuses to fix a date, saying "I promise you that you won't know what day you are to be executed until the guards come to collect you at 8 o'clock in the morning of that day."

So the prisoner goes back to his cell and thinks this over. Firstly, he realises that he cannot possibly be executed on January 31st, because if it gets to 8:10 am on January 30th and the guards haven't come to collect him, then he will know that he is to be killed the next day (since he has to be executed in January) - but this contradicts what the judge said!

Next, he realises that he cannot be executed on January 30th, since if it gets to 8:10 am on January 29th and the guards haven't come, then since he knows they won't be coming on the 31st, they must be coming on the 30th, so he knows the day of his execution in advance and this again contradicts the judge.

Now using exactly the same reasoning, he sees he cannot be executed on the 29th, the 28th, the 27th... in fact he cannot be executed at all! The prisoner stops worrying, and is consequently rather surprised when the guards come for him on the 17th...

So where did the prisoner go wrong? This is a subtle problem, and I'm not sure I've solved it. To avoid spoiling your fun I've put my answer lower down the page.

Okay, what I think the answer is is this: the prisoner's logic is entirely correct, but the judge's statement is wrong, or at least inconsistent with the assertion that he is to be executed in January. A possible correction would be: "Either you will be executed on the 31st, or you won't know the day in advance."