18
$\begingroup$

I wanted to split the expression $r^k (r+n)!$ as a sum of factorials, where $k ,n \ \in \ \mathbb{Z} \ ;\ k>0$.

For example,

  • $r(r+n)! = (r+n+1)! - (n+1)(r+n)!$

  • $r^2(r+n)! = (r+n+2)! - (2n+3)(r+n+1)! + (n+1)^2 (r+n)!$

And in general,

If $$ r^k (r+n)! = \sum_{m=0}^{k} \lambda_{m} (r+n+m)! $$

where $ \lambda_{m} $ is independent of $r$, find a closed form expression for $\lambda_{m}$.


My Try :

1) I tried to form a two variable recurrence for the expression and solve it such that we can express it in a summation form.

Let $r^k (r+n)! = A(k,n)$

Since $ r^k(r+n)! = r^{k-1}(\overline{r+n+1} - \overline{n+1})(r+n)! = r^{k-1}(r+n+1)! - r^{k-1} (n+1)(r+n)! $

$ \implies A(k,n) = A(k-1 , n+1) - (n+1)A(k-1,n) $

we can fix the initial conditions as $A(k,0) = r^k r!$ and $A(0,n) = (r+n)!$. I tried solving the above using generating functions, but eventually we'll have to find a Mac Lauren Series expansion for $\dfrac{1}{\Gamma \left( n+1 + \frac{2}{x} \right)}$

2) The expression can be rewritten as $$ r^k = \sum_{m=0}^{k} \lambda_{m} (r+n+m)_{m} $$

where $(x)_{y}$ denotes the falling factorial. This resembles the identity $$ r^k = \sum_{m=0}^{k} {k\brace m} (r)_{m} $$

where $ \displaystyle {a\brace b} $ denotes the Stirling Numbers of the Second Kind. So maybe the the coefficients can be expressed in terms of Stirling Numbers.

3) I also tried plugging in values of $r$ and making a system of $k+1$ equations, but it became tedious to solve.


Update (26th November, 2016) : The user @Marko Riedel has discovered a remarkable closed form expression, namely

$$ \lambda_m = (-1)^{k+m} \sum_{p=0}^{k-m} {k\choose p} {k+1-p\brace m+1} n^p $$

I have put a bounty since I feel that there might be alternate solutions to prove (or maybe even simplify) the above proposition. I'm also looking for any references/links to this problem.

Also, the great answers so far reveal that the identity is valid even when $n$ is not an integer.

Any help will be greatly appreciated.

$\endgroup$
  • $\begingroup$ The problem can also be posed as: Given $\lambda^{q}_{-1} = 0, \, \forall q \in \{ 0,1,...,k \}$, $\lambda_0^0 = 1$, $\lambda_{j}^0 = 0, \, \forall j \in \{1,2,...,k\}$ and the recursion $\lambda_m^p = \lambda_{m-1}^{p-1} - (n+m+1)\lambda_{m}^{p-1}$, compute $\lambda_{j}^k \, \forall j \in \{0,1,...,k\}$. Now, I have to see how to solve this recursion problem. $\endgroup$ – Dhruv Kohli - expiTTp1z0 Nov 24 '16 at 6:19
13
$\begingroup$

We are given that

$$r^k (r+n)! = \sum_{m=0}^k \lambda_m (r+n+m)!$$

and seek to determine the $\lambda_m$ independent of $r.$ We claim and prove that

$$\lambda_m = (-1)^{k+m} \sum_{p=0}^{k-m} {k\choose p} {k+1-p\brace m+1} n^p.$$

With this in mind we re-write the initial condition as

$$r^k = \sum_{m=0}^k \lambda_m m! {r+n+m\choose m}.$$

We evaluate the RHS starting with $\lambda_m$ using the EGF of the Stirling numbers of the second kind which in the present case says that

$${k+1-p\brace m+1} = \frac{(k+1-p)!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+2-p}} \frac{(\exp(z)-1)^{m+1}}{(m+1)!} \; dz.$$

We obtain for $\lambda_m$

$$(-1)^{k+m} \sum_{p=0}^{k-m} n^p {k\choose p} \frac{(k+1-p)!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+2-p}} \frac{(\exp(z)-1)^{m+1}}{(m+1)!} \; dz.$$

The inner term vanishes when $p\ge k+2$ but in fact even better it also vanishes when $p\gt k-m$ which implies $m+1\gt k+1-p$ because $(\exp(z)-1)^{m+1}$ starts at $[z^{m+1}]$ and we are extracting the term on $[z^{k+1-p}].$

