3
$\begingroup$

Asking for

FindGeneratingFunction[{1, 3, 11, 43, 171, 683, 2731, 10923, 43691, 174763}, t]

gives the answer (namely (1 - 2 t)/(1 - 5 t + 4 t^2)) almost immediately. However if I prepend zeros in the beginning it takes significantly more time:

Timing[FindGeneratingFunction[{0, 0, 0, 0, 0, 1, 3, 11, 43, 171, 683, 2731, 10923, 43691, 174763}, t]]

gives {20.3438, ((1 - 2 t) t^5)/(1 - 5 t + 4 t^2)}, while adding one more zero results in the answer

DifferentialRoot[Function[{\[FormalY],\[FormalX]},{(7-46 \[FormalX]+90 \[FormalX]^2-48 \[FormalX]^3) \[FormalY][\[FormalX]]+(-1+\[FormalX]) \[FormalX] (-1+2 \[FormalX]) (-1+4 \[FormalX]) (\[FormalY]^\[Prime])[\[FormalX]]==0,\[FormalY][0]==0}]][t]/t

I need to add two more terms of the sequence to the right to get ((1 - 2 t) t^6)/(1 - 5 t + 4 t^2).

Can I improve performance by manipulating options to FindGeneratingFunction? There is an option Method but I could not find anything in the documentation about it.

Moreover to

FindGeneratingFunction[{0, 0, 0, 0, 0, 2, 2, 6, 6, 22, 22, 86, 86, 342, 342, 1366, 1366, 5462, 5462}, t]

(multiplying by two and repeating each term twice) gives (2^(1 + t) t^5 (1 - 2 t^2))/(1 - t - 4 t^2 + 4 t^3), and this I don't understand at all - what is 2^(1 + t) doing there??

$\endgroup$
  • $\begingroup$ (1) Please do not use the bugs tag until a behavior is confirmed as a bug. (2) The zeros make this a different sequence; why don't you remove them if you want the first result? $\endgroup$ – Mr.Wizard Feb 26 '16 at 20:53
  • $\begingroup$ @Mr.Wizard Will know, thanks. As for the zeros - well sometimes one wants to blindly feed several sequences into a program without knowing whether they start with several zeros or not... $\endgroup$ – მამუკა ჯიბლაძე Feb 26 '16 at 20:55
  • $\begingroup$ Would it be a solution to programmatically strip zeros, or possibly repeated elements of any kind, appearing at the start of your list? $\endgroup$ – Mr.Wizard Feb 26 '16 at 20:57
  • $\begingroup$ @Mr. Wizard, that could work; it would correspond to needing to multiply the result of the stripped version with an appropriate power, and then adding back an appropriate geometric series. $\endgroup$ – J. M. is away Feb 26 '16 at 22:01
  • $\begingroup$ @J.M. Since FindSequenceFunction[{0, 0, 0, 0, 0, 1, 3, 11, 43, 171, 683, 2731, 10923, 43691, 174763}] is fast is there an easy way to use that output to compute a generating function? $\endgroup$ – Mr.Wizard Feb 26 '16 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.