How many unique ways to make a change of 63 cents by using any combinations of penny, nickel, dime, and/or quarter coins? Click here for the solution.
Solution Let’s assume function \(f_1(n)\) is number of ways using pennies to make a change of \(n\) cents. Obviously, we have $$f_1(n) = \begin{cases} 0 & \text { if n < 0 }\\ 1 & \text { if n = 0 }\\ f_1(n-1) = \cdots = f_1(0) = 1 & \text { if n > 0 } \end{cases} $$ Lets assume function \(f_2(n)\) is number of ways using pennies and/or nickels to make a change of \(n\) cents. $$f_2(n) = \begin{cases} 0 & \text { if n < 0 }\\ 1 & \text { if n = 0 }\\ f_1(n)+f_2(n-5) = f_2(n-5) +1 & \text { if n > 0 } \end{cases} $$ Lets assume \(f_3(n)\) is number of ways using pennies, nickels and/or dimes to make a change of \(n\) cents. $$f_3(n) = \begin{cases} 0 & \text { if n < 0 }\\ 1 & \text { if n = 0 }\\ f_2(n)+f_3(n-10) & \text { if n > 0 } \end{cases} $$ Lets assume \(f_4(n)\) is number of ways using pennies, nickels, dimes and/or quarters to make a change of \(n\) cents. $$f_4(n) = \begin{cases} 0 & \text { if n < 0 }\\ 1 & \text { if n = 0 }\\ f_3(n)+f_4(n-25) & \text { if n > 0 } \end{cases} $$ Obviously, the answer for making a changes of 63 cents is the same as to make 60 cents, because 3 pennies must be used to make a change of 3 cents. So we consider \(n\) that are multiples of 5, as shown in the following table: $$ \begin{array}{c|c|c|c|c} \ n\ & f_1(n) & f_2(n) & f_3(n) & f_4(n) \\ \hline 0 & 1 & 1 & 1 & 1\\ 5 & 1 & 2 & 2 & 2\\ 10 & 1 & 3 & 4 & 4\\ 15 & 1 & 4 & 6 & 6\\ 20 & 1 & 5 & 9 & 9\\ 25 & 1 & 6 & 12 & 13\\ 30 & 1 & 7 & 16 & 18\\ 35 & 1 & 8 & 20 & 24\\ 40 & 1 & 9 & 25 & 31\\ 45 & 1 & 10 & 30 & 39\\ 50 & 1 & 11 & 36 & 49\\ 55 & 1 & 12 & 42 & 60\\ 60 & 1 & 13 & 49 & 73\\ %65 & 1 & 14 & 56 & 87\\ \end{array} $$ Therefore, the answer to the question is: $$ f_4(63) = f_4(60) = 73 $$ \(\blacksquare\)