# Prove Recursive formula (Dynamic programming) N(C,i)

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.

Posted on Categories proxies