Base Case in Strong Induction Proofs

1. Mar 30, 2013

velouria131

I am dealing with sets of problems that go as such: "How many n-cent postages can be formed from x and y cent stamps"

For instance, I am doing a problem where x and y are 4 and 11 respectively. I don't understand how to determine a base case. I know that I must proof P(k + 1) for all P(i). The answer in my book is that the base case is a postage equal to 30 cents, but I don't follow. Could someone explain how I would go about finding a base case? The book seems to set this bound after showing 4 and 11 cent combinations up to 28. However, I do not see why 30 was chosen as a lower bound. Thanks.

2. Mar 31, 2013

MarneMath

I'm sorry for the short reply, I'm running a slight fever, but i'll like to try to give you some advice since it's midday here and I've noticed no one else has tried to help you. I've encountered problems like this and if I do recall it was in Rosen's discrete mathematics. Anyway, the idea is what you need to find the number for which you can make every consecutive number appear. For example, the number cannot be 4, because you can't make 5, 6, 7 nor can it be 8 because you can't make 9 or 10. If you continue on this path, I think you'll find that 28 will be the least number you can have such that you can make 28 + k, where k is an natural number. To prove this, I also suspect you'll eventually need to show that 29, 30 also work, and proceed with the strong induction form. I hope that clears this up some.