Just another quick example of how inductive proofs can help in linguistics. Well, any nerd who appreciates language will find this one cool. What we'll prove is the property P that the word that describes the most recently developed missile-seeking missile used in an arms race is given, in English, by the formula: anti^(n-1)missile^n. What that says is that the word will contain n copies of the word "missile" stuck one next to the other in a row, preceded by the n-1 copies of the word "anti" stuck together in a row. It may help to think of missiles designed for tanks rather than other missiles: first you start with the intended target, a tank, then stick "anti" to the left to show that it's aimed against a tank, then stick "missile" on the right to show that it's a missile that's taking out the tank. Note that in writing, such a compound word is often spelled as two separate words like "speed limit," but it is really just the same as "bookcase" or "man-breasts." Only the unimportant written forms are different.
OK, consider the Basis n=1, where we're talking about the first missile one country designs. Well, they call it just that, "missile," nothing fancy yet. Sure enough, there is 1 copy of "missile" preceded by 1-1 = 0 copies of "anti." Now, as the arms race gets going, the other country will design an "anti-missile missile," which will in turn prompt the first to design an "anti-anti-missile-missile missile," and so forth. For the Inductive step, assume that P(n) is true, i.e that the above formula describes the nth development. Now consider what the enemy country will do, i.e. the n+1th development: they will design something that is "anti" what the other country just developed at stage n and will also label it a "missile." Since we already began with anti^(n-1)missile^n, now we have something that is "anti" that thing and which is a "missile," and we stick on yet another "anti" to the left and another "missile" to the right in order to capture that. So this n+1th development is an anti^(n)missile^(n+1), which means that P(n+1) is true. This followed from our assumption that P(n) was true, which completes the Inductive step. In conclusion, the formula above gives the word form of the nth development in an arms race for missile-seeking missiles.
The observation of the recursive nature of this English compound word is due to pioneering morphologist and phonologist Morris Halle.