MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

(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?

13 minor clarifications + dating

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

12 added 431 characters in body

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

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

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: 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.

11 found another mistake
10 that should fix it now
9 trying to correct formatting error