My problem with mathematical induction is that a lot of the time it’s simple to prove a statement is true (just do enough of the algebra calisthenics) yet just because a statement is true doesn’t mean that you learned all that much about a problem. I think everyone that ever took a discrete math class had to churn out the proof for the following statement.
Certainly the wikipedia page on induction doesn’t fail to include this as an example.
This is the canonical inductive proof. However to me it’s not interesting. I think deriving the solution is easy enough. More interesting is deriving the solution to the sum of square or sum of cubes or an arbitrary higher power.
I was curious as to how these formulas came to be. It’s all well and good to say, “Sure, this formula does indeed work”, and it’s a different thing to derive it.
For convenience I will write the identities in the following way:
The crux of the derivation for higher powers lies in the fact that:
to see why this is so, plug in the first few terms of the expansion of (i+1)^2 as well as the last few terms:
Subtracting all the like terms, only two terms remain: -1 and (n+1)^2
Here’s the derivation:
By a similar argument the sum of cubes is derived as well:
After plenty of simplification the simplified form does indeed come out
The same process can be used to derive sums of cubes and any other power, as long as the sums of previous powers are known.