Two questions: Recurrence and Matrices

Question

We have a recurrence which produces a triangle's row and would like to find an efficient way to produce all rows up to that limit. In addition: Is there a way to do this using matrices? Where we would define a seed number and the same rules to get a triangle?

Clear[a, n];
a[0] := {1};
a[1] := {2*a[0], 3*a[0]};
a[n_] := Flatten[{{4*a[n - 2][[1]], 6*a[n - 2], 9*a[n - 2][[-1]]}}]

Edit corrected the row skipping.

a[-1] = {};
a[0] = {1};
a[n_] := a[n] = Flatten[{{2*a[n - 1][[1]], 6*a[n - 2], 3*a[n - 1][[-1]]}}]

Answer 1

Don't use SetDelayed for the starting conditions, and use memoization for the general rule:

Clear[a, n];
a[0] = {1};
a[1] = {2*a[0], 3*a[0]};
a[n_] := a[n] = Flatten[{4*a[n - 2][[1]], 6*a[n - 2], 9*a[n - 2][[-1]]}]

If you now do a[10]; then all the even n < 10 will be stored inside a[2], a[4],....

Putting the result in a matrix would be something like:

Clear[mat];
mat[n_] := Block[{ans}, ans = ConstantArray[0, {n, n}];
  ans[[1, 1]] = 1;
  ans[[2, 1]] = 2*ans[[1, 1]];
  ans[[2, 2]] = 3*ans[[1, 1]];
  Do[ans[[row, 1]] = 4*ans[[row - 2, 1]];
   ans[[row, row]] = 9*ans[[row - 2, row - 2]];
   Do[ans[[row, col]] = 6*ans[[row - 2, col - 1]], {col, 2, 
     row - 1}], {row, 3, n}];
  ans]

If this is what you mean by "do[ing] this using matrices" ;)

Answer 2

LinearRecurrence

A bit of experimentation shows this nice equivalence with LinearRecurrence which may touch on your matrix quest in some way.

a2[n_] := LinearRecurrence[{3/2}, {2^(n - 1)}, n]

Array[a2, 5]

{{1}, {2, 3}, {4, 6, 9}, {8, 12, 18, 27}, {16, 24, 36, 54, 81}}

NestList

As J. M. proposed you could use NestList, and I would use Join instead of Flatten as should your recursion allow packed arrays it will preserve packing.

f = {#[[2]], Join[2 #[[2, {1}]], 6 #[[1]], 3 #[[2, {-1}]]]} &;

NestList[f, {{}, {1}}, 4][[All, 2]]

{{1}, {2, 3}, {4, 6, 9}, {8, 12, 18, 27}, {16, 24, 36, 54, 81}}

Creating a case to illustrate the point about Join:

f2 = {#[[2]], Flatten[{4 #[[1, 1]], 6 #[[1]], 9 #[[1, -1]]}]} &;

test[fn_] :=
  NestList[fn, N @ {Range@1, Range[2, 3]}, 640][[All, 1]] // Length // RepeatedTiming

test /@ {f, f2}   // Column

{0.0041, 641}

{0.018, 641}