We begin this section with some important notation. Summation notation, written \(\sum_{i=1}^{j} i\), represents a sum. Here, \(i\) is called the index of the sum, and we add iterations until \(i=j\). For example, \[\sum_{i=1}^{j} i = 1 + 2 + \cdots + j\nonumber \] Another example: \[a_{11} + a_{12} + a_{13} = \sum_{i=1}^{3} a_{1i}\nonumber \]
The following notation is a specific use of summation notation.
Notation \(\PageIndex{1}\): Summation Notation
Let \(a_{ij}\) be real numbers, and suppose \(1\leq i\leq r\) while \(1\leq j\leq s\). These numbers can be listed in a rectangular array as given by \[\begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1s} \\ a_{21} & a_{22} & \cdots & a_{2s} \\ \vdots & \vdots & & \vdots \\ a_{r1} & a_{r2} & \cdots & a_{rs} \end{array}\nonumber \]
Then \(\sum_{j=1}^{s}\sum_{i=1}^{r} a_{ij} \) means to first sum the numbers in each column (using \(i\) as the index) and then to add the sums which result (using \(j\) as the index). Similarly, \(\sum_{i=1}^{r}\sum_{j=1}^{s} a_{ij} \) means to sum the vectors in each row (using \(j\) as the index) and then to add the sums which result (using \(i\) as the index).
Notice that since addition is commutative,
\[\sum_{j=1}^{s}\sum_{i=1}^{r} a_{ij} = \sum_{i=1}^{r}\sum_{j=1}^{s} a_{ij}. \nonumber\]
We now consider the main concept of this section. Mathematical induction and well ordering are two extremely important principles in math. They are often used to prove significant things which would be hard to prove otherwise.
Definition \(\PageIndex{1}\): A set is well ordered if every nonempty subset \(S,\) contains a smallest element \(z\) having the property that \(z\leq x\) for all \(x\in S.\)
In particular, the set of natural numbers defined as \[\mathbb{N} = \left\{ 1,2,\cdots \right\}\nonumber \] is well ordered.
Consider the following proposition.
Proposition \(\PageIndex{1}\): Well Ordered Sets Any set of integers larger than a given number is well ordered.
This proposition claims that if a set has a lower bound which is a real number, then this set is well ordered.
Further, this proposition implies the principle of mathematical induction. The symbol \(\mathbb{Z}\) denotes the set of all integers. Note that if \(a\) is an integer, then there are no integers between \(a\) and \(a+1.\)
Theorem \(\PageIndex{1}\): Mathematical Induction A set \(S\subseteq \mathbb{Z},\) having the property that \(a\in S\) and \(n+1\in S\) whenever \(n\in S\), contains all integers \(x\in \mathbb{Z}\) such that \(x\geq a.\)
Proof
Let \(T\) consist of all integers larger than or equal to \(a\) which are not in \(S.\) The theorem will be proved if \(T=\emptyset .\) If \(T\neq \emptyset\) then by the well ordering principle, there would have to exist a smallest element of \(T,\) denoted as \(b.\) It must be the case that \(b>a\) since by definition, \(a\notin T.\) Thus \(b\geq a+1\), and so \(b-1\geq a\) and \(b-1\notin S\) because if \(b-1\in\) \(S,\) then \(b-1+1=b\in S\) by the assumed property of \(S.\) Therefore, \(b-1\in T\) which contradicts the choice of \(b\) as the smallest element of \(T.\) (\(b-1\) is smaller.) Since a contradiction is obtained by assuming \(T\neq \emptyset ,\) it must be the case that \(T=\emptyset\) and this says that every integer at least as large as \(a\) is also in \(S\).
Mathematical induction is a very useful device for proving theorems about the integers. The procedure is as follows.
Procedure \(\PageIndex{1}\): Suppose \(S_{n}\) is a statement which is a function of the number \(n\), for \(n=1,2,\cdots\), and we wish to show that \(S_{n}\) is true for all \(n \geq 1\). To do so using mathematical induction, use the following steps.
Base Case: Show \(S_{1}\) is true.Assume \(S_{n}\) is true for some \(n\), which is the induction hypothesis . Then, using this assumption, show that \(S_{n+1}\) is true.
Proving these two steps shows that \(S_{n}\) is true for all \(n = 1,2,\cdots\).
We can use this procedure to solve the following examples.
Example \(\PageIndex{1}\): Prove by induction that \(\sum_{k=1}^{n}k^{2}=\displaystyle \frac{n\left( n+1\right) \left( 2n+1\right) }{6}\).
Solution
By Procedure \(\PageIndex{1}\) , we first need to show that this statement is true for \(n=1\). When \(n=1\), the statement says that \[\begin{aligned} \sum_{k=1}^{1}k^{2}&=\frac{1\left( 1+1\right) \left( 2(1)+1\right) }{6}\\ &=\frac{6}{6} \\ &=1\end{aligned}\]
The sum on the left hand side also equals \(1\), so this equation is true for \(n=1\).
Now suppose this formula is valid for some \(n\geq 1\) where \(n\) is an integer. Hence, the following equation is true.
\[\sum_{k=1}^{n}k^{2}= \frac{n\left( n+1\right) \left( 2n+1\right) }{6} \label{induction1}\]
We want to show that this is true for \(n+1\).
Suppose we add \((n+1)^2\) to both sides of Equation \(\eqref{induction1}\). \[\begin{aligned} \sum_{k=1}^{n+1}k^{2}&=\sum_{k=1}^{n}k^{2}+\left( n+1\right) ^{2} \\ &=\frac{n\left( n+1\right) \left( 2n+1\right) }{6}+\left( n+1\right) ^{2}\end{aligned}\]
The step going from the first to the second line is based on the assumption that the formula is true for \(n.\) Now simplify the expression in the second line, \[\frac{n\left( n+1\right) \left( 2n+1\right) }{6}+\left( n+1\right) ^{2}\nonumber \]
This equals \[\left( n+1\right) \left( \frac{n\left( 2n+1\right) }{6}+\left( n+1\right) \right)\nonumber \] and \[\frac{n\left( 2n+1\right) }{6}+\left( n+1\right) =\frac{6\left( n+1\right) +2n^{2}+n}{6}=\frac{ \left( n+2\right) \left( 2n+3\right) }{6}\nonumber \]
Therefore, \[\sum_{k=1}^{n+1}k^{2}=\frac{ \left( n+1\right) \left( n+2\right) \left( 2n+3\right) }{6}=\frac{ \left( n+1\right) \left( \left( n+1\right) +1\right) \left( 2\left( n+1\right) +1\right) }{6}\nonumber \] showing the formula holds for \(n+1\) whenever it holds for \(n.\) This proves the formula by mathematical induction. In other words, this formula is true for all \(n = 1, 2, \cdots\).
Consider another example.
Example \(\PageIndex{2}\): Show that for all \(n\in \mathbb{N}\), \(\displaystyle \frac{1}{2}\cdot \displaystyle \frac{3}{4}\cdots \displaystyle \frac{2n-1}{2n}<\displaystyle \frac{1}{\sqrt{2n+1}}.\)
Solution
Again we will use the procedure given in Procedure \(\PageIndex{1}\) to prove that this statement is true for all \(n\). Suppose \(n=1\). Then the statement says \[\frac{1}{2}< \frac{1}{\sqrt{3}}\nonumber \] which is true.
Suppose then that the inequality holds for \(n.\) In other words, \[\frac{1}{2}\cdot \frac{3}{4}\cdots \frac{2n-1}{2n} < \frac{1}{\sqrt{2n+1}}\nonumber \] is true.
Now multiply both sides of this inequality by \(\frac{2n+1}{2n+2}\). This yields \[\frac{1}{2}\cdot \frac{3}{4}\cdots \frac{2n-1}{2n}\cdot \frac{2n+1}{2n+2}< \frac{1}{\sqrt{2n+1}}\frac{2n+1}{2n+2}=\frac{\sqrt{2n+1}}{2n+2}\nonumber \]
The theorem will be proved if this last expression is less than \(\displaystyle\frac{1}{\sqrt{2n+3}}.\) This happens if and only if \[\left( \frac{1}{\sqrt{2n+3}}\right) ^{2}=\frac{1}{2n+3}>\frac{2n+1}{\left( 2n+2\right) ^{2}}\nonumber \] which occurs if and only if \(\left( 2n+2\right) ^{2}>\left( 2n+3\right) \left( 2n+1\right)\) and this is clearly true which may be seen from expanding both sides. This proves the inequality.
Let’s review the process just used. If \(S\) is the set of integers at least as large as \(1\) for which the formula holds, the first step was to show \(1\in S\) and then that whenever \(n\in S,\) it follows \(n+1\in S.\) Therefore, by the principle of mathematical induction, \(S\) contains \([1,\infty )\cap \mathbb{Z} ,\) all positive integers. In doing an inductive proof of this sort, the set \(S\) is normally not mentioned. One just verifies the steps above.
