MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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 – 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
up vote 2 down vote accepted

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.

share|cite|improve this answer
@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.

share|cite|improve this answer
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.

share|cite|improve this answer
This is unreadable! – JBL Apr 24 '10 at 15:02
@ JBL: Now it is ok. – Sunni Apr 24 '10 at 15:28

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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