Most unusual form of mathematical induction After reading the algebraic proof of Fundamental Theorem of Algebra, where induction was carried out on "The highest power of $2$ dividing $n$", which I regard to be unusual and brilliant at the same time, I wondered if there were other problems where similar unusual inductions were used. So my question is:
What is the most unusual/strange form of induction you have seen? If it's in a paper or book, a reference to the same would be appreciated.
 A: It's hard to say what the "most unusual" induction is, because you can perform induction on (for the sake of simplicity let's say) any countable well-founded relations. Actually a well-founded relation is a concept that is designed to make the induction work. Some particular examples include structural induction, which happens very often in theoretical computer science (mostly the context is termination), e.g. in


*

*dynamic programming,

*rewriting systems,

*potential function arguments, e.g. in complexity theory or in generalized ordinal potentials in game theory.


Having said that, there are many weird relations on which the induction is performed and it would be hard to describe what is the most unusual one. Besides the well-known, one of a bit less-known, but commonly used is the Dershowitz-Manna ordering for multisets, and for some underlying spaces of multisets this might already be pretty hairy.
Perhaps I should also add that you can go even further, e.g. in one of my recent papers (which unfortunately I cannot link to right now) I prove that there exists a well-founded relation with some desirable properties and I proceed with induction on it without even knowing how it looks like (this was weird for me the first time I've written down the proof).
I hope this helps $\ddot\smile$
A: Just to use FLT because it is a well known statement that won't need explaining:
Fermat's last theorem is a statement that asks to prove non-existance.  If you tried to use induction directly, a proof might go something like:
assume : $\not \exists x,y,z,n: x^n + y^n = z^n$
prove : $\not \exists a,b,c,d: a^d + b^d = c^d, d > n$
This would be a difficult approach to attempt for a proof because of the quantifiers.  However you could take the contrapositive of induction:
assume : $ \exists a,b,c,d: a^d + b^d = c^d$
prove : $ \exists x,y,z,n: x^n + y^n = z^n, n < d$
Where it becomes a problem of constructing $x,y,z,n$ from $a,b,c,d$.  A universally quantified problem was converted to an existentially quantified one that can be proven "by example" by reversing the direction of the induction.
(I'm not saying there actually is a valid proof along these lines, I'm just pointing out something interesting you can do with induction.)
