Problem 8.11 of A Concise Introduction to Pure Mathmatics

Just for this question, count 1 as a prime number. A well-know result in number theory says that for every integer x>= 3, there is a prime number p such that 1/2x < p < x. Using this result and strong induction, prove that every positive integer is equal to a sum of primes, all of which are different.

Proof:

1) The statement is true for 3, 3 = 1 + 2.
2) Assume the statement is true for all s <= n
3) For n + 1, make p is a prime between 1/2(n+1) and (n + 1). then n + 1 = p + s, and s < 1/2(n + 1). According to 2) s equal to sum of different primes (p0 + p1 + p2 + ...), and since p > 1/2 (n+1) > s, p is different from (p0,p1,p2...). Therefore n + 1 is a sum of different primes.

End of Proof.