MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 2 added 6 characters in body

I think the best example of this will be the fundamental theorem of aithmetic: the assertion that every positive 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.
show/hide this revision's text 1 [made Community Wiki]

I think the best example of this will be the fundamental theorem of aithmetic: the assertion that every positive natural number 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.