# Making a recursive formula for finding amount of ways to spend money on beer

So far, i've only made recursive formulas for finding simple patterns such as fibonacci, however i can't seem to get my head around this.

The information available is that there are $n$ different beers with different prices, the $i$th beer has a price $p_i$. Students have $C$ amount of money

How would you make a recursive formula for the amount of ways students can spend exactly $C$ money on beer?

• Does the order matter ? I mean does the purchase of 4, 3, 2, 4 differs from the purchase of 2, 4, 4, 3 ?
– user16034
Commented Jul 27, 2022 at 9:23

## 3 Answers

The $n$-the beer has price $p_n$. You can use $k$ items of beer $n$, provided $k\cdot p_n\le C$. The remaining money can be used for beers $1$ to $n-1$. That gives a recursive approach.

• so if i were to make that as a recursive formula it would be something like: $$N(C, i)=\begin{cases} N(C, i)=0 & \text{if C=0}\\ N(C, i)= k \cdot p_i & \text{if K \cdot p_n \leq C}\\ N(C, i)= C-p_i & \text{if C>0 and K \cdot p_n > C } \end{cases}$$ I'm actually unsure on how to formulate "$1$ to $n-1$ Commented May 18, 2018 at 12:26

My attempt is

N(C)=\left\{ \begin{align} &0&C<p_{min}\\ &1&C=p_{min}\\ &\displaystyle\sum_i N(C-p_i)&\text{other cases} \end{align} \right.

The summation part solves your problem of going through 1 to n.

Implementing this on the computer gives correct answers.

• This is wrong. Try $p_1=2,p_2=3,C=3$.
– user16034
Commented Jul 27, 2022 at 9:58

If the order matters and the $$p_k$$ are distinct,

$$N(C)=\begin{cases}C=p_1\to1\\C=p_2\to1\\\cdots\\C=p_n\to1\\\text{else}\to\displaystyle\sum_{p_k\le C}N(C-p_k)\end{cases}$$