0
$\begingroup$

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.

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

1 Answer 1

0
+50
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ what is $n$ in the example? Can you please give an example of expansion, for example, $A(6,2)$? $\endgroup$
    – user144765
    Apr 2, 2015 at 6:50
  • $\begingroup$ Sorry, I messed up $m$ and $n$ in my answer. I have corrected them. $\endgroup$
    – Zilin J.
    Apr 4, 2015 at 17:05

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.