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.

secondorder 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. $\endgroup$ – Peter Kravchuk Mar 26 '16 at 3:451more comment