How many terms does FindSequenceFunction need to discover a simple polynomial rule?

Question

Consider a simple sequence starting with

    seq1 = {429, 1014, 1935, 3264, 5073, 7434, 10419, 14100, 18549, 23838};

We are looking for a rule (of course there are infinitely many) that would be compatible with the above terms. Mathematica finds a simple answer :

FindSequenceFunction[seq1, x] // Expand
(* 108 + 213 x + 96 x^2 + 12 x^3 *)

The result being a cubic polynomial, one could hope that it should be enough to give the first four terms to FindSequenceFunction in order for it to find the (hopefully) same result.

seq2 = {429, 1014, 1935, 3264};

FindSequenceFunction[seq2, x]
(* FindSequenceFunction[{429, 1014, 1935, 3264}, x] *)

But it is not so... Of course you could do it yourself "by hand" (and recover the above result) if you assume that the function to be found is an arbitrary cubic :

Solve[Map[{a0, a1, a2, a3}.{1, #, #^2, #^3} &, {1, 2, 3, 4}] == {429, 1014, 
   1935, 3264}]
(* {{a0 -> 108, a1 -> 213, a2 -> 96, a3 -> 12}} *)

What looks surprising is that, in this particular case, FindSequenceFunction needs five terms (why ?) to get the (same) result.

seq3 = {429, 1014, 1935, 3264, 5073};

FindSequenceFunction[seq3, x] // Expand
(* 108 + 213 x + 96 x^2 + 12 x^3 *)

In the previous examples, we discovered that, in order to get a simple polynomial answer, FindSequenceFunction had to use one more term than what could have been naively expected.

Here is a similar but slightly more involved example:

Consider the sequence starting as follows (I give 7 terms) :

seq4 = {14880, 227880, 1483920, 6176880, 19535040, 51303840, 117826080};

FindSequenceFunction fails to find a rule for it...

FindSequenceFunction[seq4, x]
(* FindSequenceFunction[{14880, 227880, 1483920, 6176880, 19535040, 51303840, 
  117826080}, x] *)

However, I know a priori that my sequence comes from a 6th degree polynomial. So is not difficult, by hand, to find that the following function works :

Table[120 + 794 x + 2413 x^2 + 4215 x^3 + 4355 x^4 + 2431 x^5 + 552 x^6, {x, 
  1, 7}]
(* {14880, 227880, 1483920, 6176880, 19535040, 51303840, 117826080} *)

Here, one could have expected FindSequenceFunction to need 7 terms of the sequence to get the answer, it was not so. It needs 8 terms :

Table[120 + 794 x + 2413 x^2 + 4215 x^3 + 4355 x^4 + 2431 x^5 + 552 x^6, {x, 
  1, 8}]
(* {14880, 227880, 1483920, 6176880, 19535040, 51303840, 117826080, 244519560} *)

FindSequenceFunction[%, x] (* Indeed ! *)
(* 120 + 794 x + 2413 x^2 + 4215 x^3 + 4355 x^4 + 2431 x^5 + 552 x^6 *)

But why to use eight terms ? What is the rationale behind this behavior ?

Answer 1

seq1 = {429, 1014, 1935, 3264, 5073, 7434, 10419, 14100, 18549, 23838};

You can get the expected result with only four terms if you set the ValidationLength to zero

f1[n_] = FindSequenceFunction[seq1[[1 ;; 4]], n,
   ValidationLength -> 0] // Expand

(*  108 + 213 n + 96 n^2 + 12 n^3  *)

f1 /@ Range[Length[seq1]] === seq1

(*  True  *)

Or using the last four terms of seq1

f2[n_] = FindSequenceFunction[seq1[[-4 ;;]], n,
    ValidationLength -> 0] /.
   n :> n - (Length[seq1] - 4) // Expand

(*  108 + 213 n + 96 n^2 + 12 n^3  *)

f2 /@ Range[Length[seq1]] === seq1

(*  True  *)