# Representing any $n\geq 12$ as a Sum of $4$'s and $5$'s

Describe the set of all possible dollar amounts that can be formed using only four and five dollar bills, and argue about the correctness of your answer using mathematical induction. Hint: Your solution should be in the form of a set. For example, the solution $€\{4, 5, 8, 9, 10, 12, ...\}$ implies you can represent dollar amounts $4, 5, 8, 9, 10$, and all integral amount greater than $12$.

-
See solution in this entry: math.stackexchange.com/questions/654877/… –  Tom Collinge Feb 4 at 7:39

## 3 Answers

Any number multiple of $4$ can be easily formed i.e., $4,8,12,16,20\cdots$

For $m=4n+1=4(n-1)+5\implies$ we need $n\ge1\implies m\ge5$ i.e., $5,9,13,17\cdots$

For $m=4n+2=4(n-2)+5\cdot2\implies$ we need $n\ge2\implies m\ge10$ i.e., $10,14,18,22\cdots$

For $m=4n+3=4(n-3)+5\cdot3\implies$ we need $n\ge3\implies m\ge15$ i.e., $15,19,23,27\cdots$

The numbers those can not be formed are $1,2,3,6,7,11$

-

The Frobenius Coin problem with n = 2, gcd(4,5) = 1 . The number of non-representable dollar amounts is (4 - 1)*(5 - 1)/2 = 6 .

-

Since $8$ is possible, $12$ is possible. Use $4$ and then do $12-4$

Since $8$ is possible, $13$ is possible. Use $5$ and then do $13-5$

Since $9$ is possible, $14$ is possible. Use $5$ and then do $14-5$

Since $10$ is possible, $15$ is possible. Use $5$ and then do $15-5$

After $15$ you can always get one of $12$, $13$, $14$, $15$ by using just $4$ repeatedly.

You can use induction as follows: Suppose all values $\ge 12$ and up to $n>15$ is possible. Then $n+1$ is possible since $n+1 - 4$ is between $12$ and $n$.

-