# Explicit expression for recursive sums - II

A twist on just unfolded recursive summation formula. Let polynomials in nonnegative integer variables $$t_1,t_2,\dots$$ be defined by the recurrence: $$\begin{split} g_0 &= 1, \\ g_k(t_1,t_2,\dots,t_k) &= \sum_{j=0}^{t_1} g_{k-1}(t_2+j,t_3+j,\dots,t_k+j)\qquad (k\geq 1). \end{split}$$ Can $$g_k(t_1,t_2,\dots,t_k)$$ be explicitly expressed in terms of $$t_1,t_2,\dots,t_k$$ or via known combinatorial entities?

First few values are: $$\begin{split} g_0 &= 1,\\ g_1(t_1) &= 1+t_1,\\ g_2(t_1,t_2) &= (1+t_1)(1+t_2) + \frac{t_1(1+t_1)}2,\\ g_3(t_1,t_2,t_3) &= \frac12 \left(t_1^{2}+\left(2 t_2 + t_3 +3\right) t_1 +\left(1+t_2 \right) \left(t_2 +2 t_3 +2\right)\right) \left(1+t_1 \right) \end{split}$$

In the case of equal arguments, the values $$\big(g_k(t,t,\dots,t)\big)_{k\geq 0}$$ apparently represent the row sums of the $$t$$-th power of the matrix $$T$$ defined in OEIS A097712 and also the $$t$$-th column of table in OEIS A125860.

In particular, $$\big(g_k(1,1,\dots,1)\big)_{k\geq 0}$$ form OEIS A016121 defined as the number of tuples $$(a_1=1, a_2, ..., a_k)$$ satisfying $$a_i \leq a_{i+1} \leq 2a_i$$ for each $$i=1,2,\dots,k-1$$.

• It should be $a(n+1)=g_n(1,2,3,4,\ldots)$ in A008934. May 11 at 21:58
• More generally a conjecture is $g_n(k-1, k, k+1, \ldots )=$ column $k$ of A093729, for $k \ge 0$. May 12 at 19:41
• A generalization of this function and the one in the linked question could be: $h_k(t_1,t_2,\dots,t_k):=\sum_{j_1=0}^{t_1} \sum_{j_2=0}^{t_2+s_1(j_1)} \sum_{j_3=0}^{t_2+s_2(j_1,j_2)} \dots \sum_{j_k=0}^{t_k+s_{k-1}(j_1,\ldots,j_{k-1})} 1$. For $g_k$ we have $s_n(j_1,\ldots, j_n) = \sum_{m=1}^n j_m$. Another interesting case is $s_n(j_1,\ldots, j_n) = rj_{n-1}$, for example with $r=2$. May 13 at 8:11
• It seems that B.W.J. Irwin tried some of these nested sums: see A254439, A002449 and this that includes a generalization and several example sequences, A101481, A132616. Maybe one day I will write a program to check if there is some other sequence left at the OEIS that can be expressed in this way. May 13 at 8:20

I originally saw the idea that inspired me to this answer here.

From the statement it follows that

$$g_k(t_1, t_2, \dots, t_k) - g_k(t_1 - 1, t_2, \dots, t_k) = g_{k-1}(t_2+t_1, t_3+t_1, \dots, t_k+t_1).$$

Generally, one can express shift in the argument of analytic function with the operator exponent

$$f(x+a) = e^{a\frac{\partial}{\partial x}}f(x),$$

Let's denote $$D_k = \frac{\partial}{\partial t_k}$$, then the recurrence above rewrites as

$$(1-e^{-D_1}) g_k = e^{t_1 (D_2+D_3+\dots + D_k)}g_{k-1},$$

We can't invert $$(1-e^{-D_1})$$ operator directly because it doesn't distinguish between $$0$$ and $$1$$.

However we know that $$g_k(0, t_2, \dots, t_k) = g_{k-1}(t_2, \dots, t_k)$$, hence we can just solve the equation above for higher degrees of $$t_1$$, meaning that it's sufficient to find $$D_1 g_k$$:

$$D_1 g_k = \frac{D_1}{1-e^{-D_1}}e^{t_1(D_2+\dots+D_k)} g_{k-1}$$

Now let $$I_k$$ be the integrating operator over $$t_k$$ such that $$[t_k^0]I_k f(t_k, \dots)=0$$, we can express $$g_k$$ as

$$g_k(t_1, t_2, \dots, t_k) = \left[1 + I_1 \cdot \frac{D_1}{1-e^{-D_1}} \cdot e^{t_1(D_2+\dots+D_k)} \right]g_{k-1}(t_2, \dots, t_k).$$

Substituting it for $$g_{k-1}$$ and up to the very end, we get

$$g_k(t_1, t_2, \dots, t_k) = \prod\limits_{j=1}^k \left(1+I_j \cdot \frac{D_j}{1-e^{-D_j}} \cdot e^{t_j(D_{j+1}+\dots+D_k)} \right) \cdot 1,$$

assuming that the product unravels left-to-right as $$j$$ grows and then is applied to the constant $$1$$.

### Example for $$k=1$$

The expression in this case is simply

$$g_1(t_1) = \left(1+I_1 \frac{D_1}{1-e^{-D_1}}\right) \cdot 1$$

The exponent operator rewrites as

$$\frac{D_1}{1-e^{-D_1}} = \frac{1}{\sum\limits_{k=1}^\infty \frac{(-D_1)^{k-1}}{k!}} = \frac{1}{1-\frac{D_1}{2}+O(D_1^2)} = 1+\frac{D_1}{2}+O(D_1^2).$$

When it is applied to $$1$$, it yields $$1$$, then $$I_1 \cdot 1 = t_1$$, as the integration makes sure that it is $$0$$ for $$t_1=0$$.

Then, adding $$1$$ the result is, indeed, $$g_1 = 1+t_1$$.

• Thank you! This is quite a interesting but somewhat unusual representation, and I do not see right away what kind of benefits it provides. Say, can it be used to speed up evaluation of $g_k$? May 24 at 1:59
• I think, computationally you could use it to get the explicit representation of $g_k$ as a multivariate polynomial of $t_1, \dots, t_k$. Generally you can compute the result of applying the polynomial $g(D)$ of $D=\frac{\partial}{\partial x}$ to the polynomial $f(x)$ as $$g(D) f(x) = [g(x^{-1})\{f(x)\}],$$ where $[\cdot]$ and $\{\cdot\}$ are linear transforms such that $[x^k]=\frac{x^k}{k!}$ and $\{x^k\}=k!x^k$. I wrote a bit more about it some time ago in this article for the univariate case. May 24 at 2:11