1
$\begingroup$

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}$

$\endgroup$
  • $\begingroup$ Are you familiar with the theory in the case of linear recurrence relations in one variable? In this case one can write down an answer involving no summation symbols. $\endgroup$ – Qiaochu Yuan Jul 14 '14 at 23:39
  • $\begingroup$ You're referring to the case of constant coefficients where one considers the the auxiliary polynomial and proceeds to write the solution as a linear combination of its roots? $\endgroup$ – DAS Jul 15 '14 at 4:17
  • $\begingroup$ Yep. In more than one variable it's sometimes possible to do nice things involving finding the generating function. $\endgroup$ – Qiaochu Yuan Jul 15 '14 at 4:22
  • $\begingroup$ I do know a little bit about generating functions although I have not extensively studied them. I'm aware that it is sometimes possible to use a generating function to obtain a 'nice' solution via algebraic manipulations. However, I do not think a generating function will always help you out. Even if it could help you out, unless you have an extensive amount of experience with them or get lucky it seems like there is a good chance you'd miss out on this fact, perhaps after some extensive (frustrating) algebraic manipulation. $\endgroup$ – DAS Jul 16 '14 at 7:01
  • $\begingroup$ So, I'd be interested in knowing if there is a way to determine if a solution more efficient than expanding out the recurrence summation is obtainable via manipulation of some generating function(s), instead of a 'maybe'. Then manipulating some generating function(s) for a long time, ending up with nothing, and then not even knowing if the generating function approach won't help or if you just missed something. $\endgroup$ – DAS Jul 16 '14 at 7:04

Your Answer

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

Browse other questions tagged or ask your own question.