How to find a recurrence relation for counting the number of solutions?

Question

Consider the diophantine equation $$x_1+3x_2+5x_3 = n$$ where $x_i\geq 0$ and $n\geq 1.$ Let $P_n(1,3,5)$ denote the number of solutions to this equation. I want to express $P_n(1,3,5)$ in terms of $P_{1}(1,3,5), P_{2}(1,3,5),\cdots, P_{n-1}(1,3,5).$

Here is what I observed:

If $(x_1,x_2,x_3)$ is a solution to $$x_1+3x_2+5x_3 = k$$ then $(x_1+1,x_2,x_3)$ is a solution to $$x_1+3x_2+5x_3 = k+1$$ $(x_1,x_2+1,x_3)$ is a solution to $$x_1+3x_2+5x_3 = k+3$$ and $(x_1,x_2,x_3+1)$ is a solution to $$x_1+3x_2+5x_3 = k+5.$$ But I don't know know how to combine this to get the desired relation. Any ideas will be much appreciated.

Edit: Based on the answer given below, we observe that a solution (x_1,x_2,x_3) to $$x_1+3x_2+5x_3 = n$$ must have $x_1>0$ or $x_2>0$ or $x_3>0.$ If $x_1>0$ then (x_1-1,x_2,x_3) is a solution $$x_1+3x_2+5x_3 = n-1$$ and there are $P_{n-1}(1,3,5).$ Proceeding in a similar manner for $x_2$ and $x_3$ and applying the inclusion-exclusion principle we get: $$P_{n}(1,3,5) = P_{n-1}(1,3,5)+P_{n-3}(1,3,5)+P_{n-5}(1,3,5)-P_{n-4}(1,3,5)-P_{n-8}(1,3,5)-P_{n-6}(1,3,5)+P_{n-9}(1,3,5).$$

Answer 1

Let's do a simpler example: $P_n(2,3)$, the number of solutions to $2x+3y=n$ in nonnegative integers. For $n>0$ a solution must have either $x>0$ or $y>0$. A solution with $x>0$ means that $(x-1,y)$ is a solution to $2X+3Y=n-2$ so there are $P_{n-2}(2,3)$ of these. Likewise there are $P_{n-3}(2,3)$ solutions with $y>0$. But some solutions have $x>0$ and $y>0$, and there are $P_{n-5}(2,3)$ of these. By the inclusion/exclusion principle, $$P_n(2,3)=P_{n-2}(2,3)+P_{n-3}(2,3)-P_{n-5}(2,3).$$

In your example, you'll have to do three-fold inclusion/exclusion...

Answer 2

One way to solve this is with generating functions. For $x_1$ you get a factor $(1 - z)^{-1}$, $x_2$ gives $(1 - z^2)^{-1}$, $x_3$ adds $(1 - z^3)^{-1}$. Pulling all together:

$\begin{align*} [z^n] \frac{1}{(1 - z) (1 - z^2) (1 - z^3)} &= \frac{1}{24} [z^n] \frac{11 + 3 z + 3 z^2}{1 - x^3} + \frac{1}{8} [z^n] \frac{1}{1 + z} + \frac{17}{72} [z^n] \frac{1}{1 - z} + \frac{1}{4} [z^n] \frac{1}{(1 - z)^2} + \frac{1}{6} [z^n] \frac{1}{(1 - z)^3} \end{align*}$

The last expression by partial fraction, but adding back together fractions with denominators $1 + z + z^2$ and $1 - z$ to simplify coefficient extraction.

Now, using the generalized binomial theorem:

$\begin{align*} (1 - z)^{-m} &= \sum_{n \ge 0} (-1)^n \binom{-m}{n} z^n \\ &= \sum_{n \ge 0} \binom{n + m - 1}{m - 1} z^n \end{align*}$

Thus we get:

$\begin{align*} &\frac{1}{24} (11 [n \equiv 0 \pmod{3}] + 3 [n \not\equiv 0 \pmod{3}]) + \frac{1}{8} (-1)^n + \frac{17}{72} + \frac{1}{4} \binom{n + 2 - 1}{2 - 1} + \frac{1}{6} \binom{n + 3 - 1}{3 - 1} \\ &\quad = \frac{1}{24} (11 [n \equiv 0 \pmod{3}] + 3 [n \not\equiv 0 \pmod{3}]) + \frac{6 n^2 + 36 n + 47 + 9 (-1)^n}{72} \end{align*}$

Here $[\dotsb]$ is Iverson's convention: 1 if the condition in brackets is true, 0 otherwise.