My teacher said to use Bertrand's postulate and I have tried this for so long and I seem to go nowhere. Help would be appreciated.

EDIT: Here's what I've done in my proof so far (I need help finalizing case 2)

First note that for $p_0=13$, we can express all integers $7 \leq n \leq 2p_0=26$ as a sum of distinct primes less than or equal to $13$. Now, we will prove that we can construct these sums indefinitely. Assume we know some prime $p'$ exists such that every integer $7\leq n \leq 2p'$ can be expressed as a sum of distinct primes less than or equal to $p'$. Then, by Bertrand's postulate, there exists a prime $p$ such that $p'<p<2p'$. We claim now that every integer $7\leq n \leq 2p$ can be written as a sum of distinct primes less than or equal to $p$. Consider the two following cases

Case 1: $2p'-p\geq 7$, hence $2p'\geq p+7$ so the terms $p,p+1,\dots,p+7$ are less than or equal to $2p'$ which means they can be written as a sum of distinct primes $\leq p'$ by hypothesis. It is left to check whether the terms $p+8,p+9,\dots, 2p$ satisfy our claim. Note if we subtract $p$ from every term in the arithmetic progression above, it becomes $8,9,\dots, p<2p'$ which shows that each term can be written as the sum of $p$ plus some other distinct primes less than or equal to $p'<p$ by hypothesis.

Case 2: $2p'-p\leq 6$, hence $2p'\leq p+6$. Here we can see all terms $p+7,\dots, 2p$ satisfy our claim along with $p+2,p+3$ and $p+5$ by a similar argument as in Case 1. I'm not sure how to deal with $p+1,p+4,$ and $p+6$ though.

EDIT: Oh, since any prime $p \geq 13$ is odd, then the only possible values for $2p'$ in Case 2 are $p+1,p+3$ and $p+5$, so I don't have to worry about the other cases. I think I'm done!

EDIT: Nope, I still need to deal with $p+4$ and $p+6$.

  • 2
    $\begingroup$ Use strong induction. $\endgroup$ – DeepSea Aug 3 '15 at 4:10
  • 1
    $\begingroup$ I don't think this is easy (though I could be wrong). At first I thought you could use Bertrand to find a prime $p$ with $[\frac n2]<p<n$. Then, defining $m$ by $n-p=m$ you just inductively write $m$ as a sum of distinct primes (it is less than $p$ so you know $p$ doesn't appear twice). Alas, I see no reason why $m$ might not be $1$, $4$, or $6$ any of which would make the argument fail. $\endgroup$ – lulu Aug 3 '15 at 4:17
  • 1
    $\begingroup$ Seems to be known as Richert's Theorem. Not horribly difficult, but not straight forward either. I couldn't find his original paper but here is a proof: matwbn.icm.edu.pl/ksiazki/aa/aa41/aa4117.pdf $\endgroup$ – lulu Aug 3 '15 at 4:33

We shall inductively prove a stronger form, namely that every positive integer $n \ge 7$ can be written as the sum of distinct primes such that the largest is at most $\max(11,n-7)$. It turns out that strengthening makes the induction work!

Take $n \ge 28$.

Let $m = \lceil \frac{n-6}{2} \rceil= \lfloor\frac{n-5}{2} \rfloor$.

Let $p$ be a prime such that $m+1 \le p \le 2m-1$ [by Bertrand's postulate].

Then $\frac{n-5}{2} \le p \le n-7$.

By the induction to be established $n-p$ can be written as a sum of distinct primes such that the largest is at most $\max(11,n-p-7)$, which is less than $p$ because $p \ge \frac{28-5}{2} > 11$ and $2p \ge n-5 > n-7$.

Thus $n$ can be written as a sum of distinct primes such that the largest is at most $\max(7,n-7)$, and the induction holds as long as the claim is true for every $n$ from $7$ to $27$.

7 = 5+2
8 = 5+3
9 = 7+2
10 = 5+3+2
11 = 11
12 = 7+5
13 = 11+2
14 = 7+5+2
15 = 7+5+3
16 = 11+5
17 = 7+5+3+2
18 = 11+7
19 = 11+5+3
20 = 11+7+2
21 = 11+7+3
22 = 13+7+2
23 = 13+7+3
24 = 13+11
25 = 13+7+5
26 = 13+11+2
27 = 13+11+3
  • $\begingroup$ Superb! I just corrected the line where you define $m$. Thanks! $\endgroup$ – Jeze Ken Aug 5 '15 at 20:40
  • $\begingroup$ @JezeKen: Thanks! My silly careless mistake! $\endgroup$ – user21820 Aug 6 '15 at 0:28

Hint: Bertrand's postulate is useful for the inductive step. i.e. with the assumption this holds for all $n < M-1$, you have some prime $p$ s.t. $M \ge p > M/2$. Thus you can express $M-p$ as a sum of distinct primes, none of which are $p$.

All that remains is to show $n=7$ and that cases for which $M-p < 7$ can be handled. $M-p \in \{1, 4, 6\}$ will merit some detail... (times like this one wishes $1$ is allowed as a prime. This last part however seems to be quite difficult).

  • $\begingroup$ You can use the stronger form giving a prime $k < p < 2k - 2$ for any $k \ge 4$. But you still have to consider $M - p \in \{4, 6\}$. $\endgroup$ – 6005 Aug 3 '15 at 4:47
  • $\begingroup$ Thank you. I'm using your ideas, but do you think we can treat the cases $M-p=1,4,6$ without allowing the primes to be negative? $\endgroup$ – Jeze Ken Aug 3 '15 at 5:15
  • $\begingroup$ I think for the approach given, it will be difficult. I think we will essentially have to find another large prime $p_2$ s.t. $M-p_2 > 6$ for those cases, and argue distinctiveness will hold with $p_2$. Will think about it more later. $\endgroup$ – Macavity Aug 3 '15 at 5:22
  • 2
    $\begingroup$ Richert's theorem does use positive primes only. What you saw in the proof was that sums of the form $\sum_{k=1}^n\epsilon_kp_k$ with $\epsilon_k\in\{-1,1\}$ cover all integers (of correct parity) in a large interval. Adding $\sum_{k=1}^np_k$ produces all even numbers in a suitable interval where all coefficients are in $\{0,2\}$. Division by $2$ produces the claim. $\endgroup$ – Hagen von Eitzen Aug 3 '15 at 6:53
  • 2
    $\begingroup$ The accepted answer to math.stackexchange.com/questions/1382803/… contains a short proof of Richert's result. $\endgroup$ – Hagen von Eitzen Aug 3 '15 at 9:37

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.