How about the result concerning finding the roots of polynomials; that there are increasingly complex exact and explicit formulae as you go from linear to quartic, but it's impossible to find such formulae for quintics or higher.

I don't know if that fits your needs: it's elementary to state, but not exactly elementary to prove.