I’ve been asked to prove the correctness of the following recursive formula. The formula is trying to define, how many ways you can spend your money C on the i amount of beers. I did the following recursive formula where you either bought a beer and losing $ P-i$ money, or passed the beer and went for the next in the array $ i-1$ . You cannot buy the same type of beer twice.

$ $ N(C,i)=\begin{cases} 0 & \quad \text{if } C<0\;||\; i<0 \ 1 & \quad \text{if } C=0\ N(C,i-1)+N(C-P_i,i-1) & \quad otherwise \end{cases} $ $

I’m not certain how to prove the correctness of the algorithm. Especially because the assignment is about dynamic programming, and I can’t find any repeated subproblems. The amount of money you will have will differ unless some of the different beers cost the same. I asked a fellow student who said the problem will always give overlapping subproblems. The problem has also been talked about here (Making a recursive formula for finding amount of ways to spend money on beer), but I think my recursive formula is correct.

Sorry, if the question is unclear, or if I’ve done something wrong. It’s the first time on stackexchange, and I think, this is the place to ask the question and not the mathmatics site.