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.

  • 1
    $\begingroup$ There's a recurrence relation. $p_{n+1}(x) = \sum_{i=1}^{x} ip_n(i)$, and $p_n(x+1) = \sum_{i=0}^{n} (x+1)^{n-i}p_i(x)$ $\endgroup$ – NovaDenizen Apr 20 '14 at 1:57
  • $\begingroup$ ooh cool. thanks a lot! i guess i noticed the first one when i was looking at the sum, but not the second one! i have no idea how you got that, looks very strange to me. $\endgroup$ – buckwheats Apr 20 '14 at 2:21
  • 1
    $\begingroup$ That assumes $p_0(x) = 1$. Maybe it would be better written $p_n(x + 1) = (x+1)^n + \sum_{i=1}^{n}(x+1)^{n-i}p_i(x)$. $p_n(x+1)$ is $(x+1)^n$ plus the sum of all sequences of length $j$ and $\le x$ followed by $n-j$ instances of $x+1$. $\endgroup$ – NovaDenizen Apr 20 '14 at 14:26
  • $\begingroup$ thanks for explaining. i see what's going on now, well not fully see it like i would be confident enough to write that recursion myself and defend it, but pretty close. when you take derivatives of each side from that recursion and evaluate at $x=0$ you can get $2n$ linear equations (each derivative you take gets you a new equation) in the $2n$ coefficients of $p_n$, and the first, say, $2$ coefficients to $p_n$ only depend on the first two of the others, so its not really that bad to calculate them, and those are the most useful ones to know. $\endgroup$ – buckwheats Apr 21 '14 at 3:59

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


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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.