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

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

• Is it just me, or is there no bound on the number of r:s? That is, the set of r:s that $a_n$ depend on is unique for each $a_n.$ It seems like this would trivially give that EVERY sequence can be expressed as a "recurrence" of this type. Then I see no reason why one should be able to solve such recurrences in general. – Per Alexandersson May 10 '11 at 4:24
• ? The r_(n,m) are given. – The_Sympathizer May 10 '11 at 5:32
• (That is, we consider them a "known" piece of information.) Notice how I said "of the form" -- which means the r_(n,m) are just a placeholder. Nothing is assumed about what they are in order to make the general formula I gave, just as we don't need to know what r_n is to say that if a_n = r_n + a_(n-1) then a_n = sum_{j=1...n} r_j (assuming a_1 = r_1), despute that a judicious choice of r_n will give any sequence. And I also mentioned a specific sequence of r_(n,m) I'm interested in, and if, in that case, there is a formula of a form akin to that of the formula for Bernoulli numbers, etc. – The_Sympathizer May 10 '11 at 5:42

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$

• This is interesting but does not seem to suggest an obvious way of simplifying (reducing the number of terms) in the case given. – The_Sympathizer May 30 '11 at 2:34
• @Mike3: True. It focuses the first part of your question, how these recurrences are called and what theory might be behind them (eigensequences, for instance, to look for). I've no idea how to simplify such recurrences in general, and because for the left triangular matrix there are infinitely many variants possible such a solution must depend on very tight restrictions for the generation-rule of the entries of that matrix, and for your example I've also no helpful idea. – Gottfried Helms May 30 '11 at 6:25
• I tried looking up "eigensequence" on Google (incl. Google Scholar and Google Books) but it didn't really help. 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? – The_Sympathizer Sep 29 '11 at 21:52
• @mike3: what I recall for sure is that I found this term in some article in the "jornal of integer sequences" (which is indeed tightly related to the OEIS), and may be it was unjustified to assume that it is a term generally used elsewhere... – Gottfried Helms Oct 1 '11 at 19:08