1.6 Problems on Natural Numbers and Induction

(i)

\(1^n=1\) in any field;

(ii)

\((\forall n \in \mathbb {N})\) \(2^n\geq 2\) in any ordered field; Specify the proposition \(P(n)\).

(i)\('\)

\(P(1)\) is true; From the inductive definition of \(n\)th power of any element \(x\) in field \(F\), we have \(1^1= 1\), hence \(P(1)\) holds.

(ii)\('\)

\(P(m)\implies P(m+1)\) ; If we assume \(P(n)\) holds for some particular \(n=m\), then we have \(1^m =1\), again by the inductive definition of natural powers, we have \(1^{m+1} = 1^m \cdot 1\). From our inductive hypothesis, we have \(1^{m+1}=1 \cdot 1 =1\) by the properties of neutral elements (Axiom IV). Thus, \(P(m+1)\) is true whenever \(P(m)\) is true.

Hence, by induction, \(1^n =1\) in any field, ordered or not, as we only used the general field axioms.
For (ii), we can set the induction proposition \(P(n)\) mean \(2^n \geq 2\).

(i)\('\)

\(P(1)\) is true; by the definition of natural powers, \(2^1=2 \geq 2\). Thus, \(P(1)\) holds.

(ii)\('\)

\(P(m)\implies P(m+1)\); If we assume \(P(n)\) holds for some \(n=m\), then we have \(2^m \geq 2\), because \(2>1\) (straight forward implication of \(1>0\), monotonicity of addition, and definition of “2”), by the monotonicity of multiplication, we have \(2^m \cdot 2 \geq 2 \cdot 1\), by the definition of natural powers, and the properties of neutral elements, \(2^{m+1}\geq 2\). Thus, \(P(m+1)\) holds if \(P(m)\) holds.

Hence, by induction, we have \(2^n\geq 2\) for all \(n \in \mathbb {N}\).

Assume this known for \(n=2\), and use induction on \(n\).

We have shown in Example (A), that if \(x_1,x_2 \in \mathbb {N}\) then, \(x_1+x_2 \in \mathbb {N}\) along with \(x_1x_2 \in \mathbb {N}\). We can let \(P(n)\) mean that \(\sum _{k=1}^n x_k \in \mathbb {N}\). For sums, we have:

(i)

\(P(2)\) is true; By definition of sums, we have \(\sum _{k=1}^2 x_k = \sum _{k=1}^1x_k+x_2= x_1+x_2\); Because \(x_1, x_2 \in \mathbb {N}\), by Example (A), \(x_1+x_2 \in \mathbb {N}\). Thus \(P(2)\) holds.

(ii)

\(P(m)\implies P(m+1)\); Assuming \(P(m)\) holds implies that \(\sum _{k=1}^m x_k \in \mathbb {N}\). By the definition of sum, \(\sum _{k=1}^{m+1} x_k = \sum _{k=1}^m x_k +x_{m+1}\). Because of the inductive hypothesis, \(\sum _{k=1}^m x_k \in \mathbb {N}\) and from our assumption, \(x_{m+1} \in \mathbb {N}\), thus \(\sum _{k=1}^{m+1} x_k\) is also a natural element of the field by Example (A). Thus \(P(m+1)\) is true when \(P(m)\) is true.

Similarly, for products of natural elements, Let \(P'(n)\) mean that \(\prod _{k=1}^{n}x_k \in \mathbb {N}\). with this we have:

(i)\('\)

\(P'(2)\) is true; Again by the definition of products, we have \(\prod _{k=1}^2 x_k = (\prod _{k=1}^1x_k) \cdot x_2 = x_1\cdot x_2\), which by Example (A), is also a natural element of the field.

(ii)\('\)

\(P'(m)\implies P'(m+1)\); Assuming \(P'(m)\) holds, we have \(\prod _{k=1}^{m}x_k \in \mathbb {N}\) and by definition of products, we have \(\prod _{k=1}^{m+1}x_k = (\prod _{k=1}^{m}x_k )\cdot x_{m+1}\), then from the inductive hypothesis and Example (A), we have \(\prod _{k=1}^{m+1}x_k \in \mathbb {N}\). Thus, \(P'(m+1)\) is true when \(P'(m)\) is true.

(i)

\(P(2)\) is true; By definition of sums, \(\sum _{k=1}^2 x_k = \sum _{k=1}^1x_k+x_2= x_1+x_2\); Because \(x_1>0\) and \(x_2>0\), by addition of inequalities, and properties of neutral elements, we have \(x_1+x_2 >0+0=0\). Thus, \(P(2)\) holds.

(ii)

\(P(m) \implies P(m+1)\); \(P(m)\) being true implies, \(\sum _{k=1}^m x_k>0\), choosing some \(x_{n+1}>0\), by the addition of inequalities, and properties of neutral elements, we have, \(\sum _{k=1}^m x_k +x_{m+1}>0\). Now, by the recursive definition of sums, \(0< \sum _{k=1}^m x_k +x_{m+1} = \sum _{k=1}^{m+1}x_k\). Hence, \(P(m+1)\) is true when \(P(m)\) is true.

Thus, the sum of all positive elements in an ordered field is also positive. Similarly for multiplication, define \(P'(n)\) to mean \(\prod _{k=1}^n x_k>0\).

(i)\('\)

\(P'(2)\) is true; by definition of products, \(\prod _{k=1}^2x_k = (\prod _{k=1}^1x_k)\cdot x_2=x_1\cdot x_2\). Because \(x_1>0\) and \(x_2>0\), by the monotonicity of multiplication (Axiom IX), \(x_1 \cdot x_2 > 0 \cdot x_2\). By Corollary 5 (\(x_2 \cdot 0 = 0 \cdot x_2 =0\)), we have \(x_1\cdot x_2 >0\), hence \(P'(2)\) holds.

(ii)\('\)

\(P'(m) \implies P'(m+1)\); \(P'(m)\) being true means that \(\prod _{k=1}^{m}x_k >0\), then choose some element \(x_{m+1}>0\), by the monotonicity of multiplication and Corollary 5 similar to reasoning in (i)\('\), \((\prod _{k=1}^{m}x_k)\cdot x_{m+1} >0\). By the recursive definition of products \(\prod _{k=1}^{m+1}x_k =(\prod _{k=1}^{m}x_k)\cdot x_{m+1} >0\). Hence, \(P'(m+1)\) holds when \(P'(m)\) is true.

Assume this known for \(n=2\).

(i)

\(P(2)\) is true; Again, by the recursive definition of products, \(\prod _{k=1}^2x_k = (\prod _{k=1}^1x_k)\cdot x_2=x_1\cdot x_2\), we need to show that \(x_1 \cdot x_2 \neq 0\). First, assume that opposite: \(x_1\cdot x_2 =0\), then we have, by field axioms and Corollary 5: \begin {align*} x_1\cdot x_2 &=0\\ x_1^{-1} \cdot (x_1x_2) &= x_1^{-1} \cdot 0\\ x_2=0 \end {align*}

But, this contradicts our assumption that \(x_1, x_2 \neq 0\). Thus, \(x_1\cdot x_2 \neq 0\). Hence \(P(2)\) holds.

(ii)

\(P(m) \implies P(m+1)\); If \(P(n)\) holds for some \(n=m\), then we have \(\prod _{k=1}^m x_k \neq 0\), then from the definition of products, we have \(\prod _{k=1}^{m+1} x_k = (\prod _{k=1}^m x_k)\cdot x_{m+1}\), we need to show that \((\prod _{k=1}^m x_k)\cdot x_{m+1} \neq 0\). Similar to the logic used in (i), by assuming that \((\prod _{k=1}^m x_k)\cdot x_{m+1} = 0\), we can show that this would imply either \(\prod _{k=1}^m x_k =0\) or \(x_{m+1} = 0\), which is impossible from construction, hence \(P(m+1)\) holds whenever \(P(m)\) holds.

Thus, the (finite) product of nonzero elements of a field is also nonzero. Now, we have to show that: \begin {align*} \left (\prod _{k=1}^n x_k \right )^{-1} = \prod _{k=1}^n x_k^{-1} \end {align*}

This expression implies that \(\prod _{k=1}^n x_k^{-1}\) is the multiplicative inverse of \(\prod _{k=1}^n x_k \). Note that it only now makes sense to talk about the multiplicative inverse after we have shown that the expression is nonzero, hence the inverse is defined. We again use induction here with the proposition \(P'(n)\) here meaning: \begin {align*} \left (\prod _{k=1}^n x_k\right ) \cdot \left (\prod _{k=1}^n x_k^{-1}\right ) = 1. \end {align*}

Thus,

(i)\('\)

\(P'(2)\) is true; By the recursive definition of products, we have \((\prod _{k=1}^n x_k) \cdot (\prod _{k=1}^n x_k^{-1}) = (x_1x_2)\cdot (x_1^{-1}x_2^{-1})\). By commutativity and associativity and the properties of inverses and neutral elements, we have \((x_1x_2)\cdot (x_1^{-1}x_2^{-1}) = (x_1x_1^{-1})\cdot (x_2x_2^{-1})= 1\cdot 1 =1\), thus \(P'(2)\) is true.

(ii)\('\)

\(P'(m) \implies P'(m+1)\); If \(P'(m)\) holds, then: \begin {gather*} \left (\prod _{k=1}^m x_k\right ) \cdot \left (\prod _{k=1}^m x_k^{-1}\right ) = 1\\ \because \prod _{k=1}^{m+1} x_k = \left (\prod _{k=1}^m x_k\right ) \cdot x_{m+1}\;\;\text {and}\;\; \prod _{k=1}^{m+1} x_k^{-1} = \left (\prod _{k=1}^m x_k^{-1}\right ) \cdot x^{-1}_{m+1}\\ \implies \left (\prod _{k=1}^{m+1} x_k\right ) \cdot \left (\prod _{k=1}^{m+1} x_k^{-1}\right ) = \left [\left (\prod _{k=1}^m x_k\right ) \cdot x_{m+1} \right ]\cdot \left [ \left (\prod _{k=1}^m x_k^{-1}\right ) \cdot x^{-1}_{m+1}\right ] \\ = \left [ \left (\prod _{k=1}^m x_k\right ) \cdot \left (\prod _{k=1}^m x_k^{-1}\right )\right ] \cdot [x_{m+1}\cdot x^{-1}_{m+1}] \end {gather*} By, the inductive hypotheses, we have \(\left (\prod _{k=1}^m x_k\right ) \cdot \left (\prod _{k=1}^m x_k^{-1}\right ) =1\), also by the properties of fields, we have \(x_{m+1}\cdot x^{-1}_{m+1} =1\), thus indeed, we have: \begin {align*} \left (\prod _{k=1}^{m+1} x_k\right ) \cdot \left (\prod _{k=1}^{m+1} x_k^{-1}\right ) = 1 \end {align*}

Hence, by the theorem of induction, \(P'(n)\) holds for all \(n\geq 2\). Note that we still have not completed the proof. Now we have these two true equations: \begin {align*} \left (\prod _{k=1}^{n} x_k\right ) \cdot \left (\prod _{k=1}^n x_k \right )^{-1} =1\\ \left (\prod _{k=1}^{n} x_k\right ) \cdot \left (\prod _{k=1}^{n} x_k^{-1}\right ) = 1 \end {align*}

Hence, \begin {align*} \left (\prod _{k=1}^{n} x_k\right ) \cdot \left (\prod _{k=1}^n x_k \right )^{-1} = \left (\prod _{k=1}^{n} x_k\right ) \cdot \left (\prod _{k=1}^{n} x_k^{-1}\right ) \end {align*}

because of our earlier proof that the product is not zero, by the cancellation of the same element (Cancellation Corollary), we finally have: \begin {align*} \left (\prod _{k=1}^n x_k \right )^{-1} = \left (\prod _{k=1}^{n} x_k^{-1}\right ) \end {align*}

for any non zero \(n\) elements \(x_1,\ldots , x_n\) of a field (both ordered and unordered).

(i)

\(P(2)\) is true; By the definition of sums we have \(c(\sum _{k=1}^n x_k ) = c\cdot ( x_1 +x_2)\). By the distributive property of elements in a ordered field, we have \(c(x_1+x_2)=cx_1+cx_2\), which is equal to \(\sum _{k=1}^n cx_k\). Thus, \(P(2)\) holds.

(ii)

\(P(m)\implies P(m+1)\); This means that \(c(\sum _{k=1}^m x_k ) = \sum _{k=1}^m cx_k\). Hence, by the definition of sums and the distributive property, we have \(c(\sum _{k=1}^{m+1} x_k )= c(\sum _{k=1}^{m} +x_{m+1})= c\sum _{k=1}^{m}x_k + cx_{m+1}\), by the inductive hypothesis and the definition of sums, we have \(c\sum _{k=1}^{m}x_k + cx_{m+1} = \sum _{k=1}^{m}cx_k + cx_{m+1} = \sum _{k=1}^{m+1}cx_k\). Thus, \(P(m+1)\) is true if \(P(m)\) is true.

Hence, (i), is shown to be true. for (ii), we again let \(P'(n)\) when \(\sum _{k=1}^n (x_k\pm y_k) = \sum _{k=1}^n x_k \pm \sum _{k=1}^n y_k\).

(i)\('\)

\(P(2)'\) is true; By the definition of sums, we have \(\sum _{k=1}^2 (x_k\pm y_k)=(x_1\pm y_1)+(x_2\pm y_2)\), by associativity and commutativity, we have \((x_1+x_2)\pm (y_1+y_2)\), then by the definition of sums, \((x_1+x_2)\pm (y_1+y_2)= \sum _{k=1}^2 x_k \pm \sum _{k=1}^2 y_k\). Thus, \(P'(2)\) is true.

(ii)\('\)

\(P'(m)\implies P'(m+1)\); We have \(P'(m)\) holding, hence, \(\sum _{k=1}^m (x_k\pm y_k) = \sum _{k=1}^m x_k \pm \sum _{k=1}^m y_k\), when \(n=m+1\), we have: \(\sum _{k=1}^{m+1} (x_k\pm y_k)= \sum _{k=1}^m (x_k\pm y_k)+ (x_{m+1}\pm y_{m+1})\), and from the inductive hypothesis, we have \((\sum _{k=1}^m x_k \pm \sum _{k=1}^m y_k)+(x_{m+1}\pm y_{m+1})\), by associativity and commutativity, we get the desired result, thus \(P'(m+1)\) holds when \(P'(m)\) holds.

(i)

\(P(2)\) is true; Again, by the definition of sums, we have \(| \sum _{k=1}^2 x_k |= |x_1+x_2|\), and by the triangle inequality, we have, \(|x_1+x_2| \leq |x_1|+|x_2|\). This, again by the definition of sums, is just \(\sum _{k=1}^2 |x_k|\). Thus, \(P(2)\) is true.

(ii)

\(P(m)\implies P(m+1)\); Assuming \(P(m)\) holds means that \(| \sum _{k=1}^m x_k | \leq \sum _{k=1}^m |x_k|\), for the \(m+1\) case we have, by definition of sums and triangle inequality: \begin {align*} \left | \sum _{k=1}^{m+1} x_k \right |= \left | \sum _{k=1}^{m} x_k +x_{m+1}\right | \leq \left |\sum _{k=1}^{m} x_k\right |+|x_{m+1}| \end {align*}

But, from the inductive hypothesis, \begin {align*} \left | \sum _{k=1}^{m+1} x_k \right | \leq \left |\sum _{k=1}^{m} x_k\right |+|x_{m+1}| \leq \sum _{k=1}^m |x_k| +|x_{m+1}|= \sum _{k=1}^{m+1} |x_k| \end {align*}

Thus, \(P(m+1)\) holds when \(P(m)\) holds.

given that \(a,b \geq 0\) for all \(n\in \mathbb {N}\). Now, we prove \(P(n)\):

(i)

\(P(1)\) is true; we are given, \(a<b\). From the inductive definition of \(a^1 = a\) and \(b^1 =b\), thus, \(a^1=a < b = b^1\), hence \(a^1<b^1\), showing that \(P(1)\) holds.

(ii)

\(P(m) \implies P(m+1)\); assuming \(P(n)\) holds for some \(m\), we have \(a<b \implies a^m <b^m\). For \(m+1\), we have \(a^{m+1} = a^ma\), from the definition of natural powers. We also have \(a<b\) from the proposition, thus, \(a^{m+1}=a^ma<b^ma<b^mb=b^{m+1}\), hence \(a^{m+1}<b^{m+1}\). Thus, \(P(m+1)\) is true when \(P(m)\) holds.

By, the principle of induction, given \(a,b\geq 0\), \(a<b \implies a^n <b^n\) for all natural \(n\) of an ordered field. For \(P'(n)\), we use the second induction law, to simply:

(i)

\(P'(1)\) is true; we are given \(a^1<b^1\), but by the definition of natural powers, we have \(a^1=a\) and \(b^1=b\), thus, \(a<b\) as required, showing that \(P'(1)\) holds.

(ii)

\(P'(1), \ldots , P'(m-1) \implies P'(m)\); by assuming \(P'(n)\) holds for all \(n < m\), specifically holding for \(n=1\) and \(n=m-1\), we have: \begin {align*} a^{1}<b^{1} \implies a<b, \\ a^{m-1}<b^{m-1} \implies a<b \end {align*}

with, \(a^m=a^{m-1}\cdot a^1<b^{m-1}\cdot a < b^{m-1} \cdot b = b^{m}\), thus, from \(P'(1)\) and \(P'(m-1)\) we have \(a^m<b^m\) also implying that \(a<b\).

Hence, by the principle of induction, given \(a,b\geq 0\), for any natural element \(n\) of an ordered field, \(a^n<b^n\) implies \(a<b\).
We now have shown that, given \(a,b \geq 0\), for any natural \(n\) of a field: \begin {align*} a<b \iff a^n<b^n \end {align*}

if \(a<1\), we have \(a^n<1^n\), which from Problem 1. we know that \(1^n=1\), thus, \(a^n<1\), the same reasoning holds for the \(a>1\) case, giving \(a^n>1^n=1\).

Note that for \(P'(n)\) we can prove the contrapositive \(a\geq b \implies a^n > b^n\), thus proving the original statement much more easily.

(i)

\((1+\epsilon )^n \geq 1 +n\epsilon \) if \(\epsilon >-1\)

(ii)

\((1-\epsilon )^n \geq 1 -n\epsilon \) if \(\epsilon <1\)

These are Bernoulli Inequalities. Infer that \(2^n >n\), \(n=1,2,\ldots ,\) in \(\mathbb {R}\).

(i)

\(P(1)\) is true; we have by the definition of natural powers, \((1+\epsilon )^1=1+\epsilon \), this trivially shows that \(P(1)\) is true.

(ii)

\(P(m)\implies P(m+1)\); if \(P(m)\), then \((1+\epsilon )^m \geq 1 +m\e \), because we assume that \(\epsilon >-1\), we have \(\epsilon -1>0\), thus by the monotonicity of multiplication, \((1+\epsilon )^m(1+\epsilon ) \geq (1+m\epsilon )(1+\epsilon )\). Hence, we have \((1+\epsilon )^{m+1} \geq 1+m\epsilon +\epsilon +m\epsilon ^2 > 1+(m+1)\epsilon \). Thus, we have shown that \(P(m+1)\) whenever \(P(m)\) is true.

By similar reasoning, we can also show (ii). Thus, when \(\epsilon =1\), \((1+1)^n \geq 1+n \implies 2^n\geq 1+n>n\).

(i)

\(P(1)\) is true; we have, for \(n=1\), \(a^{1+1}-b^{1+1}=a^2-b^2\), from earlier exercise, we have shown that this is equal to \((a-b)\cdot (a+b)\), but this is equal to \((a-b)\cdot \sum _{k=0}^1 a^kb^{n-k}\). Thus, \(P(1)\) holds.

(ii)

\(P(m)\implies P(m+1)\); Here, we have \(a^{m+1}-b^{m+1}= (a-b)\cdot \sum _{k=0}^m a^kb^{m-k}\) holding. Consider the case when \(n=m+1\) on RHS: \begin {align*} (a-b)\cdot \sum _{k=0}^{m+1} a^kb^{(m+1)-k}&=(a-b)\cdot \left [b\sum _{k=0}^{m} a^kb^{m-k} +a^{m+1}b^0 \right ] \end {align*}

from the inductive hypothesis, we have \(\sum _{k=0}^m a^kb^{m-k} = \dfrac {a^{m+1}-b^{m+1}}{a-b}\), thus, we have: \begin {align*} (a-b)\cdot \sum _{k=0}^{m+1} a^kb^{(m+1)-k}&= (a-b)\cdot \left [ b\cdot \frac {a^{m+1}-b^{m+1}}{a-b} +a^{m+1}\right ]\\ &=a^{(m+1)+1}-b^{(m+1)+1} \end {align*}

Hence, \(P(m+1)\) holds.

(I)

\(1+2+\cdots +n= \frac {1}{2}n(n+1)\);

(II)

\(\sum _{k=1}^n k^2 = \frac {1}{6}n(n+1)(2n+1)\);

(III)

\(\sum _{k=1}^n k^3 = \frac {1}{4}n^2(n+1)^2\);

(IV)

\(\sum _{k=1}^n k^4 = \frac {1}{30}n(n+1)(2n+1)(3n^2+3n-1)\).

(i)

\(P(1)\) is true; \(\sum _{k=1}^1k = 1 = \frac {1}{2}\cdot 1 \cdot 2=1\), thus \(P(1)\) holds.

(ii)

\(P(m)\implies P(m+1)\); if \(P(m)\) holds, then, \(\sum _{k=1}^m k = \frac {m}{2}(m+1)\), adding \(m+1\) to both sides, we get the desired result: \(\sum _{k=1}^{m+1} k = \frac {(m+1)}{2}((m+1)+1)\). Hence, \(P(n)\) holds for all natural \(n\).

For (II), (III) and (IV) we can show this with the same identity.

(i)

\(P(1)\) is true; \(a^ma^1=a^{m+1}\) by the definition of natural powers. Thus \(P(1)\) holds.

(ii)

\(P(k)\implies P(k+1)\); Given \(a^ma^k = a^{m+k}\), when \(n=k+1\), we have \(a^{m+k+1}= a^{(m+k)+1}=a^{m+k}\) by the definition of natural powers, the result of which, by the inductive hypothesis, is just \(a^ma^ka^1=a^ma^{k+1}\), thus, \(P(k+1)\) holds.

For (II), similarly, we have \(P(n)\) being true when \((a^m)^n=a^{mn}\).

(i)

\(P(1)\) is true; \((a^m)^1=a^m\), by the definition of natural powers, and now by properties of neutral elements, \(a^m = a^{m\cdot 1}\), thus, \(P(1)\) holds.

(ii)

\(P(k)\implies P(k+1)\); Given \((a^m)^k=a^{mk}\), for \(n=k+1\), we have \((a^m)^{k+1}=(a^m)^ka^m\), by the definition of natural powers. Now by the inductive hypothesis, we have \((a^m)^ka^m= a^{mk}a^m\), and from (I), we have \(a^{mk}a^m= a^{mk+m} = a^{m(k+1)}\), hence \(P(k+1)\) holds.

For (III), similarly, we have \(P(n)\) being true when \((ab)^n = a^nb^n\).

(i)

\(P(1)\) is true; \((ab)^1=ab\), by the definition of natural powers. Thus, \(P(1)\) trivially holds.

(ii)

\(P(m)\implies P(m+1)\) Given \((ab)^m=a^mb^m\), for \(n=m+1\), we have \((ab)^{m+1} = (ab)^m(ab)\), by the definition of natural powers. Then, from the inductive hypothesis, we have \((ab)^m(ab) = (a^mb^m)\cdot ab\), from which, we apply the commutative and associative properties of field elements proven in the last section, giving us \((a^mb^m)\cdot ab = a^{m+1}b^{m+1}\). Thus, \(P(m+1)\) holds.

For (IV), similarly, we have \(P(n)\) being true when \(\dfrac {a^n}{a^m}=a^{n-m}\).

(i)

\(P(1)\) is true; \(\dfrac {a^1}{a^m}=a^1\cdot a^{-m}\) by the definition of natural powers, then again by definition, \(a^1\cdot a^{-m}= a^{1-m}\). Thus, \(P(1)\) holds.

(ii)

\(P(k)\implies P(k+1)\); Given \(\dfrac {a^k}{a^m}=a^{k-m}\), for \(n=k+1\), we have \(\dfrac {a^{k+1}}{a^m}=\dfrac {a^k}{a^m}\cdot a^1\), then by the inductive hypothesis, we have \(\dfrac {a^k}{a^m}\cdot a^1 = a^{k-m}a^1\), which by definition is \(a^{(k+1)-m}\). Thus, \(P(k+1)\) holds if \(P(k)\) holds.

For (V), we have \(P(n)\) being true when \(\left (\dfrac {b}{a}\right )^n = \dfrac {b^n}{a^n}\).

(i)

\(P(1)\) is true; \(\left (\dfrac {b}{a}\right )^1 = \dfrac {b}{a}\) by the definition of natural powers, hence \(P(1)\) trivially holds.

(ii)

\(P(m)\implies P(m+1)\); Given \(\left (\dfrac {b}{a}\right )^m = \dfrac {b^m}{a^m}\), for \(n=m+1\), we have \(\left (\dfrac {b}{a}\right )^{m+1}= \left (\dfrac {b}{a}\right )^m \cdot \left (\dfrac {b}{a}\right )^1 = \dfrac {b^m}{a^m} \cdot \dfrac {b}{a}\), which by field properties and definition of natural powers, is \(\dfrac {b^{m+1}}{a^{m+1}}\), thus \(P(m+1)\) holds.

For (VI), we have \(P(n)\) being true when \(ma+na=(m+n)a\), holding \(m\) constant.

(i)

\(P(1)\) is true; \(ma+1\cdot a=ma+a\), from the definition of “natural multiplies” of field elements, we have \(ma+a=(m+1)a\); thus, \(P(1)\) holds.

(ii)

\(P(k)\implies P(k+1)\); Given \(ma+ka = (m+k)a\), for \(n=k+1\), we have \(ma+(k+1)a = ma+[ka+a]\) from the definition of natural multiplies. Them by the inductive hypothesis, \(ma+[ka+a] = (m+k)a +a\), then again by the definition, is equal to \([m+(k+1)]a\), proving \(P(k+1)\).

For (VII), we have \(P(n)\) being true when \(ma\cdot nb =(mn)(ab)\).

(i)

\(P(1)\) is true; \(ma \cdot (1\cdot b)=ma\cdot b = (m \cdot 1)(ab)\) by associativity and commutativity. Thus, \(P(1)\) holds.

(ii)

\(P(k)\implies P(k+1)\); Given \(ma\cdot kb = (mk)(ab)\), for \(n=k+1\), we have: \(ma\cdot (k+1)b=ma\cdot (kb+b) = ma\cdot kb + ma\cdot b\), which by the inductive hypothesis, we have \(ma\cdot kb +ma\cdot b=(mk)(ab)+m(ab)=(m(k+1))(ab)\), thus \(P(k+1)\) holds.

For (VII), we have \(P(n)\) being true when \(n(a\pm b) = na\pm nb\).

(i)

\(P(1)\) is true; We have \(1\cdot (a\pm b) =a\pm b\) by the definition of natural multiplies. But then, by the properties of neutral elements, \(a\pm b= 1\cdot a \pm 1\cdot b\). Thus, \(P(1)\) holds.

(ii)

\(P(m)\implies P(m+1)\); Given \(m(a\pm b)=ma \pm mb\), for \(n=m+1\), by the definition of natural multiplies, \((m+1)(a\pm b) = m(a\pm b)+ (a\pm b)\), which by the inductive hypothesis, is \((ma\pm mb)+(a\pm b)\), by associativity and commutativity, we have \((ma+a)\pm (mb+b)\), for which applying the definition of natural multiplies, we get \((m+1)a \pm (m+1)b\), showing that \(P(m+1)\) holds when \(P(m)\) holds.

Provided \(x>0\).

Note that, for any ordered field \(F\), \(1_F>0_F\), along with the fact each natural of \(F\) is \(\geq 1_F\).

To create a sound inductive proposition \(P(n)\) we need to make sure that, it includes these conditions:

1.

Existence: for each \(x \in \mathbb {N}_F\), we have some \(n \in \mathbb {N}_\mathbb {R}\), such that \(x=n\cdot 1_F \in \mathbb {N}_F\). Call the \(x\), \(x_n\), i.e., \(x_n :=n\cdot 1_F\).

2.

Uniqueness: this representation of \(x\) is unique, i.e., If \(m\) is some natural number of \(\mathbb {N}_\mathbb {R}\), then, \(m\cdot 1_F = n\cdot 1_F \implies m=n\). In other words, if \(x_n=x_m \implies n=m\).

Thus, we have:

Base Case (\(P(1)\)):

\(\bullet \)

Existence: \(x_1 = 1\cdot 1_F =1_F\), by the definition of natural multiplies, and by construction, \(1_F \in \mathbb {N}_F\), thus \(x_1\) exists. Coming from the other direction, \(1_F\) is the smallest natural of element of \(F\), by the definition of natural multiplies, \(1_F=1\cdot 1_F= x_1\), thus the smallest natural element of \(F\), can be represented by this form.

\(\bullet \)

Uniqueness: We need to show that there is no \(m \in \mathbb {N}_\mathbb {R}\) such that \(m\neq 1\), and \(m\cdot 1_F=1_F\). From the properties of naturals, \(m\geq 1\), but from the condition \(m\neq 1\), \(m\) would have to be \(>1\). We will show, by induction, that for all \(m>1\), it is never the case that \(m\cdot 1_F=1_F\).

Taking advantage of the order of \(F\), we can set the inductive proposition, \(U(n)\), to be true when \(n\cdot 1_F >1_F\), given \(n \in \mathbb {N}_{\mathbb {R}}\) and \(n>1\)

(i)

\(U(2)\) is true; for \(n=2\), we have, \(2\cdot 1_F= 1_F +1_F\), by the definition of natural multiplies. But, because \(1_F>0\), \(2\cdot 1_F= 1_F+1_F> 1_F\), by the monotonicity of addition in an ordered field. Thus, \(2\cdot 1_F>1_F\).

(ii)

\(U(k)\implies U(k+1)\); Given that \(U(n)\) holds for \(n=k\), we have \(k\cdot 1_F>1_F\), again, by the monotonicity of addition in an ordered field, we have \(k\cdot 1_F+1_F>1_F+1_F\), by the definition of natural multiplies, we have \((k+1)\cdot 1_F>2\cdot 1_F\), but we have already shown that \(2\cdot 1_F > 1_F\), thus, by the transitive property of \(F\), \((k+1)\cdot 1_F>1_F\).

Hence, by induction, we can conclude that there does not exist \(m\neq 1\), such that \(m\cdot 1_F=1_F\). Thus, We have shown the Uniqueness.

Inductive Step (\(P(k)\implies P(k+1)\)):

Given \(P(k)\) holds, \(x_k = k\cdot 1_F \in \mathbb {N}_F\), and \(k\cdot 1_F\) is a unique representation.

\(\bullet \)

Existence: because, \(x_k = k\cdot 1_F \in \mathbb {N}_{F}\), by the property of any natural element, \(x_k+1_F\) is also a natural of \(F\), hence \(k\cdot 1_F+1_F \in \mathbb {N}_F\). By the definition of natural multiplies, \(k\cdot 1_F+1_F = (k+1)\cdot 1_F = x_{k+1} \in \mathbb {N}_F\). Thus, we have shown that \(x_{k+1}\) is also a natural of \(F\) if \(x_k\) is.

\(\bullet \)

Uniqueness: given \(n=k\), for any \(m\in \mathbb {N}_{\mathbb {R}}\), \(m\cdot 1_F = k\cdot 1_F \implies m=k\). Adding \(1_F\), to both sides of the inductive hypothesis’s conditional: \begin {align*} k\cdot 1_F +1_F &= m\cdot 1_F +1_F\\ (k+1)\cdot 1_F &= (m+1)\cdot 1_F \end {align*}

by the definition of natural multiples. Note that the conditional of the inductive hypothesis still holds, hence, as does the implication, that is \(k=m\), then, adding \(1\) to both sides, \(k+1= m+1\). because \(m\) is arbitrary, we have \((k+1)\cdot 1_F = m_F\cdot 1_F \implies k+1=m_F\). Hence, \(x_{k+1}=(k+1)\cdot 1_F\) is unique if \(x_k\) is unique.

Thus, by the principle of mathematical induction, each natural \(x\) of \(\mathbb {N}_F\) has a unique representation of the form \(x=n\cdot 1_F\), where \(n \in \mathbb {N}_{\mathbb {R}} \) and \(1_F\) is the unity of \(F\). We have also shown the existence of each \(x_n = n\cdot 1_F\) in \(F\) as its natural elements.

Note that, for any \(x \in F\), and any \(n \in \mathbb {N}_{\mathbb {R}}\), \(nx \in F\). We can easily show that this holds for all \(n\) by induction. The Base case, by definition of natural multiples, holds. If the proposition holds for some \(n=k\), \(kx \in F\). Then by the definition of natural multiplies, \((k+1)x = kx+x\). Because \(kx \in F\) and \(x \in F\), by the closure property of all fields, \(kx+x \in F\).

Now, we need to show that, for \(m,n \in \mathbb {N}_{\mathbb {R}}\), we have \(m<n \iff mx<nx\). First, showing that \(m<n \implies mx < nx\).

Fixing \(m\), we can define, the inductive proposition, \(Q(n)\) to be true when either \(n\leq m\) or \(mx < nx\), for some \(x>0_F\) of \(F\). Note that we have constructed the inductive proposition in such a way that it applies for all natural \(n\). Thus, we have:

(i)

\(Q(1)\) is true; From the properties of natural numbers, \(m \geq 1\). Hence, \(n=1 \leq m\), thus \(Q(1)\) holds.

(ii)

\(Q(k) \implies Q(k+1)\); We have either, \(k \leq m\) or \(mx<kx\).

(a)

if \(k \leq m\), either \(k=m\) or \(k<m\). If \(k<m\), then \(k+1\leq m\). If \(k=m\), then \(kx=mx\), given that \(0_F<x\), by the monotonicity of addition, \(mx< x+mx = x+kx\). By the definition of natural multiplies, \(mx < (k+1)x\). Thus, \(Q(k+1)\) holds when \(k \leq m\).

(b)

if \(mx<kx\), adding \(x\) to both sides of the equation, by the monotonicity of addition, \(mx+x<kx+x\). Because, \(mx<mx+x\), we have \(mx<mx+x < kx+x\), by the definition of natural multiplies, we have \(mx<(k+1)x\). Thus \(Q(k+1)\) holds when \(mx<kx\)

We have shown that \(m<n\) implies that \(mx<nx\). To show the converse, \(mx<nx \implies m<n\), is true, can consider the contrapositive of the converse (i.e., the inverse), which is \(m\geq n \implies mx \geq nx\). We can apply very similar reasoning as above to prove this.

For nonnegative integers \(n,k\;\; (k \leq n) \in \mathbb {R}\). Verify Pascal’s Law: \begin {align*} \binom {n}{k} + \begin {pmatrix} n \\ k+1 \end {pmatrix} = \begin {pmatrix}n+1 \\ k+1 \end {pmatrix} \end {align*}

Using it, prove inductively that \(\big (\begin {smallmatrix} n \\ k\end {smallmatrix} \big )\) is always a natural number. Then, establish inductively the binomial theorem: for elements \(a,b\) of any field \(F\) and any natural number \(n\), \begin {align*} (a+b)^n = \sum _{k=0}^n \binom {n}{k} a^k b^{n-k}. \end {align*}

Deduce from it the formulae of Problem 10 directly.

are equal iff \(x_1 = y_1, x_2= y_2, \ldots , x_n=y_n\). Assume this is known for \(n=2\).

(i)

\(A \times B\) has \(mn\) elements;

(ii)

\(A\) has \(2^m\) subsets;

(iii)

If further \(A \cap B = \varnothing \), then \(A \cup B\) has \(m+n\) elements.

(\(q\) and \(r\) are called, respectively, the quotient and remainder from the division of \(m\) by \(n\)). If \(r= 0\), we say \(n\) divides \(m\) and write \(n|m\).