A239605 First column of A316273. Recurrence similar to series reversion giving Catalan numbers.

1, 1, 2, 4, 10, 24, 66, 178, 508, 1464, 4320, 12886, 38992, 119030, 366740, 1138036, 3554962, 11167292, 35259290, 111825840, 356100044, 1138107490, 3649507278, 11738028470, 37857909164, 122411024822

Offset: 1

Author

Mats Granvik, Mar 22 2014

Keywords

• nonn

Comments

Setting second term in coefficients equal to -1 gives alternating powers of 2.

The algorithm is as follows:

Step 1. Start with a lower triangular matrix "T" with the first column equal to any number sequence. Let the columns from the second column onwards in "T" be defined by the divisor recurrence: If n >= k: Sum_{i=1..k-1} T(n-i, k-1) - T(n-i, k), otherwise T(n, k) = 0.

Step 2. Downshift matrix "T" one step to get matrix "X".

Step 3. Calculate matrix powers X^0, X^1, X^2, X^3, X^4, X^5, ... and multiply by coefficient list c0, c1, c2, c3, c4, c5, ... to get matrix "B": B = c0*X^0 + c1*X^1 + c2*X^2 + c3*X^3 + c4*X^4 + c5*X^5 + ...

Step 4. Take first column in matrix "B" and put it into the first column of a matrix "T".

Repeat steps 1 to 4 until first column in matrix "T" has converged. This sequence a(n) is the converged first column in matrix "T", when coefficients c0, c1, c2, c3, c4, c5, ... = 1,1,1,1,1,1,...

From Mats Granvik, Jul 25 2014: (Start)

In the program, changing the line

If[n >= k, Sum[t[n - i, k - 1], {i, 1, k - 1}] - Sum[t[n - i, k], {i, 1, k - 1}], 0];

to

If[n >= k, Sum[t[n - i, k - 1], {i, 1, n - 1}] - Sum[t[n - i, k], {i, 1, n - 1}], 0];

that is, summing to (n-1) instead of (k-1), gives Catalan numbers A000108 and series reversion of x/Sum[x^n, {n, 0, nn}]. (End)

From Mats Granvik, Dec 30 2017, Feb 01 2018: (Start)

Let x be an arbitrary real or complex number and let "coeff" in the Mathematica program be the coefficients of the series expansion of the expression:

1/(1 + x*y) + (2*x*y)/(1 + x*y) - (x*y^2)/(1 + x*y) + (x^2*y^2)/(1 + x*y) at y=0

and the output will be the series expansion of (1 + y)/(1 + (1 - x) y) at y=0.

This is equivalent to setting the coefficients "coeff" in the Mathematica program equal to:

coeff = Join[{1, x}, (-Sign[x]*Abs[x])^Range[10]]

which gives an output "cc" that is:

Join[{1}, x*(x - 1)^Range[0, Length[coeff] - 2]]

for all values of "x" (with the special case 0^0=1 for x=1).

(End)

Crossrefs

Cf. A051731, A000079.

Programs

Mathematica

Clear[t, n, k, i, nn, x];
coeff = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
mp[m_, e_] :=
If[e == 0, IdentityMatrix@Length@m, MatrixPower[m, e]]; nn =
Length[coeff]; cc = Range[nn]*0 + 1; Monitor[
Do[Clear[t]; t[n_, 1] := t[n, 1] = cc[[n]];
  t[n_, k_] :=
   t[n, k] =
    If[n >= k,
     Sum[t[n - i, k - 1], {i, 1, k - 1}] -
      Sum[t[n - i, k], {i, 1, k - 1}], 0];
  A4 = Table[Table[t[n, k], {k, 1, nn}], {n, 1, nn}];
  A5 = A4[[1 ;; nn - 1]]; A5 = Prepend[A5, ConstantArray[0, nn]];
  cc = Total[
    Table[coeff[[n]]*mp[A5, n - 1][[All, 1]], {n, 1, nn}]];, {i, 1,
   nn}], i]; cc
(* Mats Granvik, Aug 26 2015 *)