Fibonacci-like sequence

Question

Fix three integers $a, b, c$ and consider a sequence of integers $a_{i,j}$ defined, for $i \ge 0, j \ge 0$, recursively as follows:

$a_{i,0}=1$ for every $i$, $a_{0,j}=a+bj+cj^2$ and, for $i \ge 1, j \ge 1$, $$a_{i,j}=a_{i,j-1}+a_{i-1,j}.$$ Is there a closed formula for the $a_{i,j}$'s?

Answer 1

As for the Fibonacci sequence, let us find a basis.

1. If $a_{0,j} = 0$, then $a_{ij} = \binom{i+j-1}{j}$.
2. If $a_{0,j} = 1$, then $a_{ij} = \binom{i+j}{j}$.
3. If $a_{0,j} = j+1$, then $a_{ij} = \binom{i+j+1}{j}$.
4. If $a_{0,j} = \frac{(j+1)(j+2)}2$, then $a_{ij} = \binom{i+j+2}{j}$.

Any quadratic polynomial $a+bj+cj^2$ is an affine combination of $0$, $1$, $j+1$, $\frac{(j+1)(j+2)}2$. The answer will be the combination of $\binom{i+j-1}{j}$, $\binom{i+j}{j}$, $\binom{i+j+1}{j}$, $\binom{i+j+2}{j}$ with the same coefficients.

If I have solved the linear system correctly, one gets $$a_{ij} = (1-a)\binom{i+j-1}{j} + (a-b+c) \binom{i+j}{j} + (b-3c) \binom{i+j+1}{j} + 2c \binom{i+j+2}{j}$$

Note that for $i=j=0$ this formula yields $a_{00} = a$, which was not well-defined in the question (but does not participate in the recurrence and is therefore irrelevant).

Answer 2

I believe the pattern simplifies to \begin{align} a_{ij} = \binom{i+j-1}{j} & + \binom{i+j-1}{j-1}a + \binom{i+j}{j-1}b \\ & + \left[ \binom{i+j-1}{j-1} + 3\binom{i+j-1}{j-2} + 2\binom{i+j-1}{j-3} \right] c. \end{align}

The triangle of coefficients of $c$ is in the OEIS if you reverse the rows; it's A125165 which has a nice expression as a Riordan array.

Note: I had started on this before I saw Ivan Izmestiev's answer; I believe our claims are compatible.