We are given a number of coins and a bill and want to exchange the bill into coins. We are asked to find the distinct number of ways of different combinations of coins that make up the bill.
The recursive solution I see everywhere is the following: Let $F(n, c)$ be the total number of ways to make change for amount $= n$ with $m$ coins $= \{c_1,...c_m\}$. Take the last coin $c_m$. We have two cases:
(1) We used $c_m$ in the solution and so we compute $F(n)=F(n-c_m,coins)$.
(2) We didn't use the coin $c_m$ in the solution and so we compute $F(n,coins-c_m)$.
Therefore, $$F(n) = F(n-c_m,coins) + F(n,coins-c_m)$$
I also see another way of solving this problem (here)) which basically is summarized as follows:
(1) start with $c_1$, then compute $F(n-c_1, \{c_1\})$.
(2) start with $c_2$, then compute $F(n-c_2, \{c_1,c_2\})$.
...
(m) start with $c_m$, then compute $F(n-c_m, \{c_1,c_2,...,c_m\})$.
The final sum is: $$F(n, coins) = F(n-c_1,\{c_1\}) + F(n-c_2,\{c_1,c_2\}) + ... + F(n-c_m, \{c_1,c_2,...,c_m\})$$
I see explanations and pictures of recursion trees showing how each method generates all the combinations we're interested in but I don't see how we could for example formally prove method 1? Where is this counting principle from? Is there a chapter or an article that I can read to understand it? Is there a way to prove formally that the number of ways to make change is $F(n) = F(n-c_m,coins) + F(n,coins-c_m)$?
