Property of a recursive integer sequence

Question

Loosely related to this question, I encountered a recursive sequence of integers $(b(j,n))_{j\in\mathbb Z,n\in\mathbb N}$ given by

$$ b(0,1)=-1\qquad b(j,n)=0\text{ if }j<0\text{ or }j\geq n\\ b(j,n+1)=b(j,n)(2j-n)+b(j-1,n)(2j-3n-1)\text{ for all }n\in\mathbb N, j\in\lbrace 0,\ldots,n\rbrace.\tag{1} $$

Note that the non-vanishing terms of $(b(j,n))_{j\in\mathbb Z,n\in\mathbb N}$ form a triangle $$ \begin{matrix} &\underline{j=0}&\underline{j=1}&\ldots&&\\ n=1\,|&-1 &&&&\\ n=2\,|&\hphantom{-}1 &\hphantom{-}2&&&\\ \vdots&-2 &-5&-6&&\\ &\hphantom{-}6 &\hphantom{-}21 &\hphantom{-}24 &\hphantom{-}24&\\ &-24 &-108 &-189 &-120 &-120 \end{matrix} $$

Now explicit calculations suggest that one can attach polynomial weights in $j$ and $n$ to the $b(j,n)$ such that the sum over any row vanishes. More precisely:

Conjecture. For any $n\in\mathbb N$ $$ \sum_{j=0}^{n-1} b(j,n)\big( 32j^3-32(2n-1)j^2 +2(22n^2-30n+13)j-(n-1)(2n-1)(5n-6) \big)=0 $$

I believe this to be true, but so far I was not able to prove it. The problem with induction here is that when using (1) in the induction step, the weight gets $j^4$-terms which then can't be directly connected to (2) anymore.

The obvious way would be trying to find a closed form for the $b(j,n)$ but that seems quite difficult and I was hoping there would be an easier, "intrinsic" (only using the recursion or other properties of the sequence) way of proving this. I'm aware of the generating functions ansatz but as the "weights" in (1) depend on $j,n$ this seems to not work directly either.

Thanks in advance for any answer or comment!

---

Edit: just to vizualize the problem, the first non-vanishing elements of the sequence in question $\scriptstyle\big(b(j,n)(32j^3-32(2n-1)j^2 +2(22n^2-30n+13)j-(n-1)(2n-1)(5n-6))\big)_{j\in\mathbb Z,n\in\mathbb N}$ are given by

$$ \begin{matrix} &\underline{j=0}&\underline{j=1}&\ldots&&\\ n=1\,|&0 &&&&\\ n=2\,|&-12&\hphantom{-}12&&&\\ \vdots&\hphantom{-}180 &-120& -60&&\\ &-1764 &\hphantom{-}84 &\hphantom{-}1104 &\hphantom{-}576&\\ &\hphantom{-}16416 &\hphantom{-}12312 &-13608 &-7920 &-7200 \end{matrix} $$

Now it is evident that any row here sums up to 0.

Answer 1

I don't see why you can't use generating functions (although a huge mess).

Let $F = \sum_{j,n}b(j,n)x^jy^n$ be the generating function.

The recurrence relation becomes a PDE:

$$\frac{\partial F}{\partial x}(2yx + 2yx^2) - \frac{\partial F}{\partial y}(y^2 - 3xy^2) = F(1+yx)$$

Assuming this, you have to prove the following (heavily simplified but still horrendous):

$$[32\frac{\partial^3 F}{\partial x^3} -64y\frac{\partial^3 F}{\partial x^2 \partial y} + 44y^2\frac{\partial^3 F}{\partial x \partial y^2} - 10y^3\frac{\partial^3 F}{\partial y^3} + $$

$$+ 128\frac{\partial^2 F}{\partial x^2} -80y\frac{\partial^2 F}{\partial x \partial y} -57y^2\frac{\partial^2 F}{\partial y^2} + $$

$$+ 90\frac{\partial F}{\partial x} -14y\frac{\partial F}{\partial y} - 6F]\vert_{x = 1} = 0$$

Which we get by encoding the goal as a PDE, then setting $x=1$ which sums the coefficients along each power of $y$, and saying it must equal $0$.

I'm sure a computer could do the rest.

Answer 2

Here are some partial results. I reduce your conjecture to identities involving only polynomials, which are hopefully easier to show.

Observing the rightmost part of the triangle, it seems that $b(n-1,n)=(-1)^n (n!)$, and indeed this fact is easily checked by induction on $n$. Going leftwards by just one step, it also seems that $b(n-2,n)=(-1)^{n-1}n!\frac{(n-1)(n-8)}{12}$, and indeed this fact is also easily checked by induction on $n$. More generally, let us define for integers $0\leq d \lt n$

$$ t(d,n)=\frac{b(n-1-d,n)}{(-1)^{n+d}n!\prod_{k=1}^d (n-k)} \tag{3} $$

So, the two remarks above tell us that $t(0,n)=1$ and $t(1,n)=\frac{n-8}{12}$. In fact, I have checked for $n\leq 10$ the following :

Conjecture 2. When nonzero (i.e. for $n \gt d$), $t(d,n)$ is a polynomial of degree $d$ in $n$.

When translated in terms of $t$, the recursive relation governing $b$ becomes

$$ n(n+1)t(d+1,n+1)-(n-d-1)(n+2d+3)t(d+1,n)=(n-2d-2)t(d,n) \tag{4} $$

Let $h(j,n)= 32j^3-32(2n-1)j^2 +2(22n^2-30n+13)j-(n-1)(2n-1)(5n-6)$. Your sum $S_n=\sum_{j=0}^{n-1} b(j,n)h(j,n)$ can be rewritten as $S_n=\sum_{d=0}^{n-1} h(n-1-d,n)b(n-1-d,n)=(-1)^n n!U_{n}(n)$ where $U_{n}(m)=\sum_{d=0}^{n-1} (-1)^d h(m-1-d,m)t(d,m)\prod_{k=1}^d (m-k)$. Now, I have checked for $n\leq 10$ the following

Conjecture 3. $U_{n}$ is a polynomial (in $m$) divisible by $\prod_{k=1}^{n} (m-k)$.

In particular, we have $U_{n}(n)=0$, which implies your conjecture.