Linear recurrences with constant coefficients: The multivariate case (Q1591138)

Let \(H=\{h_1,\dots,h_k\}\) be a fixed set of vectors with \(d\) integer coordinates. If \(n=(n_1,\dots,n_d)\) is a vector of \(d\) non-negative integers, then write \(\bar{x}^n\) for \(x_1^{n_1}\cdots x_d^{n_d}\). This paper studies multivariate generating functions of the form \(\sum_n a_n \bar{x}^n\) whose coefficients satisfy a linear recurrence relation \(a_n=\sum_{h\in H}c_h a_{n+h}\) in which each \(c_h\) is a constant. The univariate case (\(d=1\)) is well known to give rational generating functions. The multivariate case has richer variety as is shown here by a number of examples including lattice paths, knight's walks and Young tableaux of bounded height. The main tool employed is a variant of the kernel method. On the theoretical side, an existence and uniqueness result for a solution to the general recurrence is obtained. The key property required is that the convex hull of the set \(H\) should not meet the first orthant.