Explicit expression for recursive sums - II

Question

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

Answer 1

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