# Two questions: Recurrence and Matrices

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 := {1};
a := {2*a, 3*a};
a[n_] := Flatten[{{4*a[n - 2][], 6*a[n - 2], 9*a[n - 2][[-1]]}}]


Edit corrected the row skipping.

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

• You can use NestList[], of course: NestList[{#[], Flatten[{4 #[[1, 1]], 6 #[], 9 #[[1, -1]]}]} &, {{1}, {2, 3}}, 5]. – J. M.'s discontentment Mar 29 '17 at 12:47
• Appears to be the same as b[n_, j_] := 2^(n - j)*3^j so could do e.g. Table[b[n, j], {n, 0, 10}, {j, 0, n}]. – Daniel Lichtblau Mar 29 '17 at 15:11

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

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


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

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" ;)

## 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 = {#[], Join[2 #[[2, {1}]], 6 #[], 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 = {#[], Flatten[{4 #[[1, 1]], 6 #[], 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}

• LinearRecurrence is exactly what I had in mind. Thanks. – Fred Kline Mar 29 '17 at 23:18