I think the best example of this will be the [fundamental theorem of arithmetic](http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic): the assertion that every natural number greater than 1 is either prime or the product of primes (and uniquely so). 

Proof of existence is by strong induction. Assume true below n. If n is prime, we're done. Otherwise, n = ab for some a,b < n, and by induction these are products of primes, so n is also. QED (and no need for special anchor case).

Proof of uniqueness does not use induction.