# monotonicity from 4 term-recursion.

In determining the monotonicity of coefficients in a series expansion (which appeared in one of my study), I come across the following problem.

Let $p\ge 2$ be an integer, and $$6p^3(i+3)d_{i+3}=6p^2(i+2+p)d_{i+2}+3p(p-1)(i+1+2p)d_{i+1}+(p-1)(2p-1)(i+3p)d_i,~~i\ge0$$ with $d_0=d_1=d_2=1$. How to show $d_i>d_{i+1}$ for all $i\ge3$?

By easy calculation, $d_3=1, d_4=\frac{18p^3+11p^2-6p+1}{24p^3}$. For a recursion of 2 or 3 terms, it is easy to proceed with induction, but what about 4 terms in this case?

-
What is the recurrence for the sequence $d_i-d_{i+1}$? Usual problems in such cases refer to positivity of a sequence rather than monotonicity. It is always helpful to have more indices, then the inductive argument might be clearer. There are algorithmic approaches to the positivity questions; check Manuel Kauers's publications at kauers.de. –  Wadim Zudilin Apr 17 '10 at 5:54
The problem cannot be simplified by reducing to judge the positivity of $d_i-d_{i+1}$. –  Sunni Apr 17 '10 at 15:25

I am a little bit upset that my previous answer to the question was downvoted by somebody. As far as I understand the idea of MO is not necessarily to produce final answers/solutions/responses but mostly to provide the ideas of approaching a given problem.

It's a question of time to solve this particular problem (I still wonder about where it comes from). Denote $$F(x)=\sum_{i=0}^\infty d_ix^i=1+x+x^2+x^3+\dots$$ the generating function of the sequence. The given recursion can be then written as the differential equation of order 1, $$\frac{F'}{F}=\frac{3p(2p^2+2p(p-1)x+(p-1)(2p-1)x^2)}{6p^3-6p^2x-3p(p-1)x^2-(p-1)(2p-1)x^3}$$ which can be explicitly solved: $$F(x)=\biggl(1-\frac xp-\frac{(p-1)x^2}{2p^2}-\frac{(p-1)(2p-1)x^3}{6p^3}\biggr)^{-p}$$ (one checks that the expansion indeed starts $1+x+x^2+x^3+\dots$).

The desired property $d_i>d_{i+1}$ for $i\ge3$ is equivalent to showing that the expansion $$1-(1-x)F(x)=c_0x^4+c_1x^5+c_2x^6+\dots$$ has all coefficients $c_0,c_1,c_2,\dots$ positive. In turn, the latter is equivalent to the positivity of all coefficients in the expansion $$\frac{d}{dx}\bigl(1-(1-x)F(x)\bigr)=4c_0x^3+5c_1x^4+6c_2x^5+\dots.$$ We have $$\frac{d}{dx}\bigl(1-(1-x)F(x)\bigr) =\biggl(1-\frac xp-\frac{(p-1)x^2}{2p^2}-\frac{(p-1)(2p-1)x^3}{6p^3}\biggr)^{-p}$$ $$-p(1-x)\biggl(\frac1p+\frac{(p-1)x}p+\frac{(p-1)(2p-1)x^2}{2p^3}\biggr) \cdot\biggl(1-\frac xp-\frac{(p-1)x^2}{2p^2}-\frac{(p-1)(2p-1)x^3}{6p^3}\biggr)^{-p-1}$$ $$=\frac{(p-1)(2p-1)(3p-1)}{6p^3}x^3 \cdot\biggl(1-\frac xp-\frac{(p-1)x^2}{2p^2}-\frac{(p-1)(2p-1)x^3}{6p^3}\biggr)^{-p-1}$$ $$=\frac{(p-1)(2p-1)(3p-1)}{6p^3}x^3 \cdot\Biggl(1+\sum_{n=1}^\infty\frac{(p+1)(p+2)\dots(p+n)}{n!} \biggl(\frac xp+\frac{(p-1)x^2}{2p^2}+\frac{(p-1)(2p-1)x^3}{6p^3}\biggr)^n\Biggr),$$ and the desired positivity follows.