Hence we may extend $p$ to infinity without picking up any extra contributions to get

$$(-1)^{k+m} \frac{k!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+2}} \frac{(\exp(z)-1)^{m+1}}{(m+1)!} \sum_{p\ge 0} (k+1-p) \frac{n^p z^p}{p!} \; dz.$$

This is

$$(-1)^{k+m} \frac{k!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+2}} \frac{(\exp(z)-1)^{m+1}}{(m+1)!} ((k+1)-nz) \exp(nz) \; dz.$$

Substitute this into the outer sum to get

$$(-1)^{k} \frac{k!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+2}} ((k+1)-nz) \exp(nz) \\ \times \sum_{m=0}^k {r+n+m\choose m} (-1)^m \frac{(\exp(z)-1)^{m+1}}{m+1} \; dz.$$

We have

$${r+n+m\choose m} \frac{1}{m+1} = {r+n+m\choose m+1} \frac{1}{r+n}$$

and hence obtain

$$\frac{(-1)^{k}}{r+n} \frac{k!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+2}} ((k+1)-nz) \exp(nz) \\ \times \sum_{m=0}^k {r+n+m\choose m+1} (-1)^m (\exp(z)-1)^{m+1} \; dz.$$

We may extend $m$ to $m\gt k$ in the remaining sum because the term $(\exp(z)-1)^{m+1}$ as before starts at $[z^{m+1}]$ which would then be $\gt k+1$ but we are extracting the coefficient on $[z^{k+1}],$ which makes for a zero contribution.

Continuing we find

$$-\sum_{m\ge 0} {r+n+m\choose r+n-1} (-1)^{m+1} (\exp(z)-1)^{m+1} \\ = 1 - \frac{1}{(1-(1-\exp(z)))^{r+n}} = 1 - \exp(-(r+n)z).$$

We get two pieces on substituting this back into the main integral, the first is

$$\frac{(-1)^{k}}{r+n} \frac{k!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+2}} ((k+1)-nz) \exp(nz) \; dz \\ = \frac{(-1)^{k}}{r+n} (k+1)! \frac{n^{k+1}}{(k+1)!} - \frac{(-1)^k}{r+n} k! n \frac{n^{k}}{k!} = 0.$$

and the second is

$$\frac{(-1)^{k+1}}{r+n} \frac{k!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+2}} ((k+1)-nz) \exp(nz) \exp(-(r+n)z) \; dz \\ = \frac{(-1)^{k+1}}{r+n} \frac{k!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+2}} ((k+1)-nz) \exp(-rz) \; dz \\ = \frac{(-1)^{k+1}}{r+n} (k+1)! \frac{(-r)^{k+1}}{(k+1)!} - \frac{(-1)^{k+1}}{r+n} k! n \frac{(-r)^k}{k!} \\ = \frac{1}{r+n} (k+1)! \frac{r^{k+1}}{(k+1)!} + \frac{1}{r+n} k! n \frac{r^k}{k!} \\ = \frac{1}{r+n} r^{k+1} + \frac{1}{r+n} n r^k = r^k.$$

This concludes the argument.

Addendum Nov 27 2016. Markus Scheuer proposes the identity

$$\lambda_m = (-1)^{m+k} \sum_{p=m}^k {p\brace m} {k\choose p} (n+1)^{k-p}.$$

To see that this is the same as what I presented we extract the coefficient on $[n^q]$ to get

$$(-1)^{m+k} \sum_{p=m}^k {p\brace m} {k\choose p} {k-p\choose q}.$$

Now we have

$${k\choose p} {k-p\choose q} = \frac{k!}{p! q! (k-p-q)!} = {k\choose q} {k-q\choose p}.$$

We get

$$(-1)^{m+k} {k\choose q} \sum_{p=m}^k {p\brace m} {k-q\choose p}.$$

We now introduce with deployment of the Egorychev method in mind

$${k-q\choose p} = {k-q\choose k-q-p} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k-q-p+1}} (1+z)^{k-q} \; dz.$$

This certainly vanishes when $p\gt k-q$ so we may extend $p$ to infinity, getting for the sum

$$(-1)^{m+k} {k\choose q} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k-q+1}} (1+z)^{k-q} \sum_{p\ge m} {p\brace m} z^p \; dz.$$

Using the OGF of the Stirling numbers of the second kind this becomes

$$(-1)^{m+k} {k\choose q} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k-q+1}} (1+z)^{k-q} \prod_{l=1}^m \frac{z}{1-lz} \; dz.$$

