Proving the recurrence for the “number of ways to make change” problem


I’m studying the famous making change problem. (Post 1 and Post2).

Suppose you were given three coins (1, 2, and 5) and a bill of amount 10 and you want to compute the number of ways you could exchange the bill into coins. In this specific example, there are 4 ways.

The solution involves ordering the coins from the largest to the smallest (5, 2, 1). We then can divide the solution into three subproblems:

(1) the number of ways to change using coins (1) and amount (10 – 1). Call it $ F_1(10-1)$ .

(2) the number of ways to change using coins (1,2) and amount (10 – 2). Call it $ F_2(10-2)$ .

(3) the number of ways to change using coins (1,2,5) and amount (10 – 5). Call it $ F_3(10-5)$ .

The final recurrence would be $ F(10) = F_1(10-1) + F_2(10-2) + F_3(10-5)$ .

I understand the intuition and usually dynamic programming problems have very straight forward proofs (Cut and Paste Arugments). But with this problem, I have no idea where to start? The proof is usually by contradiction and arguing how it’s not possible for $ F(n)$ not to be the optimal value. But I’m not sure here. Any hints on how to even start with this proof? Basically, why is the above recurrence correct?