From van der Waerden's book I learned this proof of the fundamental theorem of algebra, where the induction is on the exponent of 2 in the prime decomposition of the degree of the polynomial:
To show that every real polynomial $p(x)=x^n+t_{n-1} x^{n-1}+\cdots +t_0$ has $n$ roots in the complex numbers $\mathbb C$, write $n=2^k\cdot u$ with $u$ odd, and induct on $k$. For $k=0$, the degree is odd, and you have a root in $\mathbb R$. For $k>0$, let $(a_1,\ldots, a_n)$ be the roots of $p$ in some extension field; prove that the polynomial with roots $b_{ij}=a_i+a_j$ has real coefficients and use the induction hypothesis on $\binom{n}{2}$ to show that the $b_{ij}$ are in $\mathbb C$. Do the same for $c_{ij}=a_i a_j$, and then compute $a_i$ and $a_j$ from $b_{ij}$, $c_{ij}$ using square roots only.
