# Eliminating a variable from a two-variable linear recurrence

In attempting to enumerate a combinatorial class of objects, I've come to a bivariate recurrence: $$a_{n,k} = 2a_{n,k-1} + (k+1)a_{n-1,k+1} - ka_{n-1,k} - a_{n,k-2} + a_{n-1,k-1}.$$ Together with the initial conditions $a_{0,0} = 1$, $a_{0,k} = 0$ for all $k \geq 1$, and $a_{n,0} = a_{n-1,1}$, all $a_{n,k}$ can be computed.

The sequence that I really care about is $a_{n,0}$, so I'd like a way to eliminate the index $k$ from the recurrence. Are there known techniques to perform this elimination?

A few more details:

• The sequence $\{a_{n,0}\}$ is actually well-known. It satisfies the recurrence $a_{n+1} = (2n+1)a_n + a_{n-1}$ with $a_0 = 1$ and $a_1 = 0$. In fact, I am trying to enumerate a family of generalizations that give similar but more complicated bivariate recurrences from which I'd like to eliminate the auxiliary variable $k$. By generating initial terms for the generalizations, I can conjecture that their one-variable sequences do satisfy linear recurrences with polynomial coefficients (i.e., the family seems to be D-finite).

• I've intentionally left out the details of the combinatorial origin of the recurrence because there are several ad hoc ways to eliminate $k$ for this particular recurrence that do not work for the generalizations.

• The bivariate recurrence comes from a functional equation that I have for $f(z,u)$ (where $[z^nu^k]f(z,u) = a_{n,k}$): $$f(z,u) = \frac{(1-u)^2 + z(1-u)f_u(z,u)}{(1-u)^2 - zu},$$ where $f_u$ denotes $\frac{\partial f}{\partial u}$. This functional equation fully defines the sequence in the sense that you can start with $f(0,0) = 1$ and iterate the equation to obtain arbitrarily many initial terms. The generating function for the sequence I actually want is $f(z,0)$, but simply substituting $u=0$ yields $$f(z,0) = 1 + zf_u(z,0)$$ from which we can only determine that $a_{n,0} = a_{n-1,1}$.

• On the level of generating functions, eliminating the variable $k$ from the recurrence corresponds to turning the functional equation above into a linear differential equation (in $z$) to which $f(z,0)$ is a solution.

• I think the key phrase here is "kernel method in combinatorics". Mar 20, 2016 at 12:53
• @Martin I've seen and used the kernel method in situations where the functional equation involves terms like $f(z,0)$ and $f_u(z,0)$, but I'm not sure it can be applied when there are no univariate terms. Mar 20, 2016 at 12:57
• I don't see how your recurrence can be used to compute all $a_{n,k}$. You have all the $a_{0,k}$, and thus also $a_{1,0}$. However, the equation for $a_{1,k}$ is second-order recurrence in $k$, while you only have one initial condition at $n=1$. The same is true for your differential equation, $z$ is a parameter in the equation, and the most general solution contains an arbitrary function of $z$, unless you specify an initial condition as a function in $z$. Mar 26, 2016 at 0:54
• @Peter The equality $a_{n,0} = a_{n-1,1}$ makes it possible to calculate all $a_{n,k}$ with the recurrence. Mar 26, 2016 at 2:52
• @JayPantone, I probably do not see something obvious. If I am trying to increase $n$ one by one, then for each fixed $n$ I need to find $a_{n,k}$ for all $k$, and $a_{n,0}=a_{n-1,1}$ only gives me one such $a$. Using your recursion relation, I find a second order linear difference equation at fixed $n$, and I need two initial conditions to solve for it. Alternatively, I do not see why your differential equation has a unique solution. Mar 26, 2016 at 3:45

The functional equation: $$f(z,u) = \frac{(1-u)^2 + z(1-u)f_u(z,u)}{(1-u)^2 - zu},$$ represents a first-order linear differential equation w.r.t. to $f(z,u)$ as a function of $u$ (and viewing $z$ as a constant). So instead of plugging $u=0$ directly into this equation, one needs to solve it as an ODE (either manually or with an aid of computer) and plug $u=0$ into its solution to obtain the generating function $f(z,0)$.
• I agree that this works for this particular functional equation, but unfortunately it won't for the more general classes that I am interested in. In this simple case, $f(z,0)$ is the solution to a linear differential equation (in $z$) of order $1$ with polynomial coefficients of degree $2$, but in later cases the corresponding $f(z,0)$ is (for example) conjectured to be the solution to a linear ODE of order $10$ with polynomial coefficients of degree $115$, so I don't think that finding an explicit solution for $f(z,u)$ first is a feasible method. Mar 22, 2016 at 16:57