Now put $z/(1+z) = w$ to get $z = w/(1-w)$ and $dz = 1/(1-w)^2 \; dw$ to obtain

$$(-1)^{m+k} {k\choose q} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{k-q}} \frac{1-w}{w} \frac{1}{(1-w)^2} \prod_{l=1}^m \frac{w/(1-w)}{1-lw/(1-w)} \; dw \\ = (-1)^{m+k} {k\choose q} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{k-q+1}} \frac{1}{1-w} \prod_{l=1}^m \frac{w}{1-w-lw} \; dw \\ = (-1)^{m+k} {k\choose q} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{k-q+1}} \frac{1}{1-w} \prod_{l=1}^m \frac{w}{1-(l+1)w} \; dw \\ = (-1)^{m+k} {k\choose q} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{k-q+2}} \frac{w}{1-w} \prod_{l=2}^{m+1} \frac{w}{1-lw} \; dw \\ = (-1)^{m+k} {k\choose q} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{k-q+2}} \prod_{l=1}^{m+1} \frac{w}{1-lw} \; dw \\= (-1)^{m+k} {k\choose q} {k-q+1\brace m+1}.$$

This is the claim and we are done.

$\endgroup$
  • 1
    $\begingroup$ Instructive answer! (+1) $\endgroup$ – Markus Scheuer Nov 25 '16 at 8:24
  • $\begingroup$ (+1) Elegant and powerful answer! Do you mind if I keep the question open for some more time by adding a bounty? I'd like to see what other approaches can there be. $\endgroup$ – MathGod Nov 25 '16 at 15:04
  • $\begingroup$ @MarkusScheuer Thank you. I realized on completion of the computation that we never used the differential in the integrals which means it can be done using formal power series only. $\endgroup$ – Marko Riedel Nov 25 '16 at 20:41
  • $\begingroup$ @IshanSingh Feel free to put a bounty on the question. I would like to point out that I discovered the closed form. $\endgroup$ – Marko Riedel Nov 25 '16 at 20:53
  • $\begingroup$ @MarkoRiedel Do you mean that the closed form that you discovered is a new result? That's amazing! $\endgroup$ – MathGod Nov 26 '16 at 1:25
7
$\begingroup$

This answer is based upon an analysis of @MarkoRiedel's instructive answer. Although it looks somewhat different it is essentially the same.

We consider OPs identity in the form \begin{align*} r^k=\sum_{m=0}^k\lambda_m \binom{n+r+m}{m}m!\tag{1} \end{align*}

The essence

The binomial identity (1) in terms of corresponding generating functions is the relationship \begin{align*} e^{-rz}=\frac{e^{(n+1)z}}{e^{(n+1+r)z}}\tag{2} \end{align*}

We will see that the generating function of $r^k$ is essentially the LHS of (2) whereas the generating function of the sum of the RHS in (1) corresponds essentially to the coefficients of $z^n$ of the RHS of (2).

The claim

The following is valid \begin{align*} \lambda_m=(-1)^{m+k}\sum_{p=m}^k {p\brace m}\binom{k}{p}(n+1)^{k-p}\qquad\qquad 0\leq m\leq k \end{align*}

In the following we use the coefficient of operator $[z^k]$ to denote the coefficient of $z^k$ in a series. This way we can write e.g. \begin{align*} \binom{r}{k}=[z^k](1+z)^r\qquad\text{and}\qquad r^k=k![z^k]e^{rz} \end{align*}

We obtain \begin{align*} r^k&=(-1)^kk![z^k]e^{-rz}\\ &=(-1)^kk![z^k]\frac{e^{(n+1)z}}{e^{(n+1+r)z}}\tag{3}\\ &=(-1)^kk![z^k]\frac{e^{(n+1)z}}{\left(1-\left(e^z-1\right)\right)^{n+1+r}}\\ &=(-1)^kk![z^k]e^{(n+1)z}\sum_{m=0}^\infty\binom{-(n+1+r)}{m}(e^z-1)^m\tag{4}\\ &=(-1)^kk![z^k]e^{(n+1)z}\sum_{m=0}^k\binom{n+r+m}{m}(-1)^m(e^z-1)^m\tag{5}\\ &=(-1)^kk![z^k]e^{(n+1)z}\sum_{m=0}^k\binom{n+r+m}{m}(-1)^mm!\sum_{p=m}^\infty{p\brace m} \frac{z^p}{p!}\tag{6}\\ &=(-1)^kk!\sum_{m=0}^k\binom{n+r+m}{m}(-1)^mm!\sum_{p=m}^k{p\brace m} \frac{1}{p!}[z^{k-p}]e^{(n+1)z}\tag{7}\\ &=(-1)^kk!\sum_{m=0}^k\binom{n+r+m}{m}(-1)^mm!\sum_{p=m}^k{p\brace m} \frac{1}{p!}\cdot\frac{(n+1)^{k-p}}{(k-p)!}\tag{8}\\ &=\sum_{m=0}^k\binom{n+r+m}{m}m!\left((-1)^{m+k}\sum_{p=m}^k{p\brace m}\binom{k}{p}(n+1)^{k-p}\right)\tag{9}\\ \end{align*} and the claim follows.

