Proof by Induction for the Sum of Squares Formula

11 Jul 2019

Problem

Use induction to prove that ⊕ Sidenotes here and inside the proof will provide commentary, in addition to numbering each step of the proof-building process for easy reference. They are not part of the proof itself, and must be omitted when written.

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

for all $n \ge 0$.

NOTE: $k$ is a placeholder variable representing each number in a series starting from $0$, and up to and including $n$. Shove the current value of $n$ into $k$, evaluate, and do the same for the next value of $n$, etc. The "E"-shaped figure is an uppercase Sigma from the Greek alphabet. Because Sigma's spelled with an "s", it's used to represent a summation, or sum. The left-hand side (LHS) reads, "the sum from k equals zero to n of k squared."

1. Basis step ⊕ Since the formula claims to work for all numbers greater than or equal to ($\ge$) $0$, $0$ must be tested on both sides. The series on the LHS states to start at $0$, square $0$, and stop. The RHS is simply plug and chug.

For $n=0$, the left-hand side (LHS) yields:

$$\sum_{k=0}^{0} k^{2} = 0^{2} = 0.$$

And the right-hand side (RHS) yields:

$$\dfrac{0(0+1)(2 \cdot 0 + 1)}{6}=0.$$

So the equation holds on both sides for $n=0$.

2. Assume the result for $n$. ⊕ With the Basis step verified in Step 1, we assume the result to be true for $n$, and restate the original problem.

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

3. Prove the result for $(n+1)$. ⊕ "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."

\begin{align*} \sum_{k=0}^{n} k^{2} + (n+1)^{2} &= \dfrac{(n+1)((n+1)+1)(2(n+1)+1)}{6}\\ &= \dfrac{(n+1)(n+2)(2n+2+1)}{6}\\ &= \dfrac{(n+1)(n+2)(2n+3)}{6}. \end{align*}

NOTE: Recall that the sum of squares formula on the LHS starts at $0$, ends after the n-th value is squared and added, and is supposedly equivalent to the algebra on the RHS. For the LHS and RHS to stay equal to each other, any changes made to one side must also be made to the other side. Adding, subtracting, multiplying, or dividing a number on the LHS, must also be done to the opposite side to preserve equality. Observe the last number in the sum of squares formula is $n$, the "current thing." Since $n$ can be any number we want that's $\ge 0$, what would be the NEXT number after $n$?

That number would be $\mathbf{(n+1)}$, or the "next thing" we'll try to coax out from the "current thing." And since we need to square the next number prior to adding it to the series, we'll have to add $\mathbf{(n+1)^{2}}$ to both sides of the equation. But instead of tacking on $\mathbf{(n+1)^{2}}$ to the RHS (we'll do this in the next step, the proof itself) as we did to the LHS, we're going to use the RHS of Step 2, and carefully insert and replace all instances of $n$ with $n+1$, and simplify. Since the formula claims to work for all $n \ge 0$, then it should also work for $n+1$, the next number after the n-th number.

So the proof in the next step must show that the result is equal to

\begin{align*} \dfrac{(n+1)(n+2)(2n+3)}{6}, \end{align*}

or the proof fails.

4. Proof ⊕ Each line must be justified, beginning with the Induction Hypothesis, or what we're trying to prove. The rest is algebra and simplification. Notice in the next to last line of the proof, the result must look the same as what was found in Step 3. If pressed for time on a test and can't factor the cubic polynomial quickly, just go back to Step 3, F.O.I.L. and multiply out the terms on scratchpaper to see if the cubic polynomial is the same as what you got in Step 4. If they're equal, then you've got it, and can finish the proof with writing the cubic polynomial in factored form.

\begin{align*} \sum_{k=0}^{n} k^{2} + (n+1)^{2} &= \dfrac{n(n+1)(2n+1)}{6} + (n+1)^{2} && \text{(Induction Hypothesis)}\\ &= \dfrac{n(n+1)(2n+1)+6(n+1)^{2}}{6} && \text{(Algebra)}\\ &= \dfrac{(n^{2} + n)(2n+1)+6(n+1)(n+1)}{6} && \text{(Algebra)}\\ &= \dfrac{2n^{3} + n^{2} + 2n^{2} + n + 6n^{2} + 12n + 6}{6} && \text{(Algebra)}\\ &= \dfrac{2n^{3} + 9n^{2} + 13n + 6}{6} && \text{(Algebra)}\\ &= \dfrac{(n+1)(n+2)(2n+3)}{6}. && \text{(Algebra)} \end{align*}

5. Conclusion

This proves the result for $(n+1)$, so the result is true for all $n \ge 0$ by induction. $\Box$ ⊕ The proof is finished with a concluding statement.

NOTE: Focusing on the algebra, what induction shows is that inserting the "next thing" into the "current thing" of the formula's RHS representation is equivalent to adding the square of the "next thing" to the "current thing." Amazing!

$$\dfrac{(n+1)(n+2)(2n+3)}{6} = \dfrac{n(n+1)(2n+1)}{6} + (n+1)^{2}.$$