-
@Zudilin:The third solution is also correct, but rather than upvoted, it was downvoted by someone. –  Sunni May 10 '10 at 16:43
I don't say that your solution is not correct. I have troubles following it and, as a comment shows, that's not only me. –  Wadim Zudilin May 10 '10 at 20:22

For $p>1$, the characteristic polynomial of the recurrence, $f(x)=6p^3x^3-6p^2x^2-3p(p-1)x-(p-1)(2p-1)$, has a real zero $x_1$ between $0$ and $1$ (this is easy) and a pair of complex conjugate zeros $x_2$ and $x_3$ whose absolute value is strictly less than $|x_1|$ (this is less trivial). Then a generic solution $d_i$ of the recurrence satisfies $d_{i+1}/d_i\to x_1$ as $i\to\infty$, so it satisfies $d_i>d_{i+1}$ eventually. It is technically possible (by expecting the corresponding DE for the generating series, for example,--but this is in any case worth trying) to show that your solution is generic, that is, $d_i^{1/i}\to x_1$ as $i\to\infty$. Replacing "eventually" by an effective bound (an "effective" version of Poincare's theorem) is usually hard unless the asymptotics can be computed using a different representation of the sequence.

-
I thought you could only use these char poly techniques for linear recurrence relations. There are all these extra terms (i+1+2p) etc that the char poly doesn't see, and surely the answer depends on them? –  Kevin Buzzard Apr 17 '10 at 12:34
@ Zudilin: At a first glance, the hardest step in your argument lies in how to find the 'effective bound'. –  Sunni Apr 17 '10 at 15:32
The proposer has solved the problem. If you are interested, you may ask me for the solution. –  Sunni Apr 18 '10 at 16:48
I am quite interested in the answer. I tried to solve the sequence explicitly using generating function method. I got a first order linear differential equation, but the function involved an integral which can't be evaluated analytically. I think proving monotonicity doesn't require you solving the sequence, but I just think it would be interesting to solve it. Is the answer based on M.I.? –  Ross Tang Apr 19 '10 at 8:36
@miwalin: What is M.I.? Does your solution work for any real $p>1$? –  Wadim Zudilin Apr 23 '10 at 13:58

Simple calculation shows $d_3=1, d_4=\frac{18p^3+11p^2-6p+1}{24p^3}, 30p^3d_5=6p^2(4+p)d_4+(p-1)[3p(3+2p)+(2p-1)(2+3p)]d_3$, and so $d_3>d_4>d_5$.

Assume $d_i>d_{i+1}>d_{i+2}$ and $6p^3(i+2)d_{i+2}\ge 6p^2(i+1+p)d_{i+1}+(p-1)[3p(i+2p)+(2p-1)(i-1+3p)]d_i$ for all $i\ge3$ .

Then $6p^3(i+3)d_{i+3}=6p^2(i+2+p)d_{i+2}+\frac{p-1}{p}[3p^2(i+1+2p)d_{i+1}+(2p-1)(i+3p)pd_i]$< $6p^2(i+2+p)d_{i+2}+\frac{p-1}{p} \{6p^2(i+1+p)d_{i+1}+(p-1)[3p(i+2p)+(2p-1)(i-1+3p)]d_i \}\le$ $6p^2(i+2+p)d_{i+2}+ \frac{p-1}{p} 6p^3(i+2)d_{i+2}=6p^3(i+3)d_{i+2}$, this shows $d_{i+3}< d_{i+2}$.

Moreover, $6p^3(i+3)d_{i+3}=6p^2(i+2+p)d_{i+2}+3p(p-1)(i+1+2p)d_{i+1}+(p-1)(2p-1)(i+3p)d_i>$ $6p^2(i+2+p)d_{i+2}+3p(p-1)(i+1+2p)d_{i+1}+(p-1)(2p-1)(i+3p)d_{i+1}=$ $6p^2(i+2+p)d_{i+2}+(p-1)[3p(i+1+2p)+(2p-1)(i+3p)]d_{i+1}$. This shows $6p^3(i+3)d_{i+3}\ge 6p^2(i+2+p)d_{i+2}+(p-1)[3p(i+1+2p)+(2p-1)(i+3p)]d_{i+1}$. Done.

-
This is unreadable! –  JBL Apr 24 '10 at 15:02
@ JBL: Now it is ok. –  Sunni Apr 24 '10 at 15:28