Elementary Number Theory Problems 3.3 Solution (David M. Burton's 7th Edition) - Q25
Background
All theorems, corollaries, and definitions listed in the book's order:
Theorems and Corollaries in Elementary Number Theory (Ch 1 - 3)
All theorems and corollaries mentioned in David M. Burton’s Elementary Number Theory are listed by following the book’s order. (7th Edition) (Currently Ch 1 - 3)
I will only use theorems or facts that are proved before this question. So you will not see that I quote theorems or facts from the later chapters.
Question
Let $p_{n}$ denote the $n$th prime. For $n > 3$, show that $$p_{n} < p_{1} + p_{2} + \cdots + p_{n-1}$$
[Hint: Use induction and the Bertrand conjecture.]
Solution
Base Case:
For $n = 4$, $p_{4} = 7 < p_{1} + p_{2} + p_{3} = 2 + 3 + 5 = 10$.
Induction Hypothesis:
Assume $p_{k} < p_{1} + p_{2} + \cdots + p_{k-1}$ for some integer $k > 4$.
Consider the case for $k + 1$:
By Bertrand's Postulate, we have:
$$ \begin{equation} \begin{split} p_{k + 1} & < 2p_{k} \\ & = p_{k} + p_{k} \\ & \lt p_{1} + p_{2} + \cdots + p_{k-1} + p_{k} \quad \text{by inductive hypothesis} \\ \end{split} \nonumber \end{equation} $$Conclusion:
This proves the statement by induction.
Read More: All My Solutions for This Book