Although building up to it might be beyond the time available in many courses introducing induction, an interesting elementary example that seems unbelievable but is very easy to verify in any given case is Pick's Theorem.

Although building up to it might be beyond the time available in many courses introducing induction, an interesting elementary example that seems unbelievable but is very easy to verify in any given case is Pick's Theorem.