# Sum of primes less than or equal to K is greater than K

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.

• 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) – Luiz Cordeiro May 4 '16 at 1:24
• I have been trying by induction! – Prince M May 4 '16 at 1:26
• 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 – Prince M May 4 '16 at 1:29
• I am number theory illiterate. – Prince M May 4 '16 at 1:30
• never mind, I think I just got it. – 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$.

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