# How to probe the recursiveness order of a sequence $\{S_n\}$ whose generating function is known

How to probe the recursiveness order of a sequence $$\{S_n\}$$ whose generating function is known:

$$\sum_{n\geq0} S_n z^n= \frac{4 z \left(\sqrt{49 z^2-18 z+1}+7 z-1\right)}{\sqrt{49 z^2-18 z+1} \left(\sqrt{49 z^2-18 z+1}+15 z-1\right) \left(3 \sqrt{49 z^2-18 z+1}+21 z-1\right)}+\frac{3}{3-44 z}$$

And even more, as the following is proven.

$$\textbf{Conjecture}$$ : $$\{S_n\}$$ satisfy the following recurrence

$$0= P_0(n) S_n+ P_1(n) S_{n-1}+ P_2(n) S_{n-2}+ P_3(n) S_{n-3}+ P_4(n) S_{n-4}$$

where $$P_i(n) \in \mathbb{R}[n]$$ are polynomials of degree 2.

• It is a differential equation for the function (of order 4, with corresponding polynomial coefficients). You may check whether it is satisfied by direct differentiating. Jun 15 at 20:24
• ... and in this case, unless I'm mistaken, the recurrence is $$\left(12 n^{2}-1581 n +1569\right) S_{n}+\left(-572 n^{2}+75469 n -111467\right) S_{n -1}+\left(9636 n^{2}-1273335 n +2500019\right) S_{n -2}+\left(-64964 n^{2}+8600211 n -21072477\right) S_{n -3}+\left(129360 n^{2}-17172540 n +50353380\right) S_{n -4} = 0$$ Jun 16 at 5:02
• math.stackexchange.com/questions/4173685/… Jun 16 at 6:27
• @Fedor Petrov Why do you know a priori that the order of the differential equation is 4. Jun 17 at 18:28
• Sorry, of order 2, I misread the question. That's because the degrees of polynomials do not exceed 2 Jun 17 at 18:49

The relation $$0=P_0(n) S_n+ P_1(n) S_{n-1}+ P_2(n) S_{n-2}+ P_3(n) S_{n-3}+ P_4(n) S_{n-4}$$ for all $$n\geqslant 4$$ is equivalent to $$0=\sum_{n\geqslant 4} (P_0(n) S_n+ P_1(n) S_{n-1}+ P_2(n) S_{n-2}+ P_3(n) S_{n-3}+ P_4(n) S_{n-4})x^n.$$ Denote $$\sum_{n=0}^\infty S_n x^n=f(x)$$. Then $$f'(x)=\sum_{n\geqslant 0} S_n\cdot nx^{n-1}$$, $$f''(x)=\sum_{n\geqslant 0} S_n\cdot n(n-1)x^{n-2}$$. Thus for $$i\in \{0,1,2,3,4\}$$ we have $$\sum_{n\geqslant 4} P_i(n)S_{n-i}x^n= \sum_{n\geqslant i} P_i(n)S_{n-i}x^n-\sum_{n=i}^3P_i(n)S_{n-i}x^i=\\ \sum_{n\geqslant 0} P_i(n+i)S_{n}x^{n+i}-\sum_{n=i}^3P_i(n)S_{n-i}x^i.$$ Denote $$P_i(n+i)=a_i+b_in+c_in(n-1)$$ and $$\sum_{n=i}^3P_i(n)S_{n-i}x^i=g_i(x)$$. Then $$\sum_{n\geqslant 0} P_i(n+i)S_{n}x^{n+i}-\sum_{n=i}^3P_i(n)S_{n-i}x^i=x^i(a_if(x)+b_ixf'(x)+c_ix^2f''(x))-g_i(x).$$ Thus the differential equation for $$f$$ has a form $$q_0(x)f(x)+xq_1(x)f'(x)+x^2q_2(x)f''(x)=A(x)$$ for some polynomials $$q_0,q_1,q_2$$ of degree at most 4 and $$A$$ of degree at most 3.