The recurrence $a_k(n) = \sum_{0\leqslant j<n} a_{k-1}(n+j)$

Question

I'm trying to find a closed form expression to the following recurrence relation:

\begin{align} &a_k(0) = 0, \quad \forall k\geqslant 1; \\ &a_k(1) = 1, \quad \forall k\geqslant 1; \\ &a_0(n) = 1, \quad \forall n\geqslant 1; \\ &a_k(n) = \sum_{0\leqslant j<n} a_{k-1}(n+j). \end{align}

The case $k=2$ are particularly interesting, since it gives the pentagonal numbers,

$$ a_2(n) = \sum_{0\leqslant j<n} a_1(n+j) = \sum_{0\leqslant j<n} (n+j) = \binom{2n}{2} - \binom{n}{2} = \frac{n(3n-1)}{2}.$$

But for higher $k$ it seems to behave very "chaotically" (in a not exactly strict sense of this word).

If instead of "$n+j$" one chooses "$n-j$" on the definition, the closed form of the recurrence becomes much more friendly, namely $\binom{n+k-1}{k}$, that is well-known counting way, and even can be extended to the complex function in two variables $\frac{\Gamma(z+w)}{\Gamma(z)\Gamma(w+1)}$. It makes me wonder whether the above recurrence relation also have a combinatorial interest, or even a closed form that can be naturally extended to complex variables.

Answer 1

Not a comprehensive answer yet, but still food for thought : For all $k$, there is a systematic way to compute a closed form formula for $a_k(n)$ valid for all $n$. The steps are the following :

You can easily prove that for all $k$, $a_k(n)$ is a polynomial function of the variable $n$.

Proof :

It is true for $k=0$ since $a_O(n) = 1$. If $a_{k-1}(n)$ is polynomial, then $a_{k-1}(n+j)$ is also a polynomial in $n$ for all $j$ (cf Taylor's theorem for polynomials), and $a_k(n) = \sum_{j=0}^{n-1} a_{k-1}(n+j)$ is a sum of polynomials, Hence a polynomial itself.

Hence, for all $k$ and $n$, $a_{k-1}(n+j)$ is a polynomial function of the variable $j$. Rewrite $a_k(n) = \sum_{j=0}^{n-1} a_{k-1}(n+j)$ leaving only the monomial $j$ terms under the sum. Then using Faulhaber's formula (see Faulhaber's formula on Wikipedia), you can give a closed form expression for $a_k(n)$ without any $j$. This formula is heavily dependent on the concept of Bernoulli numbers (see Bernoulli number on Wikipedia), which arise in several other mathematical fields (they are involved in the closed form fomula for the even integer values of the Riemann zeta function for instance !!!)

Exemple : $k = 1$ $$a_1(n) = \sum_{j=0}^{n-1} a_0(n+j) = \sum_{j=0}^{n-1} 1 = n$$ $k = 2$ : $$a_2(n) = \sum_{j=0}^{n-1} a_1(n+j) = \sum_{j=0}^{n-1} n+j = n \sum_{j=0}^{n-1} 1 + \sum_{j=0}^{n-1} j = n^2 + \frac{n(n-1)}{2}$$

And so on ...