$\begingroup$

NovaDenizen says the polynomial sequence i wanted to know about has these two recurrence relations

(1) $p_n(x+1) = \sum_{i=0}^{n} (x+1)^{n-i}p_i(x)$

(2) $p_{n+1}(x) = \sum_{i=1}^{x} ip_n(i)$

==

i was trying to calculate the probability of something and i came upon them. i needed to know what this was equal to:

$$p_n(x)=\sum_{k_n=k_{n-1}}^{x}....\sum_{k_3=k_2}^{x} \sum_{k_2=k_1}^{x} \sum_{k_1=1}^{x}k_1k_2...k_n$$

$k \in (1,2,...,x)$.

if you make it continuous and over the reals instead of over the natural numbers then its not too hard to see what that equals.

$$p_n(x) \approx \int_{k_n=0}^{x}...\int_{k_3=k_2}^{x}\int_{k_2=k_1}^{x}k_1k_2k_ndk_1dk_2...dk_n =\dfrac{(x)^{2n}}{2^n n!}$$

i computed some of these and got

$$p_1(x) \approx \frac{x^2}{2}, p_2(x) \approx \frac{x^4}{8}, p_3(x) \approx \frac{x^6}{48}, p_4(x) \approx \frac{x^8}{384}, p_5(x) \approx \frac{x^{10}}{3840},...$$ so im assuming that's the formula.

from the summation formula its easy to see that $$p_1(x)=\sum_{k=1}^x k=\frac{x(x+1)}{2}$$

i spent some time to compute $$p_2(x)=\sum_{k_2=k_1}^x\sum_{k_1=1}^x k_1k_2=x^4/8+(5 x^3)/12+(3 x^2)/8+x/12=x (3 x+1) (x+1) (x+2)/24$$

these agree with the approximations from integrating, which im guessing gives the first terms of $p_n(x)$.

also i think its might be fair to say that $\dfrac{(x)^{2n}}{2^n n!} < p_n(x) < \dfrac{(x+1)^{2n}}{2^n n!}$ if you can use the integral approximation to get lower and upper estimates of $p_n(x)$.

but im wondering what this sequence of polynomials is. i think i can just use the first terms of them to calculate the probabilities i wanted to know well enough, but it wouldn't hurt to know if this sequence of polynomials has a name. thanks.

$\endgroup$ 4

2 Answers

$\begingroup$

(some years later .. !)

Note that your polynomial can be rewritten as$$ \begin{array}{l} p_{\,n} (x) = \sum\limits_{k_{\,n} = k_{\,n - 1} }^x { \cdots \sum\limits_{k_{\,2} = k_{\,1} }^x {\sum\limits_{k_{\,1} = 1}^x {k_{\,1} k_{\,2} \cdots k_{\,n} } } } = \\ = \sum\limits_{\begin{array}{*{20}c} {} \\ {1\, \le \,k_{\,1} \, \le \,k_{\,2} \, \le \, \cdots \, \le \,k_{\,n} \, \le \,x} \\ \end{array}} {\prod\limits_{1\, \le \,j\, \le \,n} {k_{\,j} } } = \left[ \begin{array}{c} x + 1 \\ x - n \\ \end{array} \right] \\ \end{array} $$where the second line reproduces a known representation of the unsigned Stirling Number of 1st kind : that indicated in square brackets.

These numbers are normally defined for non-negative integers at the upper and lower term.

However, there is an interesting extension to the polynomials written as above, which goes through the Eulerian Numbers of 2nd kind, here indicated within double angle brackets, and the binomials (expressed in the extended way through Gamma, or Falling Factorials), or equivalently through the Stirling Numbers of 2nd kind, here in curly brackets.$$ \eqalign{ & \left[ \matrix{ z \cr z - n \cr} \right]\quad \quad \left| \matrix{ \;0 \le {\rm integer }n \hfill \cr \;z \in \mathbb C \hfill \cr} \right.\quad = \cr & = \sum\limits_{\scriptstyle k \atop \scriptstyle \left( {0\, \le \,k\, \le \,n} \right)} {\left\langle {\left\langle \matrix{ n \cr k \cr} \right\rangle } \right\rangle \left( \matrix{ z + k \cr 2n \cr} \right)} = \cr & = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left\{ \matrix{ n + k \cr k \cr} \right\}\left( \matrix{ n - z \cr n + k \cr} \right)\left( \matrix{ n + z \cr n - k \cr} \right)} = \cr & = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( { - 1} \right)^{\,n + k} \left\{ \matrix{ n + k \cr k \cr} \right\}\left( \matrix{ z + k - 1 \cr n + k \cr} \right)\left( \matrix{ n + z \cr n - k \cr} \right)} \cr} $$Refer for instance to the renowned "Concrete Mathematics" at the section on Eulerian Numbers.

Then, since the Stirling N. 1st kind obey to the fundamental recurrence$$ \left[ \matrix{ z + 1 \cr z - n \cr} \right] = z\left[ \matrix{ z \cr z - n \cr} \right] + \left[ \matrix{ z \cr z - n - 1 \cr} \right] $$you get the expression of your polynomial.

$\endgroup$ $\begingroup$

Let $q_n(a,b) = \sum_{k_1=a}^b \sum_{k_2 = k_1}^b \dots \sum_{k_n=k_{n-1}}^b k_1 k_2 \dots k_n$.

$p_n(x) = q_n(1,x)$

$q_1(a,b) = \dfrac{b(b+1)}{2} - \dfrac{a(a-1)}{2} $

$q_n(a,a) = a^n$

$q_{n+1}(a,b) = \sum_{i=a}^b iq_n(a,i) = \sum_{i=a}^b iq_n(i,b)$

$q_{n_1 + n_2 + 1}(a,b) = \sum_{i=a}^b q_{n_1}(a,i)iq_{n_2}(i,b)$

$q_2(a,b) = \sum_{i=a}^b iq_1(a,i) = \sum_{i=a}^b i\left(\dfrac{i(i+1)}{2} - \dfrac{a(a-1)}{2}\right) = \sum_{i=a}^b \dfrac{i^3}{2} + \dfrac{i^2}2 + i\dfrac{a(a-1)}{2}$

That last expression for $q_2$ is solvable as a power sum.

It seems to me that a solution for general $n$ wouldn't be any simpler than Faulhaber's formula.

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy