# Derive a 2D recurrence from a set of linear recurrences

Given a set of high-order linear recurrences:

$A(1, n): 0, 1, 0, 1, 0, ...$

$A(2, n): a_{n} = 2a_{n-2} - a_{n-4}$

$A(3, n): b_{n} = 3b_{n-2} - 3b_{n-4} + b_{n-6}$

$A(4, n): c_{n} = 4c_{n-2} - 6c_{n-4} + 4c_{a-6} - c_{n-8}$

ans so on.

I want to derive 2D recurrence for $A(m, n)$. Obviously, each of linear recurrences has a characteristic polynomial $(x^2 - 1)^m$ (due to coefficients representing terms of row $m$ of Pascal's triangle). Moreover, each of that recurrences has more or less "nice" explicit formula. So:

1. Is it possible to derive 2D recurrence?
2. If not, is it possible to derive general explicit formula for that recurrences?

EDIT: Initial values (offset starts from $1$) are:

$A(2, n): 0,3,0,7$

$A(3, n): 0,6,3,31,10,76$

$A(4, n): 0,10,21,117,122,448,367,1131$

$A(5, n): 0,16,89,439,906,2630,3907,9037,11380,23196$

The main problem is that I don't know which initial values would be for $A(m, n)$. So I need a way to generalize it.

• for someone like me can you explain :what do you mean by $D$ recurrence? Mar 29, 2015 at 0:01
• I meant the recurrence in two variables. Mar 29, 2015 at 0:21
• How did you choose those initial values? Do they satisfy any nice recurrence formula? Mar 30, 2015 at 19:46
• I couldn't find any recurrences for initial values. Mar 30, 2015 at 20:28
• Where do the sequences come from? Mar 31, 2015 at 11:24

The ordinary generating function (OGF for short) of $A(m,n)$, for fixed $m$, is $$F_m(x):=\frac{P_m(x)}{(x^2-1)^m},$$ where $P_m(x)$ is a polynomial of degree $\leq m$.
Since you are interested in $2D$ recursion of $A(m, n)$, we also want to consider the OGF of $A(m+1, n)$, that is $$F_{m+1}(x) := \frac{P_{m+1}(x)}{(x^2-1)^{m+1}}.$$
We obtain $$F_{m+1}(x) = \frac{P_{m+1}(x)F_m(x)}{P_m(x)(x^2-1)}.$$
Suppose $Q(x) = \frac{P_{m+1}(x)}{P_m(x)(x^2-1)} = q_0 + q_1x + q_2x^2 + \dots$. Then $$A(m+1, n) = [x^n]F_{m+1}(x) = [x^n]Q(x)F_m(x) = q_0A(m,n)+q_1A(m,n-1) + \dots + q_nA(m,0).$$
Example: The OGF of $A(1,n): 0, 1, \dots$ is $\frac{x}{1-x^2}$ and the OGF of $A(2,n): 0,3,0,7,\dots$ is $\frac{3x+x^3}{(1-x^2)^2}$. Then $Q(x)=\frac{3+x^2}{1-x^2}=3+4x^2+4x^4+4x^6+\dots$ and so $$A(2,n) = 3A(1,n) + 4A(1,n-2) + 4A(1,n-4) + 4A(1,n-6) + \dots,$$ and so $A(2,6)=3A(1,6)+4A(1,4)+4A(1,2)+4A(1,0) = 0$ as $A(1,0)=A(1,2)=A(1,4)=A(1,6)=0$.
• what is $n$ in the example? Can you please give an example of expansion, for example, $A(6,2)$? Apr 2, 2015 at 6:50
• Sorry, I messed up $m$ and $n$ in my answer. I have corrected them. Apr 4, 2015 at 17:05