I am trying to show that the sum of primes less than or equal to some $k \in \mathbb{N}$ must be greater than $k$ itself. My hint was to use Bertrands Postulate but I am not getting anywhere.

  • 1
    $\begingroup$ You can do it by induction. Add all the prime numbers up to $n/2$ and use Bertrand's postulate. (The case where $n$ is even is the only one that matters, really) $\endgroup$ – Luiz Cordeiro May 4 '16 at 1:24
  • $\begingroup$ I have been trying by induction! $\endgroup$ – Prince M May 4 '16 at 1:26
  • $\begingroup$ How do I add the primes to some arbitrary n/2? Can you give me a slightly more specific outline of how the proof should go and I'll see if I can finish it off? Im mostly just trying to use this as a lemma @LuizCordeiro $\endgroup$ – Prince M May 4 '16 at 1:29
  • $\begingroup$ I am number theory illiterate. $\endgroup$ – Prince M May 4 '16 at 1:30
  • $\begingroup$ never mind, I think I just got it. $\endgroup$ – Prince M May 4 '16 at 1:34

We use the second principle of induction/complete induction/or whatever variant of the name there is (Wikipedia).

Let $P(k)$ denote the sum of all primes up to $k$. The problem is to show that $P(k)>k$ for all $k\geq 3$.

Prove it for $k=3$.

Now assume that $P(n)>n$ for all $n\leq k$, and let's prove that $P(k+1)>k+1$. (This is the inductive step). By hypothesis, we have $$P(\lfloor\frac{k+1}{2}\rfloor)>\lfloor\frac{k+1}{2}\rfloor$$ By Bertrand's postulate, there is a prime $p$ strictly between $\lfloor\frac{k+1}{2}\rfloor$ and $2\lfloor\frac{k+1}{2}\rfloor\leq k+1$, so $$P(k+1)\geq P(\lfloor\frac{k+1}{2}\rfloor)+p>\lfloor\frac{k+1}{2}\rfloor+\lfloor\frac{k+1}{2}\rfloor+1\geq k+1$$ where in the second inequality we use that $p>\lfloor\frac{k+1}{2}\rfloor$, so $p\geq\lfloor\frac{k+1}{2}\rfloor+1$.

  • $\begingroup$ Yes! this is what I ended up coming up with also. Thank you again $\endgroup$ – Prince M May 4 '16 at 1:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.