Comment:

  • In (3) we make an extension which looks simple but carries some power. In the following line we can rewrite the denominator to prepare for a binomial series expansion and it also contains the series for the Stirling numbers of the second kind.

  • In (4) we apply the binomial series expansion.

  • In (5) we use the binomial identity \begin{align*} \binom{-p}{q}=\binom{p+q-1}{q}(-1)^q \end{align*} We also set the upper limit of the inner sum to $k$ by noting that the expansion of $(e^z-1)^m$ starts with $z^m$ and since we are looking for the coefficient of $z^k$ we can restrict the limit to $m=k$.

  • In (6) we the use the following exponential series representation of the Stirling numbers of the second kind. \begin{align*} \sum_{p=m}^\infty{p\brace m} \frac{z^p}{p!}=\frac{(e^z-1)^m}{m!} \end{align*}

  • In (7) we do some rearrangements, apply the coefficient of operator rule \begin{align*} [z^{p-q}]A(z)=[z^{p}]z^qA(z) \end{align*} and restrict the upper limit of the inner sum to $k$ since the exponent $k-p$ has to be non-negative.

  • In (8) we select the coefficient of $z^{k-p}$ of $e^{(n+1)z}$.

  • In (9) we do some more rearrangements and collect terms to easier see $\lambda_m$.

$\endgroup$
  • $\begingroup$ @MarkoRiedel: Hi Marko! I did some meditations about your answer. Regards, $\endgroup$ – Markus Scheuer Nov 26 '16 at 18:43
  • $\begingroup$ I just checked your proposal and will verify it several times more. It looks to be quite brilliant work! We now have two closed forms answering the question by the OP. Congratulations! (+1). Would you consider adding a proof that the two closed forms for $\lambda_m$ are equivalent? I am sure you will get the bounty. $\endgroup$ – Marko Riedel Nov 26 '16 at 21:04
  • $\begingroup$ I suspect the proof of equivalence would work by extracting the coefficient on $[n^q]$ from your formula and showing that it matches my coefficient on $[n^p].$ Could be that there is something simple here that I am not seeing. If yes let me know. $\endgroup$ – Marko Riedel Nov 26 '16 at 21:36
  • $\begingroup$ @MarkoRiedel: I would like to extract the generating functions from your approach and show this way the formulas are equal. In fact they are not the same. In your last part one summand is zero. I optimized somewhat the calculation by switching from $\frac{e^{nz}}{e^{(n+r)z}}$ to $\frac{e^{(n+1)z}}{e^{(n+1+r)z}}$ and so avoiding the part with zero summand. $\endgroup$ – Markus Scheuer Nov 26 '16 at 21:47
  • $\begingroup$ I have added a proof that your formula is the same as mine, which you are cordially invited to consult. It is an interesting exercise, which I hope the reader will enjoy. $\endgroup$ – Marko Riedel Nov 26 '16 at 23:25
7
+100
$\begingroup$

The exposition herewith is not going to add anything substantial to the valuable answers already provided by Markus and by Marko, but is intended just to show a couple of other ways to prove the assertion.
Clearly, for $r \in R$, $(r+n)!$ and $(r+n+k)!$ make sense only if represented through the $\Gamma$ function. So, as already shown, we actually are to prove that

$$ \begin{gathered} r^{\,q} = \sum\limits_{0\, \leqslant \,j\, \leqslant \,q} {\lambda _{\,q,\;j} \left( {r + n + j} \right)^{\,\underline {\,j\,} } } = \sum\limits_{0\, \leqslant \,j\, \leqslant \,q} {\lambda _{\,q,\;j} \left( {r + n + 1} \right)^{\,\overline {\,j\,} } } = \hfill \\ = \sum\limits_{0\, \leqslant \,j\, \leqslant \,q} {j!\lambda _{\,q,\;j} \left( \begin{gathered} r + n + j \\ j \\ \end{gathered} \right)} = \sum\limits_{0\, \leqslant \,j\, \leqslant \,q} {\left( { - 1} \right)^{\,j} j!\lambda _{\,q,\;j} \left( \begin{gathered} - r - n - 1 \\ j \\ \end{gathered} \right)} \quad \quad \left| \begin{gathered} \;r \in \mathbb{R}\,,\quad n \in \mathbb{Z} \hfill \\ \;0 \leqslant q \in \mathbb{Z}\; \hfill \\ \;\lambda _{\,q,\;j} \;\text{indep}\text{.}\,\text{from}\;r \hfill \\ \end{gathered} \right. \hfill \\ \end{gathered} $$

