Approach to prove a recursive formula with two variables

Question

Given the recursive formula where $N$($C,i$) is the number of ways to buy balls (of different price) when
$C =$ current amount of money
$i$ $=$ index in price table $P$
ball price defined as $b_1 = P_1$ where $b$ is the ball at index $i$

\begin{align*} N(C, i) = \begin{cases} 1, & \mbox{if } \mbox{c = 0} \\ 0, & \mbox{if } \mbox{c < 0 or i > p.length } \\ N(C - p_i, i+1) + N(C, i+1), & \mbox{if } \mbox{c > 0} \\ \end{cases} \end{align*}

I have two questions for this :

First quick question: Is it legal to introduce $P$ in the recursive formula if not defined as a parameter for $N$?

Second question: How do I prove that the recursive formula is correct by induction? I'm used to make proofs with one variable, but here I have two? What is the starting point of the proof?

Answer 1

Yes, not mentioning $p$ as a parameter is legit. You assume the table $p$ fixed throughout the discussion, in particular already in the very definition of $N$. By the way, it seems that $N(c,i)$ rather denotes the number of ways to buy distinct balls of total cost exactly $c$ and with buying none of the balls before index $i$.

Also, it seems that there is a silent assumption that $p_i>0$ for all $i$.

To prove the recursion, note that

• without money, there is exactly one way to solve the task, namely by buying nothing (we use that the prices are positive here). Hence $N(c,i)=1$ if $c=0$.
• with negative money available, it is impossible to buy balls and end up with zero money; again this follows form the positivity of prices. Hence $N(c,i)=0$ if $c<0$.
• if there are no balls to choose from, but we still have money to spend, there is no way to solve the task. Hence $N(c,i)=0$ if $c>0$ and $i$ exceed the maximal index allowed for $p$. (whether this condition is equivalent to $i>p.\text{length}$, is probably implementation dependent.
• in all remaining cases, solving the task for $c$ and $i$ means to either buy the ball at index $i$ and solve the task with $c$ reduced by $p_i$ and $i$ increased by one; or don't buy the ball at index$I$ and solve the task with same $c$ and with $i$ replaced by $i+1$. Hence $N(c,i)=N(c-p_i,i+1)+N(c,i+1)$ in these cases.

Note that no induction was needed to justify the recursion formula.