Solving two-dimensional recurrence relation $a_{i,j} = (j-1)a_{i-1,j} + a_{i-1,j+1}$

Question

I've been given this problem. Does anyone know how to approach the following two dimensional recurrence relation?

For all $i, j ≥ 2,$

$a_{i,j} = (j-1)a_{i-1,j} + a_{i-1,j+1}$

where $ a_{1,k} = k$

I've been trying to find a general solution for it for quite a while.

Of course

$a_{2,k} = (k-1)a_{1,k} + a_{1,k+1} = (k-1)k + (k + 1) = k^2 + 1$ $a_{3,k} = (k-1)a_{2,k} + a_{2,k+1} = (k-1)(k^2 + 1) + ((k+1)^2 + 1) = k^3 + 3k + 1$

But is there a way to generalize $a_{i,j}$ for given $i$?

Answer 1

These are the $r$-Bell numbers, which appear as OEIS sequence A108087.