This is just an identity between polynomials, expressed in different basis, so it is assured that a linear combination, with coefficients independent from $r$, exists and is unique.

  • 0) the straight one $$ \begin{array}{l} r^{\,q} = \sum\limits_{0\, \le \,j\, \le \,q} {\lambda _{\,q,\;j} \left( {r + n + 1} \right)^{\,\overline {\,j\,} } } \quad \Rightarrow \\ \left( {s - \left( {n + 1} \right)} \right)^{\,q} = \sum\limits_{0\, \le \,j\, \le \,q} {\lambda _{\,q,\;j} s^{\,\overline {\,j\,} } } = \\ = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,q} \right)} {\left( { - 1} \right)^{\,q - k} \left\{ \begin{array}{c} q \\ k \\ \end{array} \right\}\left( {s - \left( {n + 1} \right)} \right)^{\,\overline {\,k\,} } } = \\ = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,q} \right)} {\left( { - 1} \right)^{\,q - k} \left\{ \begin{array}{c} q \\ k \\ \end{array} \right\}\sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,k} \right)} {\left( \begin{array}{c} k \\ j \\ \end{array} \right)\left( { - \left( {n + 1} \right)} \right)^{\,\overline {\,k - j\,} } s^{\,\overline {\,j\,} } } } = \\ = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,q} \right)} {\left( { - 1} \right)^{\,q - k} \left\{ \begin{array}{c} q \\ k \\ \end{array} \right\}\sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,k} \right)} {\left( { - 1} \right)^{\,k - j} \left( \begin{array}{c} k \\ j \\ \end{array} \right)\left( {n + 1} \right)^{\,\underline {\,k - j\,} } s^{\,\overline {\,j\,} } } } \quad \Rightarrow \\ \end{array} $$

$$ \lambda _{\,q,\;j} = \left( { - 1} \right)^{\,q - j} \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,q} \right)} {\left\{ \begin{gathered} q \\ k \\ \end{gathered} \right\}\left( \begin{gathered} k \\ j \\ \end{gathered} \right)\left( {n + 1} \right)^{\,\underline {\,k - j\,} } } = \left( { - 1} \right)^{\,q - j} \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,q} \right)} {\frac{{k!}} {{j!}}\left\{ \begin{gathered} q \\ k \\ \end{gathered} \right\}\left( \begin{gathered} n + 1 \\ k - j \\ \end{gathered} \right)} \tag{0} $$

  • 1) : development of $r^q ==> (-r-n-1+n+1)^q$
    The last of the four expressions formulated above suggests that we might try and develop $r^q$ as follows $$ \begin{gathered} r^{\,q} = \left( { - 1} \right)^{\,q} \left( { - r} \right)^{\,q} = \left( { - 1} \right)^{\,q} \left( { - r - n - 1 + n + 1} \right)^{\,q} = \left( { - 1} \right)^{\,q} \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,q} \right)} {\left( \begin{gathered} q \\ k \\ \end{gathered} \right)\left( {n + 1} \right)^{\,q - k} \left( { - r - n - 1} \right)^{\,k} } = \hfill \\ = \left( { - 1} \right)^{\,q} \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,q} \right)} {\left( \begin{gathered} q \\ k \\ \end{gathered} \right)\left( {n + 1} \right)^{\,q - k} \sum\limits_{\left( {0\, \leqslant } \right)\,j\,\left( { \leqslant \,k} \right)} {j!\left\{ \begin{gathered} k \\ j \\ \end{gathered} \right\}\left( \begin{gathered} - r - n - 1 \\ j \\ \end{gathered} \right)} } \hfill \\ \end{gathered} $$ which compared with the starting identity gives:

    $$ \lambda _{\,q,\;j} = \left( { - 1} \right)^{\,q - j} \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,q} \right)} {\left( \begin{gathered} q \\ k \\ \end{gathered} \right)\left\{ \begin{gathered} k \\ j \\ \end{gathered} \right\}\left( {n + 1} \right)^{\,q - k} } = \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,q} \right)} {\left( { - 1} \right)^{\,q - k} \left( \begin{gathered} q \\ k \\ \end{gathered} \right)\left( {n + 1} \right)^{\,q - k} \left( { - 1} \right)^{\,k - j} \left\{ \begin{gathered} k \\ j \\ \end{gathered} \right\}} \tag{1} $$

which is the answer anticipated by Markus Scheuer.

  • 2) Eulerian Numbers and Worpitzky identity
    The target identity is quite similar to the Worpitzky's Identity, except for having the binomial diagonally shifted. So it is not difficult to convert into the standard Worpitzky form $$ r^{\,q} = \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,q} \right)} {\left\langle \begin{gathered} q \hfill \\ k \hfill \\ \end{gathered} \right\rangle } \left( \begin{gathered} r + k \\ q \\ \end{gathered} \right) = \; \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,q} \right)} {\left\langle \begin{gathered} q \hfill \\ k \hfill \\ \end{gathered} \right\rangle } \sum\limits_{\left( {0\, \leqslant } \right)\,j\,\left( { \leqslant \,q} \right)} {\left( \begin{gathered} - n + k - 1 - j \\ q - j \\ \end{gathered} \right)\left( \begin{gathered} r + n + j \\ j \\ \end{gathered} \right)} $$ where the Eulerian Numbers can be expressed in different ways, among which $$ \begin{gathered} \left\langle \begin{gathered} q \\ m \\ \end{gathered} \right\rangle = \sum\limits_{0\, \leqslant \,k\, \leqslant \,m} {\left( { - 1} \right)^{\,k} \left( \begin{gathered} q + 1 \\ k \\ \end{gathered} \right)\left( {m + 1 - k} \right)^{\,q} } = \hfill \\ = \sum\limits_{0\, \leqslant \,k\,\left( { \leqslant \,q - m} \right)\,} {\left( { - 1} \right)^{\,q - m + k} \left( \begin{gathered} q + 1 \\ m + 1 + k \\ \end{gathered} \right)\,k^{\,q} } = \hfill \\ = \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,q} \right)} {\left( { - 1} \right)^{\,q - k - m} \left\{ \begin{gathered} q \\ k \\ \end{gathered} \right\}\left( \begin{gathered} q - k \\ m \\ \end{gathered} \right)\,\;k!} \hfill \\ \end{gathered} $$ So this leads to express $\lambda _{\,q,\;j} $ as

    $$ \lambda _{\,q,\;j} = \frac{1} {{j!}}\sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,q} \right)} {\left\langle \begin{gathered} q \hfill \\ k \hfill \\ \end{gathered} \right\rangle } \left( \begin{gathered} - n + k - 1 - j \\ q - j \\ \end{gathered} \right) = \frac{1} {{j!}}\sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,q} \right)} {\left\langle \begin{gathered} q \hfill \\ k \hfill \\ \end{gathered} \right\rangle } \left( { - 1} \right)^{\,q - j} \left( \begin{gathered} q + n - k \\ q - j \\ \end{gathered} \right) \tag{2} $$

In conclusion let's note that the identities above could be conveniently put into matricial notation, whereby one can more easily get the properties of $\lambda$. For instance identity (1) can be written as:

$$ \mathbf{\Lambda }(n) = \mathbf{B}^{\, - \,\mathbf{(n + 1)}} \;\mathbf{St}_{\,\mathbf{1}} ^{\, - \,\mathbf{1}} = \;\left( {\mathbf{St}_{\,\mathbf{1}} \,\mathbf{B}^{\,\,\mathbf{(n + 1)}} } \right)^{\, - \,\mathbf{1}} \quad \Rightarrow \quad \Lambda _{\,q,\,m} (n) = \left. {\frac{1} {{q!}}\nabla _{\,x} ^m \,x^{\,q} } \right|_{\,x\, = \, - \,(n + 1)} \tag{3} $$

where all matrices are LT (indexed from $0$), and
$\mathbf{B}$ is the Pascal matrix
$\mathbf{St}_{\,\mathbf{1}}$ is the matrix of the unsigned Stirling N. of 1st kind
$\nabla_{\,x}$ is the backward Delta
so that the last identity indicates the connection with the Newton backward development of $r^q$, that comes of no surprise.
Given the wide range of properties of the Pascal matrix, the formula above allows to transfer them to $\mathbf{\Lambda }(n) \mathbf{St}_{\,\mathbf{1}}$ and $ \mathbf{St}_{\,\mathbf{1}} \mathbf{\Lambda }(n)$.

Finally, it shall be remarked that the exposition made extends quite evenly to $r$ and $n$ complex.

  • ---- Addendum -----*

Might be interesting to signalize that, for $n$ non-negative integer, $\lambda$ can be expressed in terms of the so called r-Stirling Numbers ( re. e.g. to this paper by A. Z. Broder ), denoted as $\left\{ \begin{gathered} n \\ m \\ \end{gathered} \right\}_r $.
Accordingly, formula (1) can be rewritten as

$$ \begin{gathered} \lambda _{\,q,\;j} (n) = \left( { - 1} \right)^{\,q - j} \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,q} \right)} {\left( \begin{gathered} q \\ k \\ \end{gathered} \right)\left\{ \begin{gathered} k \\ j \\ \end{gathered} \right\}\left( {n + 1} \right)^{\,q - k} } \quad \left| {\;\;0 \leqslant n \in \;\;\mathbb{Z}\,} \right.\quad = \hfill \\ = \left( { - 1} \right)^{\,q - j} \left\{ \begin{gathered} q + n + 1 \\ j + n + 1 \\ \end{gathered} \right\}_{n + 1} = \left( { - 1} \right)^{\,q - j} \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n + 1} \right)} {\left( { - 1} \right)^{\,k} \left[ \begin{gathered} n + 1 \\ n + 1 - k \\ \end{gathered} \right]\left\{ \begin{gathered} q + n + 1 - k \\ n + 1 + j \\ \end{gathered} \right\}} \hfill \\ \end{gathered} \tag{a} $$

thereby getting an additional expression in terms of standard Stirling Numbers. ($\left[ \begin{gathered} n \\ m \\ \end{gathered} \right]$ being the unsigned Stirling N. of 1st kind).

$\endgroup$
  • $\begingroup$ Thank you for contributing this interesting contextual material, which I checked, except for $(3)$. This takes it to a whole new level. Quite instructive to see that you were able to streamline the argument by @MarkusScheuer for the expansion in terms of powers of $(n+1).$ (BTW what was the purpose of the re-write of the powers of $-1$ in the formula in $(1)$?) The connection to Eulerian numbers is quite special to observe and we now have three closed forms on the page, thus establishing a useful reference. (+1). $\endgroup$ – Marko Riedel Nov 27 '16 at 23:05
  • $\begingroup$ I never would have imagined when I first obtained the formula in terms of powers of $n$ that this problem would reveal itself to have so many interesting connections to other types of combinatorial numbers. Thanks again! $\endgroup$ – Marko Riedel Nov 27 '16 at 23:06
  • $\begingroup$ @MarkoRiedel: thanks for your appreciation. I am glad that all three we have given different connections of this problem with other combinatorial expressions. I find the conversion of base of polynomials a fascinating field, specially when put in matrix notation. The purpose of the second rewriting of (1) is in fact to show better how it can be put in matrix form: the powers of the Pascal M. $\mathbf {B^q}$ are in fact $\binom{n} {m} q^{(n-m)}$, and $St_1(n,m)(-1)^{(n-m)}=St_2^{-1}(n,m)$ etc. $\endgroup$ – G Cab Nov 27 '16 at 23:24
  • 1
    $\begingroup$ I just finished verifying your addendum (proof $(0)$). I congratulate you on your mastery of the Knuth notation for rising and falling factorials and the relevant identities, which we ought to see more of at MSE. Are you referencing Concrete Mathematics by any chance? It looks like your post in its present form will get the bounty. $\endgroup$ – Marko Riedel Nov 28 '16 at 2:58
  • $\begingroup$ @MarkoRiedel: Concrete Mathematics has been and is for me the top reference for learning discrete maths, notation and definition domain included. Upon that I have been delighting myself for some time to explore the change of basis of polynomials, which comes out to be very interesting when put in matrix notation. For instance, the Jordan decomposition of $\mathbf{\Lambda }$ is quite neat, and providing ties still to other combinatorial constructs .. but space here is constrained. $\endgroup$ – G Cab Nov 28 '16 at 10:02
4
$\begingroup$

Start with $$ \newcommand{\stirtwo}[2]{\left\{#1\atop#2\right\}} \begin{align} r^k &=(-1)^k((n+1)-(r+n+1))^k\tag{1}\\[9pt] &=(-1)^k\sum_{j=0}^k\binom{k}{j}(-r-n-1)^j(n+1)^{k-j}\tag{2}\\ &=\sum_{j=0}^k\sum_{m=0}^j(-1)^k\binom{k}{j}(n+1)^{k-j}\binom{-r-n-1}{m}\stirtwo{j}{m}m!\tag{3}\\ &=\sum_{m=0}^k\color{#C00000}{\sum_{j=m}^k(-1)^{k-m}\binom{k}{j}(n+1)^{k-j}\stirtwo{j}{m}}\binom{r+n+m}{m}m!\tag{4} \end{align} $$ Explanation:
$(1)$: rewrite $r=-((n+1)-(r+n+1))\vphantom{\sum\limits_{m=0}^j}$
$(2)$: apply the Binomial Theorem
$(3)$: $x^j=\sum\limits_{m=0}^j\binom{x}{m}\stirtwo{j}{m}m!$
$(4)$: change order of summation and use $\binom{-r-n-1}{m}=(-1)^m\binom{r+n+m}{m}$

Thus, if we set $$ \lambda_m=(-1)^{k-m}\sum_{j=m}^k\binom{k}{j}(n+1)^{k-j}\stirtwo{j}{m}\tag{5} $$ then $(4)$ becomes $$ r^k=\sum_{m=0}^k\lambda_m\binom{r+n+m}{m}m!\tag{6} $$ which is equivalent to your statement when $r+n\in\mathbb{Z}$.

$\endgroup$
  • $\begingroup$ Good to see additional participation. This looks to be the same almost step-by-step of proof number one by @GCab. $\endgroup$ – Marko Riedel Nov 28 '16 at 19:21
  • $\begingroup$ @MarkoRiedel: Ah, I see. There were so many answers that extensively used pretty ugly integrals, that I just started writing this answer. I didn't notice that part of GCab's answer was essentially the same as what I was writing. $\endgroup$ – robjohn Nov 28 '16 at 19:30
  • $\begingroup$ @robjohn, well indeed it is the same formula as the (1) in my answer, with explanation of the passages: could be kept for that. $\endgroup$ – G Cab Nov 29 '16 at 16:44
  • $\begingroup$ straight to the point, very nice (+1) $\endgroup$ – tired Dec 1 '16 at 11:26
1
$\begingroup$

We can rewrite the condition $\enspace\displaystyle\sum\limits_{m=0}^k\lambda_{k,m}(r+n+m)! =r^k (r+n)!\enspace$ as $$\sum\limits_{m=0}^k \lambda_{k,m} (x+m)^{\underline{m}}=(x-n)^k $$ by substituting $\enspace r\enspace $ with $\enspace x-n$ .

Using the method of differences of Discrete Mathematics with $\enspace\Delta f(x):=f(x+1)-f(x)\enspace$ for

any polynomial $ f(x)$, $\enspace\displaystyle \Delta^{n+1}:=\Delta(\Delta ^n)\enspace$ and therefore

first $\enspace\displaystyle \Delta^n f(x)= \sum\limits_{j=0}^n (-1)^{n-j}\binom{n}{j}f(x+j)\enspace$ and second $\enspace\displaystyle \Delta^l (x+m)^{\underline{m}} =m^{\underline{l} }(x+m)^{ \underline{m-l} }$

for $\enspace m\geq l\enspace $ and $\enspace \Delta^l (x+m)^{\underline{m}}=0\enspace $ for $\enspace m<l\enspace $ it follows with $\enspace f(x):=(x-n)^k\enspace$ : $$\sum\limits_{m=l}^k \lambda_{k,m} m^{\underline{l} }(x+m)^\underline{m-l}= \Delta^l \sum\limits_{m=0}^k \lambda_{k,m} (x+m)^\underline{m}=$$ $$=\Delta^l (x-n)^k =\sum\limits_{j=0}^l (-1)^{l-j}\binom{l}{j}(x-n+j)^k$$ With $\enspace x:=-(l+1) \enspace $ and therefore $\enspace (x+m)^\underline{m-l}=0\enspace $ for $\enspace m>l\enspace $ and deviding the equation by $\enspace l! \enspace $ we get $$\lambda_{k,l}=\frac{(-1)^k}{l!}\sum\limits_{j=0}^l (-1)^j\binom{l}{j}(n+1+j)^k \enspace .$$

Hint:

$\lambda_{k,l}:=\lambda_{k,l}(n)\enspace $ with $\enspace n\in\mathbb{C}\enspace $ is one of several useful generalizations of the Stirling numbers of the second kind $\enspace \displaystyle{k\brace l}:=(-1)^{k+l}\lambda_{k,l}(-1) \,$ .

$\endgroup$

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.