Gauss' "second" (1815) proof of the fundamental theorem of algebra (Werke, Volume 3, 33-56, or see Paul Taylor's translation, currently available here) follows an interesting pattern, similar to the one in Cauchy's proof of the AM-GM inequality mentioned in Pietro's answer. (It does more than this: It introduces the discriminant, for example.)

Gauss shows that a polynomial with real coefficients can be factored into real polynomials of first and second degree. We have that a polynomial of odd degree has a root. From this, he argues by assigning to a polynomial $p$ of degree $n$ a new polynomial $p^+$ of degree $n(n-1)/2$, in such a way that pairs of (possibly complex) roots of $p^+$ determine (possibly complex) roots of $p$ via quadratic equations.

So the pattern is induction not on the degree $n$ of the polynomial, but on the largest power of 2 dividing $n$.

I first encountered this neat idea not through Gauss work, but through a proof by Derksen of the fundamental theorem of algebra via linear algebra (Harm Derksen, "The fundamental theorem of algebra and linear algebra", American Mathematical Monthly, 110 (7) (2003), 620–623.)

The skeleton of Derksen's proof is as follows: One actually shows that:

If $V$ is a complex finite dimensional vector space, and ${\mathcal F}$ is a (possibly infinite) family of pairwise commuting linear operators on $V$, then the operators in ${\mathcal F}$ admit a common eigenvector.

For this, one considers the statement $E(K,d,\kappa)$: If $V$ is a vector space over $K$ of finite dimension, and $d\not{\mathrel{|}}{\rm dim}(V)$, then any family ${\mathcal F}$ with $|{\mathcal F}|=\kappa$ of pairwise commuting linear maps from $V$ to itself admits a common eigenvector.

One easily checks that the case $\kappa$ infinite follows from the finite one, and this follows by a straightforward induction, so it is enough to show $E({\mathbb C},d,1)$.

For this, one first shows $E({\mathbb R},2,1)$: A linear map from ${\mathbb R}^n$ to itself, say, with $n$ odd, admits a real eigenvalue. This follows from odd degree real polynomials having roots.

Then, one shows $E({\mathbb C},2,1)$. For this, let $V$ be a ${\mathbb C}$-vector space of odd degree n, and let $L(V)$ be the space of ${\mathbb C}$-linear transformations of $V$ to itself. Given a linear $T:V\to V$, one associates to it a real-vector subspace of $L(V)$ of real dimension $n^2$, and a pair of commuting linear maps there, in a way that from any common (real) eigenvalue we can reconstruct a complex eigenvalue of $T$. Then one uses $E({\mathbb R},2,2)$.

One then argues by induction on $k$ that $E({\mathbb C},2^k,1)$ holds. As before, to a $T:V\to V$ with $V$ of appropriate dimension $n$, one associates a complex subspace of $L(V)$ of dimension $n(n-1)/2$ and a pair of commuting linear maps there, so the result follows from $E({\mathbb C},2^{k-1},2)$.

(I must confess I haven't worked through the details enough to comment on whether this is essentially Gauss' proof in a different language.)