Is there a theory about these kinds of recurrence equations? Is this a known formula?

2011-05-10T03:02:06Z

(New information at bottom)

Hi.

For a while, I've been toying around with solving recurrence equations of the form

$$a_1 = r_{1,1}$$ $$a_n = \sum_{m=1}^{n-1} r_{n,m} a_m$$

What are these kind of recurrence equations called? Does one have any references for any general theory behind them?

The goal is to try to find a non-recursive formula for the coefficients of what is called the "Schroder function" of $e^{uz} - 1$, which satisfies the functional equation

$$\chi(e^{uz} - 1) = u \chi(z)$$.

This function can be expressed as

$$\chi(z) = \sum_{n=1}^{\infty} \chi_n z^n$$

with

$$\chi_1 = 1$$ $$\chi_n = \sum_{m=1}^{n-1} \frac{u^{n-1}}{1 - u^{n-1}} \frac{m!}{n!} S(n, m) \chi_m$$

a recurrence of the given form, where $S(n, m)$ is a Stirling number of the 2nd kind.

I managed to find the following formula:

$$a_n = r_{1,1} \sum_{\substack{1 = m_1 < m_2 < \cdots < m_k = n\\ 2 \le k \le n}}\ \prod_{j=2}^{k} r_{m_j, m_{j-1}},\ n > 1$$

which sums over $2^{n-2}$ terms, namely, all subsets of the integer interval from 1 to $n$ that contain 1 and $n$. However, is there a way to simplify this for the case I gave, where $r_{n,m} = \frac{u^{n-1}}{1 - u^{n-1}} \frac{m!}{n!} S(n, m)$? I note that in cases like the Bernoulli numbers, these kind of recurrences have solutions expressible as nested sums or as products over many fewer terms than above (with a simple linear index). Is such a thing also possible here with the $r_{n,m}$ I just gave? If so, how? Also, is the above formula already known?

ADDENDUM (19 Sep 2011): I later found out on a different group (the Usenet newsgroup sci.math) that such a recurrence may be called a "full-history recurrence", though that term seems a little more general than just referring to the specific kind of sum recurrence mentioned above, and googling it did not turn up much (much less the solution formula mentioned above! (and too bad you can't google math formulas!)), and much of what it did turn up seemed to have to do more with the recurrence in the context of algorithmic theory and computer science than with just pure maths. Is there a better name or something more useful I might try looking up?

EDIT (25 Sep 2011): There is another form of this formula, for the indexing

$$a_0 = \alpha$$, $$a_{n+1} = \sum_{m=0}^{n} r_{n,m} a_m$$.

This version goes as

$$a_n = \alpha \sum_{\substack{-1 = m_0 < m_1 < m_2 < \cdots < m_k = n-1\\ 1 \le k \le n}}\ \prod_{j=1}^{k} r_{m_j,m_{j-1}+1},\ n > 0$$.

Does that ring a bell better? Notice how we can get, e.g. the Bernoulli numbers by setting $\alpha = 1$, $r_{n,m} = -{n \choose m} \frac{1}{n - m + 1}$.

EDIT/ADD #2 (28 Sep 2011): Unfortunately, Helms' answer did not help very much. However, my access to academic resources is somewhat limited. It would be nice to have a direct reference to something containing the mentioned solution formula or a suitable equivalent and the specific kind of linear recurrence I'm asking about (the general form that is, not necessarily the "Schroder" one above), and also discussion of them of course.

EDIT/ADD #3 (29 Sep 2011): Yeah. "Eigensequence" did not seem to yield much on Google (incl. Google Scholar and Google Books). It looks to be much too broad. Certainly didn't find anything with the solution formulas I mentioned. Could this usage be peculiar to the OEIS site?

Answer by Gottfried Helms for Is there a theory about these kinds of recurrence equations? Is this a known formula?

2011-05-10T08:46:45Z

I don't know what else this may be called. But if the coefficients $r_{n,m}$ are written as lower triangular matrix $R$ and the coefficients $a_n$ as column-vector $A$ then this is an eigenvector-problem at eigenvalue $\lambda =1$ :

$ \qquad R*A=A*\lambda = A*1$

(I should note, that the formulation of the problem indicates, that the diagonal of $R$ at least from the second row on seems to be zero here because the sum-index goes only to rowindex $n$ minus 1)
Note 2: in the OEIS as well as in its associated electronic journal I've seen the term "eigensequence" and "invariant sequence" with the same meaning.

Example:

$ \qquad \small \begin{array} {rrrrrr} & & & & & | & 1 \\ & & & & & | & 2 \\ & R*&A =&A & & | & 7 \\ & & & & & | & 33 \\ & & & & & | & 201 \\ - & - & - & - & - & - & - \\ 1 & . & . & . & . & | & 1 \\ 2 & . & . & . & . & | & 2 \\ 1 & 3 & . & . & . & | & 7 \\ 1 & 2 & 4 & . & . & | & 33 \\ 2 & 3 & 4 & 5 & . & | & 201 \end{array} $

Here we have, for a rowindex $n$ : $ \qquad \sum_{m=1}^{n-1} R_{n,m}*A_m = A_n$

Is there a theory about these kinds of recurrence equations? Is this a known formula? - MathOverflow

Is there a theory about these kinds of recurrence equations? Is this a known formula?

Answer by Gottfried Helms for Is there a theory about these kinds of recurrence equations? Is this a known formula?