I am interested in theorems with unexpected conclusions. I don't mean
an unintuitive result (like the existence of a space-filling curve), but
rather a result whose conclusion seems disconnected from the
hypotheses. My favorite is the following. Let $f(n)$ be the number of
ways to write the nonnegative integer $n$ as a sum of powers of 2, if
no power of 2 can be used more than twice. For instance, $f(6)=3$
since we can write 6 as $4+2=4+1+1=2+2+1+1$. We have
$(f(0),f(1),\dots) = $ $(1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,\dots)$. The
conclusion is that the numbers $f(n)/f(n+1)$ run through all the
reduced positive rational numbers exactly once each. See A002487 in
the On-Line Encyclopedia of Integer Sequences for more
information. What are other nice examples of "unexpected conclusions"?
My favorite example of this phenomenon is Goodstein's Theorem.
Take any positive number $a_2$, such as the number $73$, and write it in complete base $2$, which means write it as a sum of powers of $2$, but write the exponents also in this way.
$$a_2 = 73 = 64 + 8 + 1 = 2^{2^2+2} + 2^{2+1} + 1.$$
Now, obtain $a_3$ by replacing all $2$'s with $3$'s, and subtracting $1$. So in this case,
$$a_3 = 3^{3^3+3} + 3^{3+1} + 1 - 1 = 3^{3^3+3} + 3^{3+1}.$$
Similarly,  write this in complete base $3$, replace $3$'s with $4$'s, and substract one, to get
$$a_4= 4^{4^4+4} + 4^{4+1} - 1 = 4^{4^4+4} + 3\cdot 4^4 + 3\cdot 4^3 + 3\cdot 4^2 + 3\cdot 4 + 3.$$
And so on. The surprising conclusion is that:
Goodstein's Theorem. For any initial positive integer $a_2$, there is $n>2$  for which $a_n=0$.
That is, although it seems that the sequence is always growing larger, eventually it hits zero. Our initial impression that this process should proceed to ever larger numbers is simply not correct. Indeed, a stronger version of the theorem, with essentially the same proof, allows one to replace the current base with any desired larger base, rather than merely increasing it by $1$ at each step.
To prove Goodstein's theorem, one can use the transfinite ordinals to measure the complexity of the numbers that arise. For example, our initial number $a_2=73$ is associated with the ordinal $\omega^{\omega^\omega+\omega}+\omega^{\omega+1}+1$. One then proves that these associated ordinals strictly descend at each step, because of the subtracting one part. Thus, it must hit zero, and the only way this happens is if the number itself is zero. One can see that we had to split up the complexity of the number  in moving from $a_3$ to $a_4$, and this causes the associated ordinal to strictly descend, even though in this case the actual number happened to get larger. Eventually, the proof goes, the complexity drops low enough that the base exceeds the number, and from this point on, one is just subtracting one endlessly.
This conclusion is very surprising. But this theorem actually packs a one-two punch! Because not only is the theorem itself surprising, but then there is the following surprise follow-up theorem:
Theorem. Goodstein's theorem is not provable in the usual Peano Axioms PA of arithmetic.
That is, the statement of Goodstein's theorem is independent of PA. It was a statement about finite numbers that is provable in ZFC, but not in PA.
