Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

For any integer $n\ge 3$, let $P(x)=\sum\limits_{i(=2k)\ge 0}^{n}\binom{n}{2k}(1-x)^k$, $Q(x)=\sum\limits_{i(=2k+1)\ge 0}^{n}\binom{n}{2k+1}(1-x)^{k+1}$. Define $\frac{P(x)}{Q(x)}\equiv\sum\limits_{i=0}^{\infty}c_ix^i $. I like to know $c_0> c_1> c_2>\cdots$, but I don't know how to show it.

share|improve this question
3  
Your notation for the sums defining P and Q is quite nonstandard and confusing, but I think I understand what you mean. Just to make sure: do you mean to sum over all integers k for which 0≤2k≤n (in the first sum) and 0≤2k+1≤n (in the second sum)? Also, what reasons (if any) do you have for assuming the desired result is true? –  Harald Hanche-Olsen Apr 24 '10 at 0:36
1  
Under Harald's guess as to the meaning, for $n=2$ we get $P=2-x$ and $Q=2(1-x)$, so that $P/Q=1/2(1+1/(1-x))$, whose coefficients are not strictly decreasing. So, if Harald was right, either miwalin meant for $n>2$ or for $c_0 \geq c_1 \geq c_2 \geq \dots$. –  Kevin O'Bryant Apr 24 '10 at 1:24
    
@Bryant: Right, if $n>2$, the coefficients are strictly decreasing. –  Sunni Apr 24 '10 at 1:58
    
@ Olsen: Yes, you got it. The result is useful in determining the convergence range of a functional iteration. I tried some examples on matlab for $n=3,4,5$. –  Sunni Apr 24 '10 at 2:05
    
Can you write a (linear) recursion for $c_i$'s (fixed $n$)? –  Wadim Zudilin Apr 24 '10 at 4:10

2 Answers 2

up vote 10 down vote accepted

The polynomials $P_n$ and $Q_n$ can be written as $$ P_n(x)=(1+\sqrt{1-x})^n+(1-\sqrt{1-x})^n, \qquad Q_n(x)=\sqrt{1-x}\bigl((1+\sqrt{1-x})^n-(1-\sqrt{1-x})^n\bigr). $$ In particular, they are both solutions to the linear difference equation $P_{n+1}(x)=2P_n(x)-xP_{n-1}(x)$ implying that their quotient $f_n(x)=P_n(x)/Q_n(x)$ satisfies the nonlinear recursion $$ f_{n+1}(x)=\frac{1+f_n(x)}{1+(1-x)f_n(x)} $$ (already observed experimentally by Martin Rubey).

The property saying that the coefficients of the power series $f(x)=c_0+c_1x+c_2x^2+\dots$ satisfy $c_0\ge c_1\ge c_2\ge\dots$ can be rephrased as $c_0-(1-x)f(x)\ge0$, where the record $a_0+a_1x+a_2x^2+\dots\ge0$ means that all $a_i\ge0$. This makes the original problem equivalent to $1-(1-x)f_n(x)\ge0$ for all $n$. This follows by induction on $n$. The base of induction is clear verification (already done by the author for a few first $n$). Assuming that it is true for a given $n$ and using that the non-negative expansion $1-(1-x)f_n(x)$ has the vanishing constant term, we conclude that the (formal) power series $$ \frac1{1-\frac12\bigl(1-(1-x)f_n(x)\bigr)} =1+\sum_{k=1}^\infty\frac1{2^k}\bigl(1-(1-x)f_n(x)\bigr)^k $$ is non-negative. It remains to apply the above recursion for $f_n(x)$: $$ 1-(1-x)f_{n+1}(x) =\frac x{1+(1-x)f_n(x)} =\frac x2\cdot\frac1{1-\frac12\bigl(1-(1-x)f_n(x)\bigr)}, $$ and the desired property follows.

share|improve this answer
    
A very good proof. –  Sunni Apr 25 '10 at 14:57
    
Thanks, miwanlin! Controry to my predictions it seems to be non-technical. –  Wadim Zudilin Apr 25 '10 at 22:50

(Not an answer - but too large for a comment) here are recurrences for the first few n. I don't have time right now to look at them, but shouldn't be hard to spot a pattern...

(1) -> P n == reduce(+, [binomial(n, 2*k)*(1-x)^k for k in 0..n | 2*k Q n == reduce(+, [binomial(n, 2*k+1)*(1-x)^(k+1) for k in 0..n | 2*k+1 n:=3; guessPRec(entries complete first(coefficients series(P n/Q n, x=0), 10))

   (3)  [[f(n): - 4f(n + 1) + f(n) + 1= 0,f(0)= 1]]

(4) -> n:=4; guessPRec(entries complete first(coefficients series(P n/Q n, x=0), 10))

   (4)  [[f(n): - 8n f(n + 1) + 4n f(n) + n= 0,f(0)= 1]]

(5) -> n:=5; guessPRec(entries complete first(coefficients series(P n/Q n, x=0), 30))

                                                                      1
   (5)  [[f(n): - 16f(n + 2) + 12f(n + 1) - f(n) + 1= 0,f(0)= 1,f(1)= -]]
                                                                      2

(6) -> n:=6; guessPRec(entries complete first(coefficients series(P n/Q n, x=0), 30))

   (6)
                                                                        1
   [[f(n): - 32n f(n + 2) + 32n f(n + 1) - 6n f(n) + n= 0,f(0)= 1,f(1)= -]]
                                                                        2

(7) -> n:=7; guessPRec(entries complete first(coefficients series(P n/Q n, x=0), 30))

   (7)
   [
     [f(n): 64f(n + 3) - 80f(n + 2) + 24f(n + 1) - f(n) - 1= 0, f(0)= 1,
            1        3
      f(1)= -, f(2)= -]
            2        8
     ]

(8) -> n:=8; guessPRec(entries complete first(coefficients series(P n/Q n, x=0), 100))

   (8)
   [
     [f(n): 128n f(n + 3) - 192n f(n + 2) + 80n f(n + 1) - 8n f(n) - n= 0,
                     1        3
      f(0)= 1, f(1)= -, f(2)= -]
                     2        8
     ]

(9) -> n:=9; guessPRec(entries complete first(coefficients series(P n/Q n, x=0), 100))

   (9)
   [
     [f(n): - 256f(n + 4) + 448f(n + 3) - 240f(n + 2) + 40f(n + 1) - f(n) + 1= 0
       ,
                     1        3         5
      f(0)= 1, f(1)= -, f(2)= -, f(3)= --]
                     2        8        16
     ]

(10) -> n:=10; guessPRec(entries complete first(coefficients series(P n/Q n, x=0), 100))

   (10)
   [
     [
       f(n):
           - 512n f(n + 4) + 1024n f(n + 3) - 672n f(n + 2) + 160n f(n + 1)
         + 
           - 10n f(n) + n
           =
           0
       ,
                     1        3         5
      f(0)= 1, f(1)= -, f(2)= -, f(3)= --]
                     2        8        16
     ]

(11) -> n:=11; guessPRec(entries complete first(coefficients series(P n/Q n, x=0), 100))

   (11)
   [
     [
       f(n):
           1024f(n + 5) - 2304f(n + 4) + 1792f(n + 3) - 560f(n + 2) + 60f(n + 1)
         + 
           - f(n) - 1
           =
           0
       ,
                     1        3         5
      f(0)= 1, f(1)= -, f(2)= -, f(3)= --]
                     2        8        16
     ]

and, in case it helps, here is the (nonlinear) recurrence for the sequence of $P_n/Q_n$:

(19) -> guessRec([P n/Q n for n in 1..100])

                                                                     1
   (19)  [[f(n): ((- x + 1)f(n) + 1)f(n + 1) - f(n) - 1= 0,f(0)= - -----]]
                                                                   x - 1
share|improve this answer
3  
$$\frac PQ=\sqrt{1-x}\frac{(1+\sqrt{1-x})^n+(1-\sqrt{1-x})^n}{(1+\sqrt{1-x})^n-(1-\sqrt{‌​1-x})^n}$$ –  Wadim Zudilin Apr 24 '10 at 10:04
1  
@Wadim: Your extra $\sqrt{1-x}$ should be in the denominator. –  Gerald Edgar Apr 24 '10 at 11:10
    
@Gerald: Thanks, I realised this after looking at the original question... –  Wadim Zudilin Apr 24 '10 at 12:39
    
Direct expansion shows $\frac PQ=\frac{(1+\sqrt{1-x})^n+(1-\sqrt{1-x})^n}{\sqrt{1-x}[(1+\sqrt{1-x})^n-(1-\sqrt‌​{1-x})^n]}$, how to see that the coefficients are decreasing? –  Sunni Apr 24 '10 at 14:39
1  
The limit on $n$ has decreasing coefficients. –  Gerald Edgar Apr 24 '10 at 15:31

Your Answer

 
discard

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.