Hi.
I just managed to put together the hard proof of the explicit, non-recursive formula for the solution of general recurrences of the form
\( a_1 = r_{1,1} \)
\( a_n = \sum_{m=1}^{n-1} r_{n,m} a_m \)
that I mentioned here:
http://math.eretrandre.org/tetrationforu...42#pid5542
The note with the proof is attached to this post. Comments, critique, etc. would be welcomed.
This proves the existence of the explicit non-recursive expression for the coefficients of the regular Schroder function of \( f(z) = e^{uz} - 1 \), and indeed, of the coefficients of regular Schroder functions in general.
So the question now becomes: is there a more "elegant" expression? I'll give some attempts at trying to take a whack at it here.
1. The regular Schroder function (at the natural fixed point 0) coefficients are given by the above recurrence formula, or the general explicit formula, with
\( r_{1,1} = 1 \)
\( r_{n,m} = \frac{u^{n-1}}{1 - u^{n-1}} \frac{m!}{n!} \left{{n \atop m}\right} \).
(where \( \left{{n \atop m}\right} \) is a Stirling number of the 2nd kind.)
Let the resulting coefficients "\( a_n \)" be denoted \( \chi_n \). Then the Schroder function is
\( \chi(z) = \sum_{n=1}^{\infty} \chi_n z^n \).
2. Now, we go and expand these out. The first few coefficients look like:
\( \chi_1 = 1 \)
\( \chi_2 = \frac{u}{-2u + 2} \)
\( \chi_3 = \frac{-2u^3 - u^2}{-6u^3 + 6u^2 + 6u - 6} \)
\( \chi_4 = \frac{6u^6 + 5u^5 + 6u^4 + u^3}{-24u^6 + 24u^5 + 24u^4 - 24u^2 - 24u + 24} \)
\( \chi_5 = \frac{-24u^{10} - 26u^9 - 46u^8 - 45u^7 - 24u^6 - 14u^5 - u^4}{-120u^{10} + 120u^9 + 120u^8 - 240u^5 + 120u^2 + 120u - 120} \).
...
Factoring the denominators and pattern recognition suggests
\( \chi_n = \frac{\sum_{j=n}^{\frac{n(n-1)}{2}} \mathrm{smag}_{n,j} u^j}{(-1)^n n! \prod_{j=1}^{n-1} (1 - u^j), n > 1 \)
where \( \mathrm{smag}_{n,j} \) are the so-called "Schroder function magic numbers".
3. We want to turn this into a recurrence on the numerators. Let \( N_n \) denote the numerator of the nth term \( \chi_n \). Then we have
\( N_n = (-1)^n n! \left(\prod_{j=1}^{n-1} (1 - u^j)\right) \chi_n \).
Now insert the recurrent expression for \( \chi_n \):
\( \begin{align}
N_n &= (-1)^n n! \left(\prod_{j=1}^{n-1} (1 - u^j)\right) \left(\sum_{m=1}^{n-1} \frac{u^{n-1}}{1 - u^{n-1}} \frac{m!}{n!} \left{{n \atop m}\right} \chi_m\right)\\
&= (-1)^n n! \sum_{m=1}^{n-1} \left(\prod_{j=1}^{n-1} (1 - u^j)\right) \frac{u^{n-1}}{1 - u^{n-1}} \frac{m!}{n!} \left{{n \atop m}\right} \chi_m\\
&= (-1)^n n! \sum_{m=1}^{n-1} \left(\prod_{j=1}^{n-1} (1 - u^j)\right) \frac{u^{n-1}}{1 - u^{n-1}} \frac{m!}{n!} \left{{n \atop m}\right} \frac{N_m}{(-1)^m m! \prod_{j=1}^{m-1} (1 - u^j)}\\
&= \sum_{m=1}^{n-1} (-1)^{n-m} \left(\prod_{j=m}^{n-1} (1 - u^j)\right) \frac{u^{n-1}}{1 - u^{n-1}} \left{{n \atop m}\right} N_m\\
&= \sum_{m=1}^{n-1} (-1)^{n-m} \left(\prod_{j=m}^{n-2} (1 - u^j)\right) u^{n-1} \left{{n \atop m}\right} N_m
\end{align} \).
But beyond here we run out of luck. The next step would be to set the sum for \( N_n \) in this and try to solve for a recurrence for the \( \mathrm{smag}_{n,j} \) and then try to come up with an explicit non-recursive formula for that, but it gets hairy and we don't have an expression for the expanded-out product there. So the first order of business here would be to find the explicit, non-recursive formula for the coefficients of
\( \prod_{j=m}^{n-2} (1 - u^j) \).
Any ideas? The degree of the resulting polynomial is \( \sum_{j=m}^{n-2} j = \frac{(n-1)(n-2) - m(m-1)}{2} \).
Also, \( N_1 = -1 \). We don't set it to 1, since if you look at the denominator formula, you'll notice it is equal to -1 there and we have \( \chi_1 = 1 \).
I just managed to put together the hard proof of the explicit, non-recursive formula for the solution of general recurrences of the form
\( a_1 = r_{1,1} \)
\( a_n = \sum_{m=1}^{n-1} r_{n,m} a_m \)
that I mentioned here:
http://math.eretrandre.org/tetrationforu...42#pid5542
The note with the proof is attached to this post. Comments, critique, etc. would be welcomed.
This proves the existence of the explicit non-recursive expression for the coefficients of the regular Schroder function of \( f(z) = e^{uz} - 1 \), and indeed, of the coefficients of regular Schroder functions in general.
So the question now becomes: is there a more "elegant" expression? I'll give some attempts at trying to take a whack at it here.
1. The regular Schroder function (at the natural fixed point 0) coefficients are given by the above recurrence formula, or the general explicit formula, with
\( r_{1,1} = 1 \)
\( r_{n,m} = \frac{u^{n-1}}{1 - u^{n-1}} \frac{m!}{n!} \left{{n \atop m}\right} \).
(where \( \left{{n \atop m}\right} \) is a Stirling number of the 2nd kind.)
Let the resulting coefficients "\( a_n \)" be denoted \( \chi_n \). Then the Schroder function is
\( \chi(z) = \sum_{n=1}^{\infty} \chi_n z^n \).
2. Now, we go and expand these out. The first few coefficients look like:
\( \chi_1 = 1 \)
\( \chi_2 = \frac{u}{-2u + 2} \)
\( \chi_3 = \frac{-2u^3 - u^2}{-6u^3 + 6u^2 + 6u - 6} \)
\( \chi_4 = \frac{6u^6 + 5u^5 + 6u^4 + u^3}{-24u^6 + 24u^5 + 24u^4 - 24u^2 - 24u + 24} \)
\( \chi_5 = \frac{-24u^{10} - 26u^9 - 46u^8 - 45u^7 - 24u^6 - 14u^5 - u^4}{-120u^{10} + 120u^9 + 120u^8 - 240u^5 + 120u^2 + 120u - 120} \).
...
Factoring the denominators and pattern recognition suggests
\( \chi_n = \frac{\sum_{j=n}^{\frac{n(n-1)}{2}} \mathrm{smag}_{n,j} u^j}{(-1)^n n! \prod_{j=1}^{n-1} (1 - u^j), n > 1 \)
where \( \mathrm{smag}_{n,j} \) are the so-called "Schroder function magic numbers".
3. We want to turn this into a recurrence on the numerators. Let \( N_n \) denote the numerator of the nth term \( \chi_n \). Then we have
\( N_n = (-1)^n n! \left(\prod_{j=1}^{n-1} (1 - u^j)\right) \chi_n \).
Now insert the recurrent expression for \( \chi_n \):
\( \begin{align}
N_n &= (-1)^n n! \left(\prod_{j=1}^{n-1} (1 - u^j)\right) \left(\sum_{m=1}^{n-1} \frac{u^{n-1}}{1 - u^{n-1}} \frac{m!}{n!} \left{{n \atop m}\right} \chi_m\right)\\
&= (-1)^n n! \sum_{m=1}^{n-1} \left(\prod_{j=1}^{n-1} (1 - u^j)\right) \frac{u^{n-1}}{1 - u^{n-1}} \frac{m!}{n!} \left{{n \atop m}\right} \chi_m\\
&= (-1)^n n! \sum_{m=1}^{n-1} \left(\prod_{j=1}^{n-1} (1 - u^j)\right) \frac{u^{n-1}}{1 - u^{n-1}} \frac{m!}{n!} \left{{n \atop m}\right} \frac{N_m}{(-1)^m m! \prod_{j=1}^{m-1} (1 - u^j)}\\
&= \sum_{m=1}^{n-1} (-1)^{n-m} \left(\prod_{j=m}^{n-1} (1 - u^j)\right) \frac{u^{n-1}}{1 - u^{n-1}} \left{{n \atop m}\right} N_m\\
&= \sum_{m=1}^{n-1} (-1)^{n-m} \left(\prod_{j=m}^{n-2} (1 - u^j)\right) u^{n-1} \left{{n \atop m}\right} N_m
\end{align} \).
But beyond here we run out of luck. The next step would be to set the sum for \( N_n \) in this and try to solve for a recurrence for the \( \mathrm{smag}_{n,j} \) and then try to come up with an explicit non-recursive formula for that, but it gets hairy and we don't have an expression for the expanded-out product there. So the first order of business here would be to find the explicit, non-recursive formula for the coefficients of
\( \prod_{j=m}^{n-2} (1 - u^j) \).
Any ideas? The degree of the resulting polynomial is \( \sum_{j=m}^{n-2} j = \frac{(n-1)(n-2) - m(m-1)}{2} \).
Also, \( N_1 = -1 \). We don't set it to 1, since if you look at the denominator formula, you'll notice it is equal to -1 there and we have \( \chi_1 = 1 \).