Because 3^{3}<2*4^{2}, we know that for all
*x*>3^{2} in *S*_{3,4} there is a smaller element
greater than *x*/2 also in *S*. (If
*x*=3^{a}4^{b}, with *b*>0, use
3^{a+1}4^{b-1}. Otherwise, we know that
*a*≥3, so use 3^{a-3}4^{b+2}.)

Therefore, by taking any *n* and subtracting from it, recursively, the
largest element of *S* that is less than or equal to *n*, one can
always reduce *n* to a number smaller than 9. In fact, by continuing to
subtract the largest element no greater than the residue that is still unused,
we can reduce *n* down to
either 0 or 1. Thus, either *n* is a subset sum or *n*-1 is.

Now, take these subsets and multiply all their elements by 4. This makes them
still in *S*_{3,4} and still distinct, and shows that any number
of the form
4*n* can be reduced in this way to either 0 or 4. Because neither 1 nor 3
divides by 4, these are unused, so we can subtract a further 1+3 where needed,
to prove that any multiple of 4 is a subset sum of *S*_{3,4}.

If *n* is not a multiple of 4, we can begin by subtracting from it 9,
9+81 or 27, as may be appropriate, to make it divide by 4, then use the method
for numbers divisible by 4 to complete the rest. This proves that all
*n*≥9+81 are subset sums.

Q.E.D.

The actual list of integers that are not subset sums of *S*_{3,4}
is {2,6,11,18,54}.

Regarding the bonus question, to prove that the same is true for all
*S*_{p,q} with co-prime *p*, *q*>1,
I must thank Li Li, again, for forwarding the relevant papers to me.

Turns out that this problem was initially posed as a conjecture by the great Hungarian mathematician Paul Erdős, and first solved by the British mathematician Bryan John Birch -- ingeniously -- in

`
B. J. Birch, Note on a
problem of Erdős, Math. Proc. Cambridge Phil. Soc. 55,
370-373, 1959.
`

Birch's proof is short, elegant and elementary: exactly the kind of proof we
like to see here, at Using your Head is Permitted. I won't repeat it on this
page, but readers are encouraged to check out the link. I'll mention here only
one stroke of brilliance of the proof: Birch initially relaxes the question to
allow also *p ^{x}q^{y}* values where

Following up on Birch's result, but using much heavier mathematical machinery,
Birch's own doctoral advisor, John William Scott Cassels, proved a similar
result regarding general sets, not just ones generateable as powers, showing
that restricting the rate at which members of the set become increasingly rare
as the numbers involved increase, while demanding that the numbers in the set
are diverse enough (e.g., not all divisible by some *k*), is enough to
ensure that all integers except for finitely many can be represented as
subset sums. The number of "missing" integers can be quite large, however.

Cassels's proof can be found in

These results have been further generalised in many papers, including recent ones, and the topic seems to be under continuous study. One particularly interesting follow-up was by Erdős himself. It was published only a few months before Erdős's death.

The innovation here is that the elements taken from the set to create a sum
must also not have pairs that divide each other. Erdős and Lewin show
(in an elementary fashion) that {*p ^{x}q^{y}*} covers all
integers in this way (with or without a finite number of exceptions) if and
only if {