Skip to main content
$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

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

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

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)$$.

• Was this article helpful?