2.2.E: Problems on Natural Numbers and Induction (Exercises)

Exercise $\PageIndex{1}$

Complete the missing details in Examples $(\mathrm{a}),(\mathrm{b}),$ and $(\mathrm{d})$.

Exercise $\PageIndex{2}$

Prove Theorem 2 in detail.

Exercise $\PageIndex{3}$

Suppose $x_{k}<y_{k}, k=1,2, \ldots,$ in an ordered field. Prove by induction on $n$ that
(a) $\sum_{k=1}^{n} x_{k}<\sum_{k=1}^{n} y_{k}$
(b) if all $x_{k}, y_{k}$ are greater than zero, then

$$\prod_{k=1}^{n} x_{k}<\prod_{k=1}^{n} y_{k}$$

Exercise $\PageIndex{4}$

Prove by induction that
(i) $1^{n}=1$;
(ii) $a<b \Rightarrow a^{n}<b^{n}$ if $a>0$.
Hence deduce that
(iii) $0 \leq a^{n}<1$ if $0 \leq a<1$;
(iv) $a^{n}<b^{n} \Rightarrow a<b$ if $b>0 ;$ proof by contradiction.

Exercise $\PageIndex{5}$

Prove the Bernoulli inequalities: For any element $\varepsilon$ of an ordered field,
(i) $(1+\varepsilon)^{n} \geq 1+n \varepsilon$ if $\varepsilon>-1$;
(ii) $(1-\varepsilon)^{n} \geq 1-n \varepsilon$ if $\varepsilon<1 ; n=1,2,3, \ldots$

Exercise $\PageIndex{6}$

For any field elements $a, b$ and natural numbers $m, n,$ prove that

$$\begin{array}{ll}{\text { (i) } a^{m} a^{n}=a^{m+n} ;} & {\text { (ii) }\left(a^{m}\right)^{n}=a^{m n}} \\ {\text { (iii) }(a b)^{n}=a^{n} b^{n} ;} & {\text { (iv) }(m+n) a=m a+n a} \\ {\text { (v) } n(m a)=(n m) \cdot a ;} & {\text { (vi) } n(a+b)=n a+n b}\end{array}$$
[Hint: For problems involving two natural numbers, fix $m$ and use induction on $n ]$.

Exercise $\PageIndex{7}$

Prove that in any field,

$$a^{n+1}-b^{n+1}=(a-b) \sum_{k=0}^{n} a^{k} b^{n-k}, \quad n=1,2,3, \ldots$$
Hence for $r \neq 1$
$$\sum_{k=0}^{n} a r^{k}=a \frac{1-r^{n+1}}{1-r}$$
(sum of $n$ terms of a geometric series).

Exercise $\PageIndex{8}$

For $n>0$ define

$$\left(\begin{array}{l}{n} \\ {k}\end{array}\right)=\left\{\begin{array}{ll}{\frac{n !}{k !(n-k) !},} & {0 \leq k \leq n} \\ {0,} & {\text { otherwise }}\end{array}\right.$$
Verify Pascal's law,
$$\left(\begin{array}{l}{n+1} \\ {k+1}\end{array}\right)=\left(\begin{array}{l}{n} \\ {k}\end{array}\right)+\left(\begin{array}{c}{n} \\ {k+1}\end{array}\right).$$
Then prove by induction on $n$ that
(i) $(\forall k | 0 \leq k \leq n)\left(\begin{array}{l}{n} \\ {k}\end{array}\right) \in N ;$ and
(ii) for any field elements $a$ and $b$,
$$(a+b)^{n}=\sum_{k=0}^{n}\left(\begin{array}{l}{n} \\ {k}\end{array}\right) a^{k} b^{n-k}, \quad n \in N \text { (the binomial theorem). }$$
What value must $0^{0}$ take for (ii) to hold for all $a$ and $b ?$

Exercise $\PageIndex{9}$

Show by induction that in an ordered field $F$ any finite sequence $x_{1}, \ldots, x_{n}$ has a largest and a least term (which need not be $x_{1}$ or $x_{n} ) .$ Deduce that all of $N$ is an infinite set, in any ordered field.

Exercise $\PageIndex{10}$

Prove in $E^{1}$ that
(i) $\sum_{k=1}^{n} k=\frac{1}{2} n(n+1)$;
(ii) $\sum_{k=1}^{n} k^{2}=\frac{1}{6} n(n+1)(2 n+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)(2 n+1)\left(3 n^{2}+3 n-1\right)$.