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.
$$ 1 + 2 + \cdots + n = \frac{n(n + 1)}{2} $$
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.
$$ 1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6} $$
$$ 1^3 + 2^3 + \cdots + n^3 = \frac{n^2(n+1)^2}{4} $$
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:
$$ \displaystyle\sum_{1}^{n}{i} = \frac{n(n + 1)}{2} $$
The crux of the derivation for higher powers lies in the fact that:
$$ \displaystyle\sum_{1}^{n}{(i+1)^2-i^2} = (n+1)^2-1 $$
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:
$$ (i+1)^2 = 2^2 + 3^2 + \cdots + (n-3)^2 + (n-2)^2 + (n-1)^2+ n^2 + (n+1)^2 $$ $$ i^2 = 1^2 + 2^2 + 3^2 + \cdots + (n-3)^2 + (n-2)^2 + (n-1)^2+ n^2 $$
Subtracting all the like terms, only two terms remain: -1 and (n+1)2 Here’s the derivation:
$$ \displaystyle\sum_{1}^{n}{(i+1)^2-i^2} = \displaystyle\sum_{1}^{n}{(i^2+2i+1)-i^2} = \displaystyle\sum_{1}^{n}{2i+1} = (n+1)^2-1 $$ $$ \displaystyle\sum_{1}^{n}{2i+1} = \displaystyle2\sum_{1}^{n}{i} + \displaystyle\sum_{1}^{n}{1} = \displaystyle2\sum_{1}^{n}{i} + n = (n+1)^2-1 $$ $$ \displaystyle\sum_{1}^{n}{i} = \frac{(n+1)^2-1 - n}{2} $$ $$ \displaystyle\sum_{1}^{n}{i} = \frac{n(n+1)}{2} $$ $$ \displaystyle\sum_{1}^{n}{(i+1)^3-i^3} = (n+1)^3-1 $$ $$ \displaystyle\sum_{1}^{n}{(i+1)^3-i^3} = \displaystyle\sum_{1}^{n}{3i^2+3i+1} = (n+1)^3-1 $$ $$ \displaystyle\sum_{1}^{n}{i^2} = \frac{(n+1)^3-1 - n - \frac{3n(n+1)}{2}}{3} $$
After plenty of simplification the simplified form does indeed come out
$$ \displaystyle\sum_{1}^{n}{i^2} = \frac{n(n+1)(2n+1)}{6} $$
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.