This question is prompted by a remark from Bill Dubuque in his answer to this question on proving a particular sum without using mathematical induction.
From Bill's answer:
A proof that a statement is true for all integers must - at some point or another - employ mathematical induction. The use of induction may not be obvious - it may be hidden (far) down the inference chain in some other theorem or lemma invoked, as in said uniqueness theorem for recurrences (difference equations).
My question is, is this always true? (I have no particular reason to doubt its veracity, but am curious if it is always true). And if so, why is this the only tenable strategy for proving a statement about all integers? If not, what are the alternative strategies?
It seems like we have to prove things for all integers with some frequency (in some areas of mathematics), so realizing that every single one of these proofs will somehow rest on inducting narrows one's search space for a proof quite substantially. I'd just like to know how strong a statement this really is.