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$

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

1 Answer 1


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


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.