# Decreasing coefficients?

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.

-
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
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

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.

-
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

-
$$\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
@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
The limit on $n$ has decreasing coefficients. –  Gerald Edgar Apr 24 '10 at 15:31