RecurrenceTable is not honoring FullSimplify

Question

I define a function nextK and compute the first three terms in a recurrence as follows:

nextK[k3_] := Expand[FullSimplify[3 + k3 + 2 Sqrt[2 + 3 k3]]]
G[y_] := nextK[G[y - 1]]
G[1] := 3
Table[G[i], {i, 3}]

with the output

However if I use RecurrenceTable

RecurrenceTable[
  {a[n + 1] == nextK[a[n]], a[1] == 3},
  a, {n, 1, 3}
]

I get the following:

Note that the third element has not been simplified. It should be the same as the third element of the previous computation. It's as if the FullSimplify in the definition of nextK has not been honored. What am I doing wrong?

(Update) Clearly, FullSimplify could be run once the table is complete, but for non-trivial tables (say 10 or 20 elements rather than just 3), the pre-simplification expressions can be huge.

Answer 1

I see the same behavior in the latest version

$Version

(* "12.2.0 for Mac OS X x86 (64-bit) (December 12, 2020)" *)

Clear["Global`*"]

nextK[k3_] := FullSimplify[3 + k3 + 2 Sqrt[2 + 3 k3]];

Add memorization to the definition of G

G[y_] := G[y] = nextK[G[y - 1]];
G[1] := 3
Table[G[i], {i, 3}]

(* {3, 2 (3 + Sqrt[11]), 15 + 4 Sqrt[11]} *)

The RecurrenceTable results have not been simplified. Presumably, nextK is first evaluated symbolically where the simplification does not change the form. Subsequent numeric values do not then have the simplification applied.

seq = RecurrenceTable[{a[n + 1] == nextK[a[n]], a[1] == 3}, a, {n, 1, 5}]

(* {3, 6 + 2 Sqrt[11], 9 + 2 Sqrt[11] + 2 Sqrt[2 + 3 (6 + 2 Sqrt[11])], 
 12 + 2 Sqrt[11] + 2 Sqrt[2 + 3 (6 + 2 Sqrt[11])] + 
  2 Sqrt[2 + 3 (9 + 2 Sqrt[11] + 2 Sqrt[2 + 3 (6 + 2 Sqrt[11])])], 
 15 + 2 Sqrt[11] + 2 Sqrt[2 + 3 (6 + 2 Sqrt[11])] + 
  2 Sqrt[2 + 3 (9 + 2 Sqrt[11] + 2 Sqrt[2 + 3 (6 + 2 Sqrt[11])])] + 
  2 \[Sqrt](2 + 
      3 (12 + 2 Sqrt[11] + 2 Sqrt[2 + 3 (6 + 2 Sqrt[11])] + 
         2 Sqrt[2 + 3 (9 + 2 Sqrt[11] + 2 Sqrt[2 + 3 (6 + 2 Sqrt[11])])]))} *)

seq = seq // FullSimplify

(* {3, 2 (3 + Sqrt[11]), 15 + 4 Sqrt[11], 6 (5 + Sqrt[11]), 51 + 8 Sqrt[11]} *)

Note that FindSequenceFunction can be used to generalize from the sequence provided by RecurrenceTable

f[n_] = FindSequenceFunction[seq, n] // FullSimplify

(* 6 - 2 Sqrt[11] + n (-6 + 2 Sqrt[11] + 3 n) *)

Verifying that this result is equivalent to G

And @@ Table[G[n] == f[n], {n, 50}]

(* True *)

However, the results of f must also be subsequently simplified to obtain the same form as G

f /@ Range[3]

(* {3, 6 + 2 Sqrt[11], 6 - 2 Sqrt[11] + 3 (3 + 2 Sqrt[11])} *)

% // FullSimplify

(* {3, 2 (3 + Sqrt[11]), 15 + 4 Sqrt[11]} *)

Answer 2

For my purposes I should have been using something like NestList.

NestList[nextK, 3, 5] 

gives exactly what is expected.

When using RecurrenceTable I did not appreciate that it is a solver, rather than an iterator. The use of == as opposed to = should have tipped me off.

As a solver, RecurrenceTable needs to set up a well defined set of recurrence definitions. In my case, it executes nextK symbolically to get nextK[a[n]]3 + a[n] + 2 Sqrt[2 + 3 a[n]]. Expand and FullSimplify have been applied, but in the symbolic case they have no effect (unlike in the numeric case using exact expressions).

A simpler example gives confirmation. We define a new function nextL that adds a random integer:

nextL[x_] :=x + RandomInteger[{1,20}]

Then

seq=RecurrenceTable[{a[n + 1] == nextL[a[n]], a[1] ==x}, a, {n, 1,5}]
(* {x,16+x,32+x,48+x,64+x} *)

Differences[seq]
(* {16,16,16,16} *)  

shows that nextL is only called once, whereas in

seq2=NestList[nextL,x,4]
(* {x,15+x,27+x,31+x,48+x} *)

Differences[seq2]
(* {15,12,4,17} *)

nextL is called for each iteration.