I wanted to find a recurrence relation for partitioning an integer $n$ into exactly $3$ parts
To be clear, I know the formula $P(n,k)=P(n-1,k-1)+P(n-k,k)$, but I want to derive a relation involving ONLY partitions into 3 parts.
I tried to do this combinatorially, but I could not see any direct patterns to derive the recurrence relation from.
Using this answer, I was able to understand why there is a bijection between the number of partitions of $n$ into $3$ parts and the number of partitions of $n$ such that the largest part is exactly $3$.
And so the only option that I have learned in my combinatorics class is to use generating functions. However I only have converted from recurrence relations TO generating functions.
I attempted to go in the reverse direction in the following manner.
The generating function as seen in that post is:
$$G(x) = \frac{x^3}{(1-x)(1-x^2)(1-x^3)}=\frac{x^3}{1-x-x^2+x^4+x^5-x^6}$$
Taking $G(x)$ as a arbitrary sum of the recurrence relation coefficients
$$(1-x-x^2+x^4+x^5-x^6) \sum_{n\ge 0} a_nx^n = x^3$$
Multiplying and equating coefficients it must be
$$a_3-a_2-a_1=1\implies a_3=a_2+a_1+1$$
Well obviously $1$ and $2$ can not be summed into using the number $3$ so $a_1 =0, a_2 = 0$.
$3 = 3$ is the only way, so $a_3=1$, which works with the recurrence relation
$4 = 3+1$ (or $4=1+1+2$ in the other side of the bijection) so $a_4=1$.
but then $a_4 \ne a_3 + a_2 +1$, so the relation I derived literally only works for $a_3$ (I naively thought I could extend it to all $n$).
So I attempted to find the $a_n$ terms for some $n$ when multiplied out
$$(1-x-x^2+x^4+x^5-x^6)(a_0 + \dots+a_{n-6}x^{n-6}+a_{n-5}x^{n-5}+a_{n-4}x^{n-4}+a_{n-3}x^{n-3}+a_{n-2}x^{n-2}+a_{n-1}x^{n-1}+a_{n}x^{n} + \dots)$$
So collecting terms $x^n$ and equating to $0$ since there is no $x^n$ on the RHS
$$a_n-a_{n-1}-a_{n-2}+a_{n-4}+a_{n-5}-a_{n-6}= 0$$
Hence $$\boxed{a_n=a_{n-1}+a_{n-2}-a_{n-4}-a_{n-5}+a_{n-6} \quad \forall n\ge 6 }$$
And by evaluating manually $a_0=0,a_1=0,a_2=0,a_4=1,a_5=2,a_6=3$. Then the Recurrence relation does work when I want to find $a_6$ ( and I assume it works for the rest).
Is this the only way I can find the recurrence relation? How would someone find this sum of $5$ terms (which skips $a_{n-3}$) combinatorially or intuitively? I worry that I have complicated the situation more than needed.