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

| cite | improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – nls Jan 11 '19 at 5:54
  • $\begingroup$ Yes, and yes. Now, a better way to do all this is to use generating functions.... @Hello_World $\endgroup$ – Angina Seng Jan 11 '19 at 5:56
  • $\begingroup$ 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. $\endgroup$ – nls Jan 11 '19 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.