<s>[INST] 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).$$
 [/INST] 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.
</s>