Show that any postage greater than or equal to 8 cents can be made from 3 cent and/or 5 cent stamps using mathematical induction. For example, 31 cents can be made by using five 5 cent stamps and two 3 cent stamps for a total of 25+6=31 cents.
Hello kullgirl418, where (i.e. non-negative integers)Then we need to show that and . is self-evident since we may replace by ; hence we will then have shown that for all .
Hence, provided and and ., provided
Now states:which is true when and , and thus the conditions on and are satisfied for . Hence, by Induction, is true for all .
The reason I've added to both sides is that I wanted to set up an expression that would enable me to show that ; in other words, to show that if we can express the sum cents using 's and 's then we can express using 's and 's.
This, after all, is what induction is all about.