Examples of multivariate linear recurrences with constant coefficients

Marko Petkovsek, Aug. 22, 1999

\(<< c:\marko\math\multivar.m\)

Inappropriate data

DiscreteInitialValueProblem[
      a[i, k] == a[i + 2, k - 1] + a[i - 1, k + 2], init, s]

DiscreteInitialValueProblem[
      a[i, k] == a[i - 2, k + 1] + a[i + 1, k - 2], init, s]

Binomial coefficients

DiscreteInitialValueProblem[
        a[n, k] == a[n - 1, k - 1] + a[n - 1, k], {a[n, 0] == 1, 
          a[0, k] == If[k == 0, 1, 0]}, {1, 1}] /. {x[1] -> x, x[2] -> y}

Series[%, {x, 0, 6}, {y, 0, 6}]

Reverse[CoefficientList[%, {y, x}]] // TableForm

SeriesTerm[SeriesTerm[%%%, {x, 0, n}], {y, 0, k}]

The chess king

DiscreteInitialValueProblem[
        a[n, k] == a[n - 1, k - 1] + a[n - 1, k] + a[n, k - 1], {
          a[n, 0] == 1, a[0, k] == 1}, {1, 1}] /. {x[1] -> x, x[2] -> y}

Series[%, {x, 0, 6}, {y, 0, 6}]

Reverse[CoefficientList[%, {y, x}]] // TableForm

SeriesTerm[SeriesTerm[%%%, {x, 0, n}], {y, 0, k}]

Dyck paths

DiscreteInitialValueProblem[
        a[i, k] == a[i - 1, k - 1] + a[i - 1, k + 1], {
          a[0, k] == If[k == 0, 1, 0], a[i, 0] == If[i == 0, 1, 0]}, {1, 
          1}] /. {x[1] -> x, x[2] -> y}

Series[%, {x, 0, 11}, {y, 0, 11}]

Reverse[CoefficientList[%, {y, x}]] // TableForm

Limit[(%%% - 1)/(x y), y -> 0] // Simplify

SeriesTerm[%, {x, 0, n}]

Table[%, {n, 0, 10}]

Table[Binomial[2  n, n]/(n + 1), {n, 0, 5}]

Motzkin paths

DiscreteInitialValueProblem[
        a[i, k] == a[i - 1, k - 1] + a[i - 1, k + 1] + a[i - 1, k], {
          a[0, k] == If[k == 0, 1, 0], a[i, 0] == If[i == 0, 1, 0]}, {1, 
          1}] /. {x[1] -> x, x[2] -> y}

Series[%, {x, 0, 9}, {y, 0, 9}]

Reverse[CoefficientList[%, {y, x}]] // TableForm

Limit[(%%% - 1)/(x y), y -> 0] // Simplify

SeriesTerm[%, {x, 0, n}]

Table[%, {n, 0, 8}]

Schroeder paths

DiscreteInitialValueProblem[
        a[i, k] == a[i - 1, k - 1] + a[i - 1, k + 1] + a[i - 2, k], {
          a[0, k] == If[k == 1, 1, 0], a[1, k] == 0, a[i, 0] == 0}, {2, 
          1}] /. {x[1] -> x, x[2] -> y}

Series[%, {x, 0, 9}, {y, 0, 9}]

Reverse[CoefficientList[%, {y, x}]] // TableForm

Limit[(%%% - y)/(x^2 y), y -> 0] // Simplify

SeriesTerm[%, {x, 0, n}]

%% /. x -> Sqrt[x]

SeriesTerm[%, {x, 0, n}]

Table[%, {n, 0, 5}]