Strong Induction to find all possible combinations of two numbers

Question

Full disclosure, this is a homework question, so I'm only looking for hints not full solutions please.

There is a store which offers two denominations of gift certificates, \$25 and \$40. Determine the possible total amounts that can be formed using the certificates, using strong induction to prove your answer.

My first approach was to write out something like this, let $S$ be a possible amount where $S = 25a + 40b$ and $a, b \in \mathbb{Z}^+$ ($0$ being included in the positive integers). The problem is that I'm not sure how to use this as a propositional statement for strong induction.

Second, I tried to make a table to find a pattern, like this: $$ \begin{array}{c|ccccc} 0 & 0 & 1 & 2 & 3 & 4 \\ \hline 0 & 0 & 25 & 50 & 75 & 100 \\ 1 & 40 & 65 & 90 & 115 & 140 \\ 2 & 80 & 105 & 130 & 155 & 180 \\ 3 & 120 & 145 & 170 & 195 & 220 \\ 4 & 160 & 185 & 210 & 235 & 260 \\ \end{array} $$

The issue with this approach was that, once again, I could see no particular path towards using strong induction (or any discernible pattern).

I'm not sure how best to move forward, and I haven't been able to find many helpful resources. I'd be very grateful for some help, thanks!

Answer 1

Since you are only looking for a hint:

HINT Expand your table by just two more columns, and then look at your table and start writing the possible total amounts in order. So you get 25, 40, 50, 65, 75, 80, .... After a while you will see a pattern ... Use this to form your hypothesis and prove by strong induction.

Answer 2

First, let us "scale down" the problem by a factor of $5$, i.e., that we are working with $5$ and $8$ gift certificates. We will "scale up" our solution afterwards.

Notice that $5$ and $8$ are coprime and thus their non-negative integer linear combinations form a numerical semigroup with two generators. A nice result of numerical semigroups with two generators $m,n$ is that any number bigger than $mn-m-n$ is in the semigroup.

To show this by induction for this particular problem, notice that $mn-m-n = 8*5-8-5 = 27$ is the largest number that can't be written as a positive integer linear combination of $5$ and $8$. Thus, the next $5$ numbers ($28,29,30,31,32$) can be written as a linear combination of $5$ and $8$, this will form your base case. See if you can explicitly find the linear combinations of $5$ and $8$ that will give you those five numbers. Now, consider $n>32$ and suppose that $k$ can be written as a positive integer linear combination of $5$ and $8$ for all $28 \leq k < n$. We want to show the same holds for $n$. Notice that $28 \leq n-5 < n$ and thus $n-5 = 5a+8b$ for $a,b\in \mathbb{Z}^+$. From this, we see that $n= 5(a+1)+8b$ and thus we can write $n$ as a positive integer linear combination of $5$ and $8$, thus completing the induction.

We still need to check the values less than $28$ which we can do by brute force. We see that we can get the following with positive integer linear combinations of $5$ and $8$ for numbers less than $28$, $$\{ 0,5,8,10,15,16,18,23,24,25,26\}.$$

Scaling our solution up by $5$, we can obtain the following amounts: $$\{0,25,40,50,75,80,90,115,120,125,130\} \cup \{140, 145,150,\dots\}$$

Answer 3

First off, if: $$S=40a+50b$$ then: $$S+10=40(a-1)+50(b+1)$$ but only if $a\ge1$. If $a=0$ and $b\ge 3$, then: $$S+10=40\cdot4+50(b-3)$$ So, if $S\ge150$, we can form $S+10$ if we can form $S$. Now, something similair can be done for $S+5$. After you've got that figured out, use induction to prove you can reach all multiples of $5$ greater than a certain number (what number?) and prove that you can only reach multiples of $5$ (why?)

Then you're left with the small cases, which you'll need to check by hand