# Prepending a sequence with zeros gives FindGeneratingFunction hard time

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}]][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??

• (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? – Mr.Wizard Feb 26 '16 at 20:53
• @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... – მამუკა ჯიბლაძე Feb 26 '16 at 20:55
• Would it be a solution to programmatically strip zeros, or possibly repeated elements of any kind, appearing at the start of your list? – Mr.Wizard Feb 26 '16 at 20:57
• @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. – J. M. is in limbo Feb 26 '16 at 22:01
• @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? – Mr.Wizard Feb 26 '16 at 22:10