Question: Hello. I am currently searching for some nice examples of proofs by induction in the finite case, that can be generalized to the infinite case using transfinite induction (and dont become trivial there).

Apparently, the only proof that comes in my mind is that every Vector-Space has a base (mostly this is proven by the Zorn-Lemma, but in the finite case this can be proven by induction, and the same proof can be used in the infinite case with transfinite induction).

Do you have any other examples?

Answer: 
Let me give a few examples and a few remarks. 

* Every countable ordinal is realized as a [Cantor-Bendixon rank](http://en.wikipedia.org/wiki/Derived_set_%28mathematics%29) of a closed set . The Cantor-Bendixon derivative X' of set X of reals (or in any topological space) is obtained by casting out isolated points. The rank of X is the number of steps required until a set is reached having no isolated points. The integers in R have rank 1; a convergent sequence has rank 2; a convergent sequence of convergent sequences has rank 3, and so on. The finite ranks are easy to construct by induction. One can continue transfinitely to produce a set with any ordinal rank.
* Cantor's [back-and-forth](http://en.wikipedia.org/wiki/Back-and-forth_method) proof that any two countable endless dense linear orders are isomorphic generalizes to the transfinite, for any two structures of size κ having a collection of partial isomorphisms with the <κ back-and-forth property. This idea is related to the model-theoretic notion of saturation, and is a fundamental method in model theory.

Your question asks for examples of finite induction that extend to the transfinite but do not trivialize when doing so. But perhaps a more common situation with transfinite induction is the dual situation, where an argument that is trivial for finite instances, but becomes nontrivial in the transfinite. For example: 

* Every countable well ordering embeds into the rational order. This is trivial for finite orders, but can be proved for countable ordinals by transfinite induction. (But actually, one can prove generally that any countable linear order embeds into Q, building the embedding by finite recursion on the enumeration of the order.)
* Every well ordering is rigid, in the sense that it has no nontrivial order automorphisms. This is trivial for finite orders, but can be proved by transfinite induction by looking at the least element to be moved.
* More generally, every transitive set is rigid. This and many other arguments in set theory proceed by proving that there can be no ∈ minimal counterexample, and such arguments can be viewed as proofs by transfinite induction on the Levy rank of the set.

Finally, let me make a distinction between using mathematical induction to prove a statement, and using mathematical recursion to carry out a mathematical construction. The difference is that the result of recursion is a mathematical object, rather than a proof of a statement. Many finite recursions extend naturally into the transfinite.

* The construction of the collection HF of all hereditary finite sets proceeds by starting with the empty set, and iterating the power set operation. The transfinite continuation of this simply collects everything together with a union at limit stages, and continues taking the power set at limit stages. The result is the Levy hierarchy Vα of all sets (or of all well-founded sets).
* One can iteratively add one to finite numbers, to get the next larger cardinal number. Continuing transfinitely, one produces the transfinite cardinals Alephα. Similarly, the cardinals Bethα result from iterating the exponential operation Bethα+1 = 2Bethα.
* There are many others.
One way to prove the general Van Kampen Theorem is to prove it first for coverings by finitely many open sets, and then generalize to the arbitrarily large coverings using transfinite induction. Whether this is simpler than Hatcher's direct argument for arbitrary coverings (Theorem 1.20 in his Algebraic Topology book) is probably a matter of taste.