Formula for number of ways to make $n$ units of currency if the coins we have are of value 1, 3, and 9 Suppose we live in a world where there are three forms of currency: each worth 1, 3, and 9 units. Can we find a formula for the number of ways to make $n$ units of currency, if we have an effectively unlimited supply of each? I am looking for a formula with finitely many binomial coefficients, the number of which does not grow with $n$.

Let $f_1(n)$ be the # of ways to make $n$ units using only $1$; $f_3(n)$ be the # of ways to make $n$ units using $1$ and $3$; and $f_9(n)$ be the # of ways using $1$, $3$ and $9$.
If only $1$ and $3$ are allowed, $3$ can be used $0 \leq k \leq \lfloor \frac{n}{3} \rfloor$ times. For the remaining $n - 3k$ units, we fill it using only $1$. Therefore,
$$
f_3(n) = \lfloor \frac{n}{3} \rfloor + 1
$$
Suppose totally $k$ $9$'s are used, there are totally $f_3(n - 9k)$ ways to fill the remaining units. Thus
$$
f_9(n) = \sum_{k=0}^{\lfloor \frac{n}{9} \rfloor} f_3(n - 9k) = \sum_{k=0}^{\lfloor \frac{n}{9} \rfloor} \lfloor \frac{n}{3} \rfloor - 3k + 1 = (\lfloor \frac{n}{9} \rfloor + 1)(\lfloor \frac{n}{3} \rfloor + 1) -  \frac{3\lfloor \frac{n}{9} \rfloor(\lfloor \frac{n}{9} \rfloor + 1)}{2} 
$$
