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

  • 1
    $\begingroup$ It should be $a(n+1)=g_n(1,2,3,4,\ldots)$ in A008934. $\endgroup$
    – BillyJoe
    May 11 at 21:58
  • 1
    $\begingroup$ More generally a conjecture is $g_n(k-1, k, k+1, \ldots )=$ column $k$ of A093729, for $k \ge 0$. $\endgroup$
    – BillyJoe
    May 12 at 19:41
  • 1
    $\begingroup$ 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$. $\endgroup$
    – BillyJoe
    May 13 at 8:11
  • 1
    $\begingroup$ 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. $\endgroup$
    – BillyJoe
    May 13 at 8:20

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

  • $\begingroup$ 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$? $\endgroup$ May 24 at 1:59
  • 1
    $\begingroup$ 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. $\endgroup$ May 24 at 2:11

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.