So, let us assume that , and . (In other words, let's assume the opposite of what we want to prove.)
Then let be the propositional function:
Then by hypothesis
Now is true for some
So, by induction is true
is true . But . Contradiction. Therefore the original assumption is false.
*Note: the proposition is true whenever is false. So if , the proposition is true, because is always false. It seems a bit crazy at first sight, but it is OK!