4
$\begingroup$

Let $a(n)$ be a sequence of rational numbers with generating function $F(x)$.

Assume $F(x)$ is composition of rational functions and radicals (roots).

Is the following conjecture true:

Conjecture 1: $a(n)=G(a(n-1),a(n-2),...,a(n-d_1))/H(a(n-1),...,a(n-d_2))$ for polynomials $G$,$H$ with rational coefficients .

Let $F(x)=\frac{1}{{(1+x)}^{\frac12}}$.

$a(n)$ starts $-1/2, 3/8, -5/16, 35/128, -63/256$

Q2 Do we have $a(n)=\frac{(-a(n-2)a(n-1) - \frac12 a(n-1)^2)}{(\frac32 a(n-2) + a(n-1))}$ for all $n$?

According to our tests with sage and pari/gp, not all $F(x)$ result in rational $a(n)$.

sage code is available online.

Wolfram Alpha gives closed form recurrence with polynomial coefficients and algebraic initial values for series 1/(1+x+x^2)^(1/3)here

series 1/(1+x+x^2)^(1/4)here

Improve this question
$\endgroup$
7
  • $\begingroup$ In your example, there is a simple expression for $a(n)$ in terms of binomial coefficients. How hard can it be to answer Q2? $\endgroup$
    – Gerry Myerson
    Commented Aug 16 at 10:09
  • $\begingroup$ I guess $F(x)=\sqrt{x+2}$ would be an example where the coefficients involve $\sqrt2$ and are not rational. math.stackexchange.com/questions/286718/… $\endgroup$
    – Gerry Myerson
    Commented Aug 16 at 10:22
  • $\begingroup$ @GerryMyerson For $F(x)=\sqrt{x+2}$ the sequence $a(n)$ is not rational. This case is described in the original question and it asks for cases when $a(n)$ is rational. $\endgroup$
    – joro
    Commented Aug 16 at 10:57
  • $\begingroup$ All I see in the original question is "According to our tests ... not all $F(x)$ result in rational $a(n)$." So, I thought some user might like to see an explicit example, to supplement your unsupported assertion. $\endgroup$
    – Gerry Myerson
    Commented Aug 16 at 12:03
  • 1
    $\begingroup$ I can read, joro, and I still don't see where you gave any example where the $a(n)$ are not rational, and I still think that my comment had value in giving an explicit example where you failed to do so. $\endgroup$
    – Gerry Myerson
    Commented Aug 16 at 22:07

2 Answers 2

Reset to default
8
$\begingroup$

A composition $F(x)=\sum a(n)x^n\in\mathbb{Q}[[x]]$ of rational functions with radicals is algebraic. The coefficients $a(n)$ of an algebraic power series are P-recursive, meaning that there are polynomials $P_0(n),\dots, P_d(n)$ for which $$ P_d(n)a(n+d)+P_{d-1}(n)a(n+d-1)+\cdots+P_0(n)a(n) =0,\ \ n\geq 0. $$ Since $a(n)\in\mathbb{Q}$ we also have $P_i(n)\in\mathbb{Q}[n]$. References include my paper here (Theorem 2.1) and the book D-Finite Functions by Manuel Kauers. (Kauers uses the term "D-finite" rather than "P-recursive.")

Addendum. As pointed out by joro, my answer above did not answer the question. Here is another attempt. From my answer above, there are polynomials $P_i(n)$ for which $$ Q(n):=P_d(n)a(n+d)+P_{d-1}(n)a(n+d-1)+\cdots+P_0(n)a(n) =0. $$ Substituting $n+1$ for $n$, we get $$ R(n):= P_d(n+1)a(n+d+1)+P_{d-1}(n+1)a(n+d)+\cdots+P_0(n+1)a(n+1)=0. $$ Regard $Q(n)$ and $R(n)$ as polynomials in $n$ whose coefficients are polynomials (or even linear forms) in the $P_i(n+k)$'s. Then the equation $$ \mathrm{Resultant}(Q(n),R(n))=0 $$ gives the desired equation with constant coefficients. The only snag is that the resultant might be 0. I believe this can be avoided by taking $d$ minimal. This argument is completely analogous to the solution to Exercise 6.63(d) in Enumerative Combinatorics, vol. 2,second edition.

Example. Let $a(n)=n!$, $A=f(n)$, $B=f(n+1)$, $C=f(n+2)$, $Q(n)=B-(n+1)A$, $R(n)=C-(n+2)B$. Then $$ \mathrm{Resultant}(Q(n),R(n))=AB-AC+B^2, $$ so $n!(n+1)!-n!(n+2)!+(n+1)!^2=0$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Many thanks. The weak conjecture from the following question would eliminate $n$: mathoverflow.net/questions/476226/… $\endgroup$
    – joro
    Commented Aug 16 at 16:16
  • $\begingroup$ @joro: what do you mean by "eliminate $n$"? $\endgroup$
    – Richard Stanley
    Commented Aug 16 at 19:02
  • 2
    $\begingroup$ I mean: the linked question conjectures that if integer sequence $f(n)$ satisfy recurrence with polynomial in $n$ coefficients, then it satisfies $f(n)=G(f(n-1),f(n-2),...,f(n-d_1)/H(f(n-1),...,f(n-d_2))$ for polynomials with integer coefficients $G,H$. $\endgroup$
    – joro
    Commented Aug 17 at 6:42
  • 2
    $\begingroup$ This is a very interesting result, but it doesn't answer the question, since the question asks about constant coefficients. $\endgroup$
    – joro
    Commented Aug 17 at 6:44
  • $\begingroup$ I think your current resultant claim is incomplete. In addition to non-zero resultant, you need it linear in the leading variable, so you can express it as $G/H$. The paper in the linked question calls this linearity "luck". Counterexample to your current revision is resultant of the form $A^2+B^2-C^2$. $\endgroup$
    – joro
    Commented Aug 18 at 8:46
5
$\begingroup$

To answer Q2, it's enough to note that $a(n)=\frac{1-2n}{2n}a(n-1)$, implying that $$\frac{(-a(n-2)a(n-1) - \frac12 a(n-1)^2)}{(\frac32 a(n-2) + a(n-1))}=\frac{(-1-\tfrac{3-2n}{4(n-1)})a(n-2)a(n-1)}{(\tfrac32 +\tfrac{3-2n}{2(n-1)})a(n-2)}=\frac{1-2n}{2n}a(n-1)=a(n).$$

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks. Do you have intuition about the general case? Wolfram Alpha gives partial results $\endgroup$
    – joro
    Commented Aug 16 at 12:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .