# Closed form of factorial and cascading power sum

Consider the following sum:

$$\sum_{i =0}^{j} \left( \frac{(j-i)^ix^i \ln(x)^{(j-i)}\ln(x)^i}{(j-i)!i!} \right)$$

I can simplify the sum to:

$$\ln(x)^j\sum_{i =0}^{j} \left( \frac{(j-i)^ix^i}{(j-i)!i!} \right)$$ Furthermore I can observe that

$$\frac{1}{(j-i)!(i!)} = \frac{1}{j!} \begin{pmatrix} j \\ i\end{pmatrix}$$

Thus:

$$\frac{\ln(x)^j}{j!}\sum_{i =0}^{j} \left( \begin{pmatrix}j \\ i \end{pmatrix}(j-i)^ix^i \right)$$

But I don't know how to go in for the kill.

Note: This answer does not provide a closed expression but a generating function which might also be helpful for further calculations.

Let's consider OPs sum by exchanging for (my) convenience $i,j$ with $n,k$ and ignoring the factor $\ln(x)^n$.

\begin{align*} \frac{1}{n!}&\sum_{k=0}^n\binom{n}{k}(n-k)^kx^k\tag{1}\\ &=\frac{1}{n!}\sum_{k=0}^n\binom{n}{k}k^{n-k}x^{n-k} \end{align*}

Let $A(z)$ denote the generating function of OPs expression (1). We show

The following is valid:

\begin{align*} A(z) &:= \sum_{n=0}^{\infty}\left(\frac{1}{n!}\sum_{k=0}^n\binom{n}{k}k^{n-k}x^{n-k}\right)z^n\tag{2}\\ &=\exp\left(ze^{xz}\right) \end{align*}

Intermezzo: Bell polynomials

According to Louis Comtet's Advanced Combinatorics section 3.3 ([3a']) the partial Bell polynomials $B_{n,k}=B_{n,k}(x_1,x_2,\ldots,x_{n-k+1})$ are defined via

\begin{align*} B_{n,k}=\frac{n!}{k!}[t^n]\left(\sum_{m\geq 1}x_m\frac{t^m}{m!}\right)^k \end{align*}

We use the coefficient of operator $[t^n]$ to denote the coefficient of $t^n$ in the formal power series.

The specific case $B_{n,k}=B_{n,k}(1,2,\ldots,n-k+1)$ yields:

\begin{align*} B_{n,k}&=\frac{n!}{k!}[t^n]\left(\sum_{m\geq 1}m\frac{t^m}{m!}\right)^k\\ &=\frac{n!}{k!}[t^n]\left(t\sum_{m\geq 0}\frac{t^{m}}{m!}\right)^k\\ &=\frac{n!}{k!}[t^{n}]t^k\exp(kt)\tag{3}\\ &=\frac{n!}{k!}[t^{n-k}]\sum_{m\geq 0}\frac{(kt)^{m}}{m!}\\ &=\frac{n!}{k!}\frac{k^{n-k}}{(n-k)!}\\ &=\binom{n}{k}k^{n-k}\tag{4} \end{align*}

We observe the partial Bell polynomials $B_{n,k}(1,2,\ldots,n-k+1)=\binom{n}{k}k^{n-k}$ are the link between OPs expression and the path to finding the generating function $A(z)$.

Using the expression (3) in (1) we obtain

\begin{align*} \frac{1}{n!}\sum_{k=0}^n&\binom{n}{k}k^{n-k}x^{n-k}\\ &=\sum_{k=0}^n\frac{1}{k!}[t^{n-k}]e^{kt}x^{n-k}\\ &=x^n[t^n]\sum_{k=0}^{\infty}\left(\frac{te^t}{x}\right)^k\frac{1}{k!}\tag{4}\\ &=x^n[t^n]\exp\left(\frac{te^t}{x}\right)\tag{5} \end{align*}

In (4) we changed the upper limit of the index $k$ from $n$ to $\infty$ which does not contribute anything (just adding $0$'s).

From the last expression (5) we finally get

and the claim follows.

Comment:

• In (6) we use expression (5)

• In (7) we use a substitution rule for formal power series:

$$A(z)=\sum_{n=0}^{\infty}a_nz^n=\sum_{n=0}^{\infty}\left([t^n]A(t)\right)z^n$$

• So i'm guessing there isn't a closed form for this? If there is, what is the natural way to convert a generating function into a closed form? – frogeyedpeas Mar 17 '15 at 20:27
• @frogeyedpeas: Maybe not a satisfactory answer, but the best I can give at the moment: I recommend reading the first section in R.P.Stanleys Enumerative Combinatorics "How to count" - He provides us with about 10 small examples and only the simplest has a closed form. The others are represented via generating functions or recurrence relations or by other means and we are invited to accept these more complex structures as basic building blocks for further analysis. – Markus Scheuer Mar 17 '15 at 21:48
• @frogeyedpeas: I also think that there is no unique natural way to find a closed form. It mostly depends on the existing knowledge, routine and techniques. Let's have a look at the three answers so far. They all are different, interesting and could be part of one's repertoire. So each derivation could be regarded as natural approach. The same holds for different ways to derive a closed form (in case a closed form really exists). – Markus Scheuer Mar 17 '15 at 22:01
• @frogeyedpeas: Thanks a lot for accepting my answer and granting the bounty. A hint which might be of interest for you: Today I've answered this question which provides some different techniques around how to find a closed formula. Best regards, – Markus Scheuer Mar 21 '15 at 23:37

Here is an alternate derivation of the generating function by @MarkusScheuer.

Suppose we are trying to evaluate $$A(z) = \sum_{n\ge 0} \frac{z^n}{n!} \sum_{k=0}^n {n\choose k} (kx)^{n-k}.$$

Introduce the integral representation $$(kx)^{n-k} = \frac{(n-k)!}{2\pi i} \int_{|w|=R} \frac{1}{w^{n-k+1}} \exp(kxw) \; dw.$$ which certainly holds for $0\lt R\lt \infty.$

This yields $$A(z) = \sum_{n\ge 0} \frac{z^n}{n!} \sum_{k=0}^n {n\choose k} \frac{(n-k)!}{2\pi i} \int_{|w|=|z|+\epsilon} \frac{1}{w^{n-k+1}} \exp(kxw) \; dw$$

or $$\frac{1}{2\pi i} \int_{|w|=|z|+\epsilon} \sum_{n\ge 0} \frac{z^n}{w^{n+1}} \sum_{k=0}^n \frac{1}{k!} \exp(kxw) w^k \; dw.$$

This is $$\frac{1}{2\pi i} \int_{|w|=|z|+\epsilon} \sum_{k\ge 0} \frac{1}{k!} \exp(kxw) w^k \sum_{n\ge k} \frac{z^n}{w^{n+1}} \; dw.$$ or $$\frac{1}{2\pi i} \int_{|w|=|z|+\epsilon} \sum_{k\ge 0} \frac{1}{k!} \exp(kxw) w^k \frac{z^k}{w^k} \sum_{n\ge 0} \frac{z^n}{w^{n+1}} \; dw.$$ Note that the second sum converges in the chosen annulus $|w|\gt |z|$ which means we may continue to simplify to obtain

$$\frac{1}{2\pi i} \int_{|w|=|z|+\epsilon} \sum_{k\ge 0} \frac{1}{k!} \exp(kxw) z^k \frac{1}{w} \frac{1}{1-z/w} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=|z|+\epsilon} \frac{1}{w-z} \exp(z\exp(xw))\; dw.$$

By the Cauchy Residue Theorem the pole at $w=z$ contributes $$\exp(z e^{xz})$$ which was to be shown.

Let us write $y=\ln x$. The question is equivalent to compute $$a_j(x)=\sum_{i=0}^j\frac{(j-i)^i\;x^i}{(j-i)!\;i!}.$$ An elegant method is to use, as already said, the generating function $$f(x,y)=\sum_{j=0}^\infty a_j(x) y^j=\sum_{j=0}^\infty y^j\sum_{i=0}^j \frac{(j-i)^i}{(j-i)!}\frac{x^i}{i!}.$$

Using the little diagram $$j\uparrow \begin{array}{cccc}\bullet&\bullet&\bullet&\bullet\\ \bullet&\bullet&\bullet&\\ \bullet&\bullet&&\\ \bullet&&&\\&\overrightarrow{i}&&\end{array}$$ we can swap the sums as follows $$\sum_{j=0}^\infty\sum_{i=0}^j=\sum_{i=0}^\infty\sum_{j=i}^\infty,$$ and obtain, after setting $k=j-i$ $$f(x,y)=\sum_{i=0}^\infty\sum_{k=0}^\infty \frac{k^ix^iy^i}{i!}\frac{y^k}{k!}.$$ Performing the sum over $i$ first we obtain $f(x,y)=\sum_k\exp(xyk)\frac{y^k}{k!}$ and easily get the final result $$f(x,y)=\exp\left(y\mathrm{e}^{xy}\right).$$ We note that if $y=\ln x$, $f(x,\ln x)=x^{x^x}$. The required result can be expressed as $$y^j \left[y^j\right]\exp(y\mathrm{e}^{xy}).$$

• Thats very interesting! I had arrived at this sum via the exponent tower $$x^{x^x}$$ I was hoping I could find a closed form to re-express $$x^{x^x}$$ in terms of 3 and x solely, based on the previous two responses it appears that won't be trivial to do – frogeyedpeas Mar 17 '15 at 20:28