1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Apr 17, 2010 at 5:54
  • $\begingroup$ The problem cannot be simplified by reducing to judge the positivity of $d_i-d_{i+1}$. $\endgroup$
    – Sunni
    Apr 17, 2010 at 15:25

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ @Zudilin:The third solution is also correct, but rather than upvoted, it was downvoted by someone. $\endgroup$
    – Sunni
    May 10, 2010 at 16:43
  • $\begingroup$ 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. $\endgroup$ May 10, 2010 at 20:22
2
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ 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? $\endgroup$ Apr 17, 2010 at 12:34
  • $\begingroup$ @ Zudilin: At a first glance, the hardest step in your argument lies in how to find the 'effective bound'. $\endgroup$
    – Sunni
    Apr 17, 2010 at 15:32
  • $\begingroup$ The proposer has solved the problem. If you are interested, you may ask me for the solution. $\endgroup$
    – Sunni
    Apr 18, 2010 at 16:48
  • $\begingroup$ 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.? $\endgroup$
    – Ross Tang
    Apr 19, 2010 at 8:36
  • 1
    $\begingroup$ @miwalin: What is M.I.? Does your solution work for any real $p>1$? $\endgroup$ Apr 23, 2010 at 13:58
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ This is unreadable! $\endgroup$
    – JBL
    Apr 24, 2010 at 15:02
  • $\begingroup$ @ JBL: Now it is ok. $\endgroup$
    – Sunni
    Apr 24, 2010 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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