An Introduction to Mathematical Induction: The Sum of the First n Natural Numbers, Squares and Cubes.

Sigma Notation

In math, we frequently deal with large sums. For example, we can write

$1+2+3+4+5+6+7+8+9+10+11+12+13,$

which is a bit tedious. Alternatively, we may use ellipses to write this as

$1+2+\cdots +13.$

However, there is an even more powerful shorthand known as sigma notation. When we write

${\displaystyle \sum _{i=1}^{13}\,i,}$

this means the same thing as the previous two mathematical statements. Here, the index below the capital sigma, Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \left(\Sigma \right)} , is the letter Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle i} , and the Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle i} that follows the $\Sigma$ is our rule to apply to each value of Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle i} . The values $1$ and $13$ tell us how many times to repeat the rule, i.e., to follow the rule for $i=1,$ then add the rule for $i=2,$ then for $i=3,$ and continue in this manner until you reach $13$. In other words,

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\displaystyle \sum _{i=1}^{13}}\,i\,=\,1+2+3+4+5+6+7+8+9+10+11+12+13.}

Of course, we can change the rule and/or the index. For example,

${\displaystyle \sum _{i=1}^{5}}\,i^{2}\,=\,1^{2}+2^{2}+3^{2}+4^{2}+5^{2}.$

Most importantly, we frequently don't have the luxury of bounds that are actual values. We can also write something like

${\displaystyle \sum _{i=n}^{2n}}\,i\,=\,n+(n+1)+\cdots +(2n-1)+2n,$

or

${\displaystyle \sum _{i=1}^{n}}\,i^{3}\,=\,1^{3}+2^{3}+3^{3}+\cdots +n^{3}.$

These non-fixed indices allow us to find rules for evaluating some important sums.

Proof by (Weak) Induction

When we count with natural or counting numbers (frequently denoted $\mathbb {N}$), we begin with one, then keep adding one unit at a time to get the next natural number. In other words,

${\text{The Natural Numbers}}\,=\,\mathbb {N} \,=\,\{1,2,3,\ldots \}\,=\,\{1,1+1,1+1+1,1+1+1+1,\ldots \}.$

This is the basis for weak, or simple induction; we must first prove our conjecture is true for the lowest value (such as $1$), and then show whenever it's true for an arbitrary $n,$ it's true for $n+1$ as well. This mimics our development of the natural numbers.

It is also equivalent to prove that whenever the conjecture is true for $n-1,$ it's true for $n.$ Which approach you choose can depend on which is more convenient, or frequently which is more appealing to the teacher grading the work.

Although we won't show examples here, there are induction proofs that require strong induction. This occurs when proving it for the Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle n^{\mathrm {th} }} case requires assuming more than just the $(n-1)^{\textrm {th}}$ case. In such situations, strong induction assumes that the conjecture is true for ALL cases of lower value than $n$ down to our base case.

The Sum of the first n Natural Numbers

Claim. The sum of the first $n$ natural numbers is

${\displaystyle \sum _{i=1}^{n}i\,=\,1+2+\cdots +n\,=\,{\frac {n(n+1)}{2}}.}$

Proof. We must follow the guidelines shown for induction arguments. Our base step is $n=1,$ and plugging in we find that

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\displaystyle {\frac {n(n+1)}{2}}\,=\,{\frac {1(1+1)}{2}}\,=\,1.}}

This gives us our starting point. For the induction step, let's assume the claim is true for $n-1,$ so

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\displaystyle \sum _{i=1}^{n-1}i\,=\,{\frac {(n-1)\left(\left(n-1\right)+1\right)}{2}}\,=\,{\frac {(n-1)n}{2}}.}}

Now, we have

${\begin{array}{rcl}{\displaystyle \sum _{i=1}^{n}i}&=&{\displaystyle \sum _{i=1}^{n-1}i\,+\,n}\\\\&=&{\displaystyle {\frac {(n-1)n}{2}}\,+\,n\qquad \qquad {\mbox{(by the induction assumption)}}}\\\\&=&{\displaystyle {\frac {n^{2}-n}{2}}\,+\,{\frac {2n}{2}}}\\\\&=&{\displaystyle {\frac {n^{2}-n+2n}{2}}}\\\\&=&{\displaystyle {\frac {n^{2}+n}{2}}}\\\\&=&{\displaystyle {\frac {n(n+1)}{2}}},\end{array}}$

as required.

$\square$

The Sum of the first $n$ Squares

Claim. The sum of the first $n$ squares is

${\displaystyle \sum _{i=1}^{n}i^{2}\,=\,1^{2}+2^{2}+\cdots +n^{2}\,=\,{\frac {n(n+1)(2n+1)}{6}}.}$

Proof. Again, our base step is $n=1,$ and plugging in we find that

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\displaystyle {\frac {n(n+1)(2n+1)}{6}}\,=\,{\frac {1(1+1)(2+1)}{6}}\,=\,1.}}

This gives us our starting point. For the induction step, let's assume the claim is true for $n-1,$ so

${\displaystyle \sum _{i=1}^{n-1}i\,=\,{\frac {(n-1)\left(\left(n-1\right)+1\right)\left(2\left(n-1\right)+1\right)}{6}}\,=\,{\frac {(n-1)n(2n-1)}{6}}\,=\,{\frac {2n^{3}-3n^{2}+n}{6}}.}$

Now, we have

${\begin{array}{rcl}{\displaystyle \sum _{i=1}^{n}i^{2}}&=&{\displaystyle \sum _{i=1}^{n-1}i^{2}+n^{2}}\\\\&=&{\displaystyle {\frac {2n^{3}-3n^{2}+n}{6}}+n^{2}\qquad \qquad {\mbox{(by the induction assumption)}}}\\\\&=&{\displaystyle {\frac {2n^{3}-3n^{2}+n}{6}}+{\frac {6n^{2}}{6}}}\\\\&=&{\displaystyle {\frac {2n^{3}+3n^{2}+n}{6}}}\\\\&=&{\displaystyle {\frac {n(2n^{2}+3n+1)}{6}}}\\\\&=&{\displaystyle {\frac {n(n+1)(2n+1)}{6}}},\end{array}}$

as required.

$\square$

The Sum of the first n Cubes

Claim. The sum of the first $n$ cubes is

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\displaystyle \sum _{i=1}^{n}i^{3}\,=\,1^{3}+2^{3}+\cdots +n^{3}\,=\,{\frac {n^{2}(n+1)^{2}}{4}}.}}

Notice that the formula is really similar to that for the first $n$ natural numbers.

Proof.. Plugging in $n=1,$ we find that

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\displaystyle {\frac {n^{2}(n+1)^{2}}{4}}\,=\,{\frac {1^{2}(1+1)^{2}}{4}}\,=\,1,}}

completing our base step.

For the induction step, let's assume the claim is true for $n-1,$ so

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\displaystyle \sum _{i=1}^{n-1}i^{3}\,=\,{\frac {(n-1)^{2}\left(\left(n-1\right)+1\right)^{2}}{4}}\,=\,{\frac {(n-1)^{2}n^{2}}{2}}.}}

Now, we have

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\begin{array}{rcl}{\displaystyle \sum _{i=1}^{n}i^{3}}&=&{\displaystyle \sum _{i=1}^{n-1}i^{3}+n^{3}}\\\\&=&{\displaystyle {\frac {(n-1)^{2}n^{2}}{4}}+n^{3}\qquad \qquad {\mbox{(by the induction assumption)}}}\\\\&=&{\displaystyle {\frac {n^{4}-2n^{3}+n^{2}}{4}}+{\frac {4n^{3}}{4}}}\\\\&=&{\displaystyle {\frac {n^{4}+2n^{3}+n^{2}}{4}}}\\\\&=&{\displaystyle {\frac {n^{2}(n^{2}+2n+1)}{4}}}\\\\&=&{\displaystyle {\frac {n^{2}(n+1)^{2}}{4}}},\end{array}}}

as required.

$\square$

Aside from being good examples of simple or weak induction, these formulas are frequently used to find an integral as a limit of a Riemann sum.