# Generating function for recurrence in two variables

Given characteristic polynomial for the recurrence in two variables (say $F(x,y)$) $$(y^2-1)^x$$ and initial values can generating function for $F(x,y)$ be derived? I know how to do it for a recurrence with one variable but have no idea how to do it in the case of two variables.

PS. The recurrence itself is unknown. Only characteristic polynomial and initial values are given.

EDIT. I can be wrong with the meaning of "characteristic polynomial" for a recurrence with two variables. The idea is that I've got a set of linear recurrences $F(x, y)$ with one variables each of which has the following characteristic polynomial: $F(1,y) = y^2 - 1, F(2,y) = (y^2 - 1)^2, F(3,y) = (y^2 - 1)^3, ...$ So I just generalized it by $F(x,y) = (y^2 - 1)^x$

• How do you define the characteristic polynomial?
– user207868
Apr 20, 2015 at 12:33
• by Berlekamp-Massey algorithm. Apr 20, 2015 at 12:49

We want $F(z,w)$ a generating function such that $$F(z,w) = \sum_{x=0}^{\infty} \sum_{y=0}^{\infty} (y^2-1)^x z^xw^y \tag{1}$$ $(y^2-1)^x z^x$ is a power series.

$$F(z,w) = \sum_{y=0}^{\infty} \frac{w^y}{1 - (y^2-1)z} \tag{2}$$

$$F(z,w) = -\frac1{z} \sum_{y=0}^{\infty} \frac{w^y}{y^2 - 1 - \frac1{z}} \tag{3}$$

$$F(z,w) = -\frac1{z} \sum_{y=0}^{\infty} \frac{w^y}{\left(y - \sqrt{1 + \frac1{z}}\right)\left(y + \sqrt{1 + \frac1{z}}\right)} \tag{4}$$

$$F(z,w) = \frac1{2z\sqrt{1 + \frac1{z}}} \left[ \sum_{y=0}^{\infty} \frac{w^y}{y + \sqrt{1 + \frac1{z}}} - \sum_{y=0}^{\infty} \frac{w^y}{y - \sqrt{1 + \frac1{z}}} \right] \tag{5}$$

Now we need a generating function such that

$$G(w) = \sum_{y=0}^{\infty} \frac{w^y}{y + c} \tag{6}$$

$$\sum_{y=0}^{\infty} w^y = \frac1{1-w} \tag{7}$$

$$w^{c-1}\sum_{y=0}^{\infty} w^y = \sum_{y=0}^{\infty} w^{y+c-1} = \frac{w^{c-1}}{1-w} \tag{8}$$

$$\int\sum_{y=0}^{\infty} w^{y+c-1} dw = \sum_{y=0}^{\infty} \frac{w^{y+c}}{y+c} = \int \frac{w^{c-1}}{1-w} dw \tag{9}$$

$$w^{-c}\sum_{y=0}^{\infty} \frac{w^{y+c}}{y+c} = \sum_{y=0}^{\infty} \frac{w^{y}}{y+c} = w^{-c}\int \frac{w^{c-1}}{1-w} dw \tag{10}$$

From wolfram +c and wolfram -c

$$\int \frac{w^{c-1}}{1-w} dw = \frac{w^c (c w \, _{2}F_{1}(1, c+1, c+2, w)+c+1)}{c (c+1)}+constant \tag{11}$$

Where $_{2}F_{1}$ is a hypergeometric function.

$$F(z,w) = \frac1{2\,z\,c} \left[ \frac{c w \, _{2}F_{1}(1, c+1, c+2, w)+c+1}{c (c+1)} + \frac{c w \, _{2}F_{1}(1, -c+1, -c+2, w)+c-1}{c (c-1)}\right] \tag{12}$$

Where $c = \sqrt{1 + \frac1{z}}$

Sanity check wolfram