Induction

05 Jul 2019

Consider the formula for computing the sum of squares:

$$\sum_{k=0}^{n} k^{2} = \dfrac{n(n+1)(2n+1)}{6}.$$

The formula says there are two ways to find a solution. The conventional way, shown by the left-hand side (LHS) of the equation, says that starting from 0, square 0, then add to it the square of 1, then add to it the square of 2, and continue adding subsequent squares to the series, finally stopping after the n-th number is squared and added. Then just add all the terms in the series together and get an answer.

For example, in calculating the sum of the squares up to and including 10, the LHS method is applied to yield:

$$0^{2} + 1^{2} + 2^{2} + 3^{2} + 4^{2} + 5^{2} + 6^{2} + 7^{2} + 8^{2} + 9^{2} + 10^{2} = 385.$$

Now the right-hand side (RHS) claims to get the same answer as the LHS simply by substituting the highest term ($10$ in for $n$), and evaluating the expression. With skepticism, substituting and evaluating the RHS yields:

$$\dfrac{10(10+1)(2 \cdot 10 + 1)}{6} = \dfrac{10 \cdot 11 \cdot 21}{6} = \dfrac{2310}{6} = 385.$$

So while the formula appears to work for a specific example, does it also work with other numbers? Can we be absolutely sure it would work for the first thousand, million, billion, or even trillion square numbers? A reasonable idea would be to keep a continuously expanding (and large and dusty) book of calculations in the library that we could look up to be sure the formula works for a particular example. Just have a computer continuously calculate the sums of the squares using the LHS and RHS methods, and check to see if both sides equal each other. Surely, performing continuous calculations using larger and larger numbers provides more than ample evidence in proving that the formula is true and universal for other numbers!

In 1910, mathematicians Alfred North Whitehead and Bertrand Russell published Principia Mathematica to build and prove mathematical foundations from first principles. It took nearly 400 pages of symbolic logic to prove that $1+1=2$.It turns out that in math, specific examples can't be used as proofs. In writing proofs, only variables, symbols, and previously proven ideas such as axioms, corollaries, lemmas, and theorems can be used as building blocks to show the truth or falsity of a statement. So how do we prove this? The good news is we have a powerful tool at our disposal which will rigorously prove and answer this question.

That tool, is INDUCTION. And here's my take on what it means:

"If you can show that the next thing exists in the current thing, then you've proved that the current thing works for all subsequent things."

In the next post, we'll see induction in action, and apply it in proving the sum of squares formula.