Recurrence involving a product of recurrents

Question

I can solve the following recurrence problem as follows:

 ClearAll[a, b];
 a[1] := 2;
 a[2] := a[1] + b;
 b = 2;
 a[n_] := Product[a[i], {i, 1, n - 1}] + b
 list = Table[a[i], {i, 1, 5}]

which gives: {2, 4, 10, 82, 6562}. But, when I try:

 f = FindSequenceFunction[list]

I get: "FindSequenceFunction[{2, 4, 10, 82, 6562}]"; when I'm expecting instead the function: 3^2^n + 1, given that:

 Table[3^2^n + 1, {n, 0, 3}]

gives: {4, 10, 82, 6562}. Frustrated; I tried other approaches that didn't work neither. For instance:

(1.) Recurrence table approach:

 ClearAll[a, b];
 With[{b = 2},
 RecurrenceTable[{a[n] == Product[a[i], {i, 1, n - 1}] + b, a[1] == 2,
 a[2] == a[1] + b}, a, {n, 1, 5}]]

(2.) RSolve approach:

 ClearAll[a, b];
 With[{b = 2}, 
 RSolve[{a[n] == Product[a[i], {i, 1, n - 1}] + b, a[1] == 2, 
   a[2] == a[1] + b}, a[n], n]]

(3.) Module approach:

 ClearAll[a, b];
 prod[n_] := Module[{a},
  a[1] := 2; b := 2; a[2] := a[1] + b; k := (n - 1);
  a[i_] := Product[a[j], {j, 1, k}] + b;
  a[n]
  ]

When I evaluate:

 prod[1]

I get 2. Similarly prod[2] gives 4 and prod[3] gives 10. But, when I try:

 prod[4]

I get the message: "$RecursionLimit::Recursion depth of 1024 exceeded during evaluation of …"

I would appreciate any help with the above three approaches. Thank you!

Answer 1

All computer algebra systems, including Mathematica, are limited in their capabilities. Your $3^{2^n} + 1$ function grows very quickly and the built-in algorithms in Mathematica FindSequenceFunction[] are not currently capable of recognizing it solely from its first few values. In some future version, it may become possible.

In the case of RecurrenceTable[] the error message clearly states you have given it a recurrence that it is not currently able to deal with. Same thing with Rsolve[]. However, it is possible to define it using standard recursion. Try the following code

ClearAll[a, b]; b = 2; a[1] = 2; 
a[i_] := Product[a[j], {j, i - 1}] + b;
Array[a, 5]

which returns {2, 4, 10, 82, 6562}.