Finding the largest linear combination that is not possible

Question

Regarding the problem:

What is the largest bet that cannot be made with chips worth $\$7.00 $ and $\$9.00$? Verify that your answer is correct with both forms of induction.

I need to find an algorithmic approach, but till now my approach is to try all possible combinations with 0,1,2,3,4,5,6,7,8 (9) as the column headings and then the next row having the values as 9,10,... and so on, till able to get all values that can be generated. All this requires an iterative approach that progressively increases the data set size, till at least 9 consecutive values can be generated. I have found that 47 is the largest value that cannot be generated.

But, first of all this is no programmable algorithm. Second, due to first reason, I cannot prove it by induction of any type.

I feel that the algorithmic approach should consider the values that are originating from the initial set of those values that cannot be generated by any linear combination of values; i.e. 1,2,3,4,5,6,8; and then checking out which value will be the last one that can be generated from them and is not a linear combination of $9x + 7y$ (with $x,y > 0$).

If there were an approach that takes all further points that are not reachable by all the initial set of non-reachable (not having a value given by the linear combination of 9x + 7y, (x,y >0)) points (1, 2, 3, 4, 5, 6, 8); then I would be very happy to get any hint for the same.

Answer 1

First of all, there is a known formula that gives the correct answer in this case: if $a,b$ are relatively prime, then the maximal element which cannot be written as a non-negative combination of $a,b$ is $(a-1)(b-1)-1$. (Extending this to the case where $a,b$ are not relatively prime is a nice exercise.)

Second, suppose you don't know this formula, and want to prove that 47 is the largest value that cannot be generated. You have to prove two things:

1. 47 cannot be generated.
2. Any larger number can be generated.

To show that 47 cannot be generated, note that if $47 = 9x + 7y$ with $x,y \geq 0$ then $x < 7$ and $y < 9$. This means that it suffices checking all $x \in \{0,\ldots,6\}$ and $y \in \{0,\ldots,8\}$.

To show that any larger number can be generated, you first show that $48,49,50,51,52,53,54$ can be generated, by giving the appropriate values of $x,y$ (for example, $48 = 3 \cdot 9 + 3 \cdot 7$). You then complete the proof by induction (how?).