View source for 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
<br>

:: <math style="vertical-align: 0px">1+2+3+4+5+6+7+8+9+10+11+12+13, </math>

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

:: <math style="vertical-align: 0px">1+2+\cdots+13. </math>

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

:: <math style="vertical-align: 0px">{\displaystyle \sum_{i=1}^{13}\, i,} </math> 

this means the same thing as the previous two mathematical statements.
Here, the '''index''' below the capital sigma, <math style="vertical-align: -5px">\left(\Sigma\right) </math>, is the letter <math style="vertical-align: 0px">i </math>, and the <math style="vertical-align: 0px">i </math> that follows the <math style="vertical-align: 0px">\Sigma </math> is our '''rule''' to
apply to each value of <math style="vertical-align: 0px">i </math> within the limits. The limits <math style="vertical-align: -1px">1 </math> and <math style="vertical-align: -1px">13 </math> tell us how many times to repeat the rule, i.e., to follow the rule for <math style="vertical-align: -4px">i=1, </math>
then add the rule for <math style="vertical-align: -4px">i=2, </math> then for <math style="vertical-align: -4px">i=3, </math> and continue in this
manner until you reach <math style="vertical-align: -1px">i=13.</math> In other words, 

:: <math style="vertical-align: 0px">{\displaystyle \sum_{i=1}^{13}}\, i\,=\,1+2+3+4+5+6+7+8+9+10+11+12+13. </math> 

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

:: <math style="vertical-align: 0px">{\displaystyle \sum_{i=1}^{5}}\, i^{2}\,=\,1^{2}+2^{2}+3^{2}+4^{2}+5^{2}. </math> 

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

:: <math style="vertical-align: 0px">{\displaystyle \sum_{i=n}^{2n}}\, i\,=\, n+(n+1)+\cdots+(2n-1)+2n, </math> 

or

:: <math style="vertical-align: 0px">{\displaystyle \sum_{i=1}^{n}}\, i^{3}\,=\,1^{3}+2^{3}+3^{3}+\cdots+n^{3}. </math> 

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 <math style="vertical-align: 0px">\mathbb{N} </math>), we begin with one, then keep adding one unit at a
time to get the next natural number. We then add one to that result to get the next natural number, and continue in this manner.  In other words, 
<br>

::<math style="vertical-align: 0px"> \text{The Natural Numbers}\,=\,\mathbb{N}\,=\,\{1,2,3,\ldots\}\,=\,\{1,1+1,1+1+1,1+1+1+1,\ldots\}. </math>

This is the basis for weak, or simple induction; we must first prove our conjecture is true for the lowest value (such as <math style="vertical-align: -1px">1</math>), and then
show whenever it's true for an arbitrary <math style="vertical-align: -4px">n, </math> it's true for <math style="vertical-align: -2px">n+1 </math>
as well. This mimics our development of the natural numbers. 

It is also equivalent to prove that whenever the conjecture is true for <math style="vertical-align: -4px">n-1, </math> it's true for <math style="vertical-align: 0px">n. </math> Which approach you choose can depend on which is more convenient, or possibly which is more appealing to the teacher grading the work.  We will use this style for the proofs on this page.

Although we won't show examples here, there are induction proofs that require '''strong induction'''. This occurs when proving it for the <math style="vertical-align: -5px">(n+1)^{\textrm{th}} </math> case requires assuming more than just the <math style="vertical-align: 0px">n^{\mathrm{th}} </math>
case. In such situations, strong induction assumes that the conjecture is true for ALL cases from <math style="vertical-align: 0px">n </math> down to our base case.

== The Sum of the first ''n'' Natural Numbers ==

'''''Claim.''''' The sum of the first <math style="vertical-align: 0px">n </math> natural numbers is 

:: <math style="vertical-align: 0px">{\displaystyle \sum_{i=1}^{n}i\,=\,1+2+\cdots+n\,=\,\frac{n(n+1)}{2}.} </math>


'''''Proof.''''' We must follow the guidelines shown for induction arguments.
Our base step is <math style="vertical-align: -4px">n=1, </math>&thinsp; and plugging in we find that

:: <math style="vertical-align: 0px">{\displaystyle \frac{n(n+1)}{2}\,=\,\frac{1(1+1)}{2}\,=\,1,} </math>

Which is clearly the sum of the single integer <math style="vertical-align: -1px">1</math>. This gives us our starting point. For the induction step, let's assume
the claim is true for <math style="vertical-align: -4px">n-1, </math> so 

:: <math style="vertical-align: 0px">{\displaystyle \sum_{i=1}^{n-1}i\,=\,\frac{(n-1)\left(\left(n-1\right)+1\right)}{2}\,=\,\frac{(n-1)n}{2}.} </math>

Now, we have

:: <math style="vertical-align: 0px">\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} </math>

as required. 

<div style="text-align:right;"><math>\square</math></div>

== The Sum of the first ''n'' Squares ==

'''''Claim.''''' The sum of the first <math style="vertical-align: 0px">n </math> squares is 

:: <math style="vertical-align: 0px">{\displaystyle \sum_{i=1}^{n}i^{2}\,=\,1^{2}+2^{2}+\cdots+n^{2}\,=\,\frac{n(n+1)(2n+1)}{6}.} </math>


'''''Proof.''''' Again, our base step is <math style="vertical-align: -4px">n=1,</math>&thinsp; and plugging in we find
that

:: <math style="vertical-align: 0px">{\displaystyle \frac{n(n+1)(2n+1)}{6}\,=\,\frac{1(1+1)(2+1)}{6}\,=\,1,} </math>

so the rule is certainly true when <math style="vertical-align: -1px">n=1.</math>

This gives us our starting point. For the induction step, let's assume
the claim is true for <math style="vertical-align: -4px">n-1, </math> so 

:: <math style="vertical-align: 0px">{\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}.} </math>

Now, we have

:: <math style="vertical-align: 0px">\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} </math>

as required. 

<div style="text-align:right;"><math>\square</math></div>

== The Sum of the first ''n'' Cubes == 

'''''Claim.''''' The sum of the first <math style="vertical-align: 0px">n </math> cubes is 

:: <math style="vertical-align: 0px">{\displaystyle \sum_{i=1}^{n}i^{3}\,=\,1^{3}+2^{3}+\cdots+n^{3}\,=\,\frac{n^{2}(n+1)^{2}}{4}.} </math>

Notice that the formula is really similar to that for the first <math style="vertical-align: 0px">n </math>
natural numbers.


'''''Proof.''''' Plugging in <math style="vertical-align: -4px">n=1, </math> we find that

:: <math style="vertical-align: 0px">{\displaystyle \frac{n^{2}(n+1)^{2}}{4}\,=\,\frac{1^{2}(1+1)^{2}}{4}\,=\,1,} </math>

completing our base step.

For the induction step, let's assume the claim is true for <math style="vertical-align: -4px">n-1, </math>
so 

:: <math style="vertical-align: 0px">{\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}}{4}.} </math>

Now, we have

:: <math style="vertical-align: 0px">\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} </math>

as required. 

<div style="text-align:right;"><math>\square</math></div>

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