Given a linear a recurrence relation. It is possible to express a solution in terms of summations, products, and the coefficients which appear in the recurrence. For example, in the case of a single index, assuming $x_0$ constant:
$ x_n = \sum_{j=0}^{n-1}[a_{n,j}x_j] \\ \quad = (a_{n,0} + \sum_{j=1}^{n-1}[a_{n,j}a_{j,0}] + \sum_{j_1=2}^{n-1} \sum_{j_2=1}^{j_1-1}[a_{n,j_1}a_{j_1,j_2}a_{j_2,0}] + . . . \\ \qquad + \sum_{j_1=n-1}^{n-1}\sum_{j_2=n-2}^{j_1-1}...\sum_{j_{n-1}=1}^{j_{n-2}-1}[a_{n,j_1}a_{j_1,j_2}...a_{j_{n-2},j_{n-1}}a_{j_{n-1},0}])x_0 $
What I'm interested in, is whether or not it's possible to determine if a more 'compact' solution exists in terms of addition, subtraction, multiplication, and division, and the original coefficient functions in the recurrence, or, more generally, in terms of some specified set of functions and/or constants (e.g. elementary functions). By 'compact' I mean 'compact' with respect to a specified set of functions and/or constants, call it the 'representation set'. To clarify further, a form which requires less function calls than the summation form given above (or more generally some specified form which is also in terms of the supplied set of functions).
If it is possible to determine if a more compact form exists, is there an algorithm to find such a form?
I'll give two examples to motivate the gist of what I'm getting at.
For each natural number or zero, m, let $e_m$ represent the $m^{th}$ elementary symmetric polynomial where we allow multiset inputs of arbitrary length. i.e. $m>0$ then $e_m$[$\emptyset$]$= 0$, $\forall x (e_0[x] = 1)$, $\forall x = (x_j)_{j=1}^{n} (e_m[x] = \sum_{1 \leq j_1<j_2<...<j_m \leq n}[x_{j_1}x_{j_2}...x_{j_m}])$
Example 1:
Consider the binomial coefficient recurrence (with its typical boundary conditions) $$ {n \choose m} = {n-1 \choose m} + {n-1 \choose m-1} $$ The typical representation of the solution is in terms of factorials: $$ {n \choose m} = \frac{n!}{m!(n-m)!} $$ Which is easily converted into the product form: $$ {n \choose m} = \prod_{j=1}^{m}[\frac{n-(j-1)}{j}] $$ On the other hand if we didn't know this and naively expanded the summation in the recurrence we would end up with $$ {n \choose m} = \sum_{1 \leq j_1<j_2<...<j_m \leq n}[1] $$ Furthermore if we allow elementary symmetric polynomials in our representation set then we can write $$ {n \choose m} = e_m[(1)_{j=1}^{n}] $$
Example 2:
Consider the recurrence: $$e_{m,n} = e_{m,n-1}+ne_{m-1,n-1} \land e_{0,n} = 1 \land (m>n \lor m<0) \rightarrow (e_{m,n} = 0)$$ If we expand the sum and refer to some properties of the elementary symmetric polynomials we get $$e_{m,n} = \sum_{1 \leq j_1<j_2<...<j_m \leq n}[j_1 j_2...j_m] = e_m[(j)_{j=1}^{n}] $$ but this summation can also be more compactly represented by noticing the relation to the stirling numbers of the first kind. If $s_{m,n}$ represents the stirling number of the first kind, then we can use the relation $e_{m,n} = (-1)^{m}s_{n+1,n+1-m}$ and the explicit formula for s: $$s_{n,m}=\frac{(2n-m)!}{(m-1)!}\sum_{k=0}^{n-m}\frac{1}{(n+k)(n-m-k)!(n-m+k)!}\sum_{j=0}^{k}\frac{(-1)^{j} j^{n-m+k} }{j!(k-j)!}.$$ to obtain a formula for $e_{m,n}$