Homework 14

Details

1. (10) Use induction to prove for all \(n\geq 1\), a set of size \(n\) has \(2^n\) subsets.
2. (10) Prove that if you have coins with values 3 and 5, any amount of change of at least 8 can be made with those coins. That is, prove (using strong induction) that every \(n\geq 8\) can be written as \(n=3a+5b\) for some integers \(a\) and \(b\). Don't forget to word the proof very carefully and prove enough base cases!