Can every theorem involving countable things necessarily be proven by induction? Last night I was working on some problems to remember how proof by induction worked, and I began to wonder if it's possible to prove every theorem on countable things by induction.  I understand proof by induction may not be the most elegant or simple way to construct the proof.
If so, is there a proof of this?  If not, is there a counterexample?
BTW, the problem I was struggling with, but finally figured out, was to prove that:
$\sum_{i=1}^n i^3 = (\sum_{i=1}^ni)^2$
 A: I assume you found something like$$\left(\sum_{i=1}^ni\right)^2-\left(\sum_{i=1}^{n-1}i\right)^2=\left(\sum_{i=1}^ni-\sum_{i=1}^{n-1}i\right)\left(\sum_{i=1}^ni+\sum_{i=1}^{n-1}i\right)=n\cdot n^2=n^3.$$I think whether all theorems on countable sets are provable by induction is an open question; the hard part would be checking some ordering exists for which a proof of the inductive step must exist. Whether I'm right or wrong, this question is probably a better fit for MathOverflow than for math.se, because it looks very, very nontrivial.
But I suspect far more theorems are thereby provable than first seem to be. There's a very complicated inductive argument in Wiles's proof of (the semistable case of) the modularity theorem, for which he needed not only a sensible ordering of E- & M-series, but also a way to make the inductive step work for said ordering. (I'm not an expert on it, but I expect he worked backwards from needing the inductive step to work to inspire him in how he'd order them.)
A: Nope. The Faulhaber formulas can be obtained by the method of indeterminate coefficients, leading to small linear systems of equations. (And I doubt that your concern has anything to do with countability.)
