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

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).$$

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...

• I have two questions: when $x>0$ and $y>0$ then if $(x-1,y-1)$ is a solution to $2x+3y=n-5$ and that is why there are $P_{n-5}(2,3)$ of them, right? And second, I made an edit. Do you think that the recurrence is correct? Jan 11, 2019 at 5:54
• Yes, and yes. Now, a better way to do all this is to use generating functions.... @Hello_World Jan 11, 2019 at 5:56
• Yeah, I know for $P_n(2,3)$ we want the n'th coefficient of $$\frac{1}{(1-x^2)(1-x^3)}.$$ But it's not clear what the power series looks like. Jan 11, 2019 at 6:00

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.