Question

Having trouble with Problem set 2 (problem 2) - Can anyone help me explain why the theorem is true (in plain English)? thanks!

Answer 1

Copying an old answer I gave:
"This is not a rigorous proof, nevertheless, I think it will give some insight. Suppose that you have packages of size 6, 9, 20. If you find six consecutive solutions starting at, then for n + 7 the solution will be the set of solution for n + 1 plus a package of size 6. For n + 8, the set of size n + 2 plus a package of size 6, etc. It is not that hard to generalize from there. At least, that's how I thought about the problem, albeit not rigorously so."
You can generalize for packages of size 6, 9, 20, after you found the consecutive numbers, you can prove that S(x) = S(x - 6) + (1,0,0), where the first index of the tuple is the smallest package size, etc. for x > n + 5.

If you wish a more rigorous proof, I may come up with something, but I think this gives a nice intuition. Anyway, if it is still unclear, go ahead and ask your doubts :-)