I'm interested in solving a particular non-linear recurrence in two variables:

$$\lambda_{j,k} = (j+k) \lambda_{j,k-1} + \begin{pmatrix} j+k \\ 2 \end{pmatrix} \lambda_{j-1, k-1}.$$

Here $j \geq -1$ and $k \geq 0$, and we have initial conditions:

$\lambda_{-1,k} = 0$ for all $k$;

$\lambda_{j,0} = 0$ for all $j>0$;

$\lambda_{0,0} = 1$.

This is a relation between the leading coefficients of certain polynomials occurring in a problem in modular invariant theory. $\lambda_{-1,k}$ doesn't really make sense in context, but introducing it simplifies the relation and initial conditions nicely. Because of the context, I happen to know that for any prime $p$, $\lambda_{j,k} \neq 0$ mod $p$ unless $j+k \geq p$. This suggests to me that there is a particularly simple solution, possibly a product of binomial coefficients.

Some starting points: Obviously $\lambda_{0,k} = k!$ and it's easy to show that $\lambda_{j,k} = 0$ if $j>k$ and $\lambda_{k,k} = \frac{(2k)!}{2^k}$ for $k \geq 0$. I've tried solving it with generating functions in two variables, but that just produces a truly terrifying PDE of order 2 and degree 4.

  • $\begingroup$ Great answer @Fedor Petrov, thanks a lot! $\endgroup$ – Jon Elmer Apr 3 '19 at 10:48
  • 1
    $\begingroup$ Your recurrence is linear. $\endgroup$ – Richard Stanley Apr 3 '19 at 23:09

Denote $\lambda_{j,k}=(j+k)! a_{j,k}$ (unless $j=-1,k=0$). Then we get $a_{j,k}=a_{j,k-1}+a_{j-1,k-1}/2$. Further denoting $a_{j,k}=2^{-j}b_{j,k}$ we get $b_{j,k}=b_{j,k-1}+b_{j-1,k-1}$ that looks like a Pascal triangle recurrence. So $b_{j,k}=\binom{k}j$ (check the initial conditions also) and $\lambda_{j,k}=2^{-j}(j+k)!\binom{k}j$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.