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

From Math Wiki
Jump to navigation Jump to search

Sigma Notation

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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1+2+\cdots+13. }

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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {\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 (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\Sigma\right) } , is the letter Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i } , and the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i } that follows the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Sigma } is our rule to apply to each value of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i } . The values Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 } and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 13 } tell us how many times to repeat the rule, i.e., to follow the rule for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i=1, } then add the rule for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i=2, } then for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i=3, } and continue in this manner until you reach Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 13} . In other words,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {\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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {\displaystyle \sum_{i=n}^{2n}}\, i\,=\, n+(n+1)+\cdots+(2n-1)+2n, }

or

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{N} } ), 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,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1} ), and then show whenever it's true for an arbitrary it's true for as well. This mimics our development of the natural numbers.

It is also equivalent to prove that whenever the conjecture is true for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-1, } it's true for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^{\mathrm{th}} } case requires assuming more than just the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n-1)^{\textrm{th}} } case. In such situations, strong induction assumes that the conjecture is true for ALL cases of lower value than Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n } down to our base case.

The Sum of the first n Natural Numbers

Claim. The sum of the first Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n } natural numbers is

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=1, } and plugging in we find that

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {\displaystyle \frac{n(n+1)}{2}\,=\,\frac{1(1+1)}{2}\,=\,1,} }

Which is clearly the sum of the single integer Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1} . This gives us our starting point. For the induction step, let's assume the claim is true for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-1, } so

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \square}

The Sum of the first n Squares

Claim. The sum of the first Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n } squares is

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=1,}   and plugging in we find that

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-1, } so

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {\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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \square}

The Sum of the first n Cubes

Claim. The sum of the first Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n } cubes is

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n } natural numbers.


Proof. Plugging in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=1, } we find that

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-1, } so

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \square}

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.

Retrieved from "https://wiki.math.ucr.edu/index.php?title=An_Introduction_to_Mathematical_Induction:_The_Sum_of_the_First_n_Natural_Numbers,_Squares_and_Cubes.&oldid=1022"