In the theory of univariate linear recurrences with constant coefficients, there is a general method of solving initial value problems based on characteristic polynomials. I would like to ask, if any similar method is known for multivariate linear recurrences with constant coefficients. E.g., if there is a general method for solving recurrences like this: $$f(n+1,m+1) = 2 f(n+1,m) + 3f(n,m) - f(n-1,m), \qquad f(n,0) = 1, f(0,m) =m + 2.$$ Moreover, is their any method for solving recurrences in several variables, when the recurrence goes only by one of the variables? E.g., recurrences like this: $$f(n + 1,m) = f(n,2m) + f(n-1,0), \qquad f(0,m) = m.$$ This second question is equivalent to the question, if there is a method of solving infinite systems of linear univariate recurrences with constant coefficients. That is, using these optics, the second recurrence becomes $$f_m(n + 1) = f_{2m}(n) + f_0(n-1), \qquad f_m(0) = m, \qquad m = 0,1,\ldots .$$ I am not interested in a solution of any specific recurrence, but in solving such recurrences in general, or at least in finding out some of the properties of possible solutions. For instance, for univariate linear recurrences, each solution has a form $$c_1 p_1(n)z_1^n + \ldots + c_k p_k(n) z_k^n,$$ where $c_i$'s are constants, $p_i$'s are polynomials and $z_i$'s are complex numbers. Does any similar property hold for some class of recurrences similar to what I have written?

I have been googling a lot, but have found only methods for some very special cases (in monographs on partial difference equations, etc.), but nothing general enough. I am not asking for a detailed explanation of any method, but references to the literature would be helpful. I don't know much about transforms (like discrete Fourier transform or $z$-transform), but I found certain hints that there could be a method based on these techniques. Is it possible to develop something general enough using transform, i.e., is the study of transforms worth an effort (in the context of solving these types of recurrences)? However, it seems to me that the generalization of the characteristic polynomial method (perhaps, some operator-theoretic approach) could lead to more general results. Has there been any research on this topic?

Thank you very much

  • 1
    $\begingroup$ I've seen recurrences like those you mention detailed in the book Generatingfunctionology (see the binomial coefficent example on page 14) by Wilf that you can download here: math.upenn.edu/~wilf/DownldGF.html Is this what you're looking for? $\endgroup$ – Matt Groff Aug 1 '12 at 14:42
  • $\begingroup$ @MattGroff Yes, the recurrences are of the type I am interested in. I have been aware that it is possible to solve some specific multivariate recurrences by means of GF, but it does not seem to me that this method can be generalized. In the one-variable case as well, I have seen many examples of successful application of GF to specific problems, but I have never seen any general method (since there is a need to know some specific GF). However, I definitely cannot call myself an expert in GF theory, so it is possible I have missed something. I will definitely take a closer look at the link. $\endgroup$ – 042 Aug 1 '12 at 16:20

A technique called kernel-method has been developed to analyse and solve multivariate linear recurrence relations.

This kernel method is presented in the paper Linear recurrences with constant coefficients: the multivariate case by Mireille Bousquet-Mélou and Marko Petkovšek.

Abstract: While in the univariate case solutions of linear recurrences with constant coeffcients have rational generating functions, we show that the multivariate case is much richer: even though initial conditions have rational generating functions, the corresponding solutions can have generating functions which are algebraic but not rational, D-finite but not algebraic, and even non-D-finite.

In section 4 the different types of solutions are analysed and criterias are stated from which the type of solution can be derived. Examples in the bivariate case are provided like (generalised) Dyck paths, Knight walks and some other types of paths.

This kernel method is also presented in section 2.3 Algebraic Generating Functions of Analytic Combinatoriccs in Several Variables by Robin Pemantle and Mark C. Wilson by referring to the material of the above paper.


Set up a bivariate generating function:

$$G(x, y) = \sum_{r, s} f(m, n) x^m y^n$$

and work from there like usual.

For your recurrence $$(n+1,m)=f(n,2m)+f(n−1,0),f(0,m)=m$$ change variable $m = 2^r$ and work from there.


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.