4
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ I think the key phrase here is "kernel method in combinatorics". $\endgroup$
    – Martin Rubey
    Mar 20, 2016 at 12:53
  • 1
    $\begingroup$ @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. $\endgroup$
    – Jay Pantone
    Mar 20, 2016 at 12:57
  • $\begingroup$ 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$. $\endgroup$
    – Peter Kravchuk
    Mar 26, 2016 at 0:54
  • $\begingroup$ @Peter The equality $a_{n,0} = a_{n-1,1}$ makes it possible to calculate all $a_{n,k}$ with the recurrence. $\endgroup$
    – Jay Pantone
    Mar 26, 2016 at 2:52
  • $\begingroup$ @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. $\endgroup$
    – Peter Kravchuk
    Mar 26, 2016 at 3:45

1 Answer 1

Reset to default
1
$\begingroup$

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)$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Jay Pantone
    Mar 22, 2016 at 16:57

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.