If we have the recurrence relation
$$\sum_{j=0}^k a_{n-j}c_j = 0$$
for all $n\geq k$ and $\lambda_1,\cdots,\lambda_s$ are the (complex) roots of
$$P(\lambda) = \sum_{j=0}^k c_j\lambda^j$$
with multiplicities $m_1,\cdots,m_s$, then we may write
$$a_n = \sum_{i=1}^s \lambda_i^n Q_i(n),$$
where $Q_i(n)$ is a polynomial of degree at most $m_i-1$.
What if we have a recurrence of the form
$$\sum_{\mathbf{s}\in S} c_{\mathbf{s}}a_{\mathbf{n}-\mathbf{s}} = 0,$$
where $S$ is a set of vectors in $\mathbb{Z}_{\geq 0}^N$ and $\mathbf{n}\in\mathbb{Z}_{\geq 0}^N$ so that each component of $\mathbf{n}$ is $\geq$ the corresponding component of any $\mathbf{s}\in S$. Can one find a similarly nice closed form for $a_{\mathbf{n}}$, possibly using the zero set of
$$P(x_1,\cdots,x_N) = \sum_{\mathbf{s}\in S} c_{\mathbf{s}} \prod_{i=1}^N x_i^{\mathbf{s}_i}?$$
I've been able to deduce that the generating function
$$f(x_1,\cdots,x_N) = \sum_{\mathbf{n}\in\mathbb{Z}_{\geq 0}^N} a_{\mathbf{n}}\prod_{i=1}^N x_i^{\mathbf{n}_i}$$
satisfies
$$f(x_1,\cdots,x_N)P(x_1,\cdots,x_N) = Q(x_1,\cdots,x_N)$$
for some polynomial $Q$ with nonzero terms only at $\prod_{i=1}^N x_i^{\mathbf{t}_i}$ for vectors $t$ that are $\leq$ some element of $S$ in all components, with strict $<$ holding in at least one component - an analogue of the first step of solving a standard one-dimensional linear recurrence. But I'm afraid I can't figure out how to continue from here, or even if one can.