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

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.

• Have you tried writing down a general generating function? – Alex R. May 27 '15 at 22:26
• @AlexR. I am not very familiar with the concept of generating functions, the only thing I've done was brute force, literally do some calculations and hope to something good to appear haha. But how could I find a generating function to this recurrence? – Alufat May 28 '15 at 0:22

## 1 Answer

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

• I've already thought that the general form of this recurrence was somewhat related with Bernoulli numbers because of Faulhaber's formula. But you indirectly gave me the idea of interpolate some values of $a_k(n)$ for fixed $k$ to find the polynomial for each $k$ and try to "heuristically" find out this relation for every $k$. I can't believe I haven't thought anything like that until now hahaha. Thanks! – Alufat May 28 '15 at 19:49
• Yes, nice Idea. An exact solution can be coded very efficiently in a small computer program since all polynomials will actually have rationnal coefficients (Prove it !) :-) – G. Fougeron May 29 '15 at 8:54