# 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? Posted on Categories proxies