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.

  • 3
    $\begingroup$ 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. $\endgroup$ Jun 15 at 20:24
  • 2
    $\begingroup$ ... 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 $$ $\endgroup$ Jun 16 at 5:02
  • $\begingroup$ math.stackexchange.com/questions/4173685/… $\endgroup$ Jun 16 at 6:27
  • $\begingroup$ @Fedor Petrov Why do you know a priori that the order of the differential equation is 4. $\endgroup$ Jun 17 at 18:28
  • 2
    $\begingroup$ Sorry, of order 2, I misread the question. That's because the degrees of polynomials do not exceed 2 $\endgroup$ Jun 17 at 18:49

Extended comment.

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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.