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

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 ?

• Please next time format your code properly – Feyre Feb 4 '17 at 10:12
• A sixth order polynomial always requires at least 7 to determine. Just like a zeroth order requires at least one point. Perhaps you're looking for Expand@InterpolatingPolynomial[seq2, x]? – Feyre Feb 4 '17 at 10:17
• Above (6, 7) versus (7,8) in the previous version : of course this was a careless slip. Sorry. Back to your answer : yes indeed, InterpolatingPolynomial does the job. Thank you. I was wondering why FindSequenceFunction had to use more terms than what seems necessary : I had missed the existence of the option ValidationLength (next answer). – Ishakuduruk Feb 4 '17 at 18:40

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  *)