|
14
|
|
edited Sep 29 2011 at 21:51 |
(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
|
|
edited Sep 29 2011 at 3:34 |
(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
|
|
edited Sep 29 2011 at 3:26 |
(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
|
|
edited Sep 29 2011 at 3:14 |
(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 \left(1 + \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}\right)$$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}$.
|
|
|
|
|
10
|
|
edited Sep 25 2011 at 19:06 |
(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 \left(1 + \sum_{\substack{{-1 sum_{\substack{-1 = m_0 < m_1 < m_2 < \cdots < m_k = n-1}n-1\\ {1 \le k \le n}}}n}}\ \prod_{j=1}^{k} r_{m_j,m_{j-1}+1}\right)$$.
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}$.
|
|
|
|
|
9
|
|
edited Sep 25 2011 at 18:56 |
(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 \left(1 + \sum_{\substack{-1 sum_{\substack{{-1 = m_0 < m_1 < m_2 < \cdots < m_k = n-1n-1}\ {1 \le k \le n}} n}}}\ \prod_{j=1}^{k} r_{m_j,m_{j-1}+1}\right)$$.
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}$.
|
|
|
|
|
8
|
|
edited Sep 25 2011 at 9:25 |
(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 \left(1 + \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}\right)$$.
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}$.
|
|
|
|
|
7
|
|
edited Sep 25 2011 at 9:10 |
(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 \left(1 + \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}\right)$$.
Does that ring a bell better?
|
|
|
|
|
6
|
|
edited Sep 20 2011 at 0:31 |
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?
|
|
|
|
|
5
|
|
edited Sep 19 2011 at 22:21 |
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?
|
|
|
|
|
4
|
|
edited May 30 2011 at 2:48 |
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 = nn\\ 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?
|
|
|
|
|
3
|
|
edited May 30 2011 at 2:42 |
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_{1 sum_{\substack{1 = m_1 < m_2 < \cdots < m_k = n, \ 2 \le k \le n}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?
|
|
|
|
|
2
|
|
edited May 10 2011 at 23:09 |
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)$$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_{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?
|
|
|
|
|
1
|
|
asked May 10 2011 at 3:02 |
Is there a theory about these kinds of recurrence equations? Is this a known formula?
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)$$
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_{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?
|
|
|
