18
$\begingroup$

I want to prove that the function $$g(x)=\frac{\ln(S_n (x))}{\ln(S_{n-1}(x))},\,x >0$$ is increasing in $x$ for all $n$, where $ S_n(x)= \sum_{m=0}^{n}\frac{x^m}{m!}$. Differentiating gives something messy that I have not been able to prove it is non-negative. I have also been trying to find an appropriate $h(x)$ increasing and proving that $ h(g(x))$ is increasing $\ln(\cdot)$ seems a good candidate.

By plotting I am almost convinced the statement is true.

$\endgroup$
  • $\begingroup$ Isn't $\lim_{n\to\infty}g=1$? $\endgroup$ – Vincenzo Oliva Mar 8 '15 at 23:33
  • $\begingroup$ @VincenzoOliva the limit is $\frac{n}{n-1}$. $\endgroup$ – clark Mar 8 '15 at 23:45
  • $\begingroup$ I said as $n\to\infty$, so the limit is indeed $1$. $\endgroup$ – Vincenzo Oliva Mar 8 '15 at 23:46
  • $\begingroup$ @VincenzoOliva okay sorry, misread the subscript $\endgroup$ – clark Mar 8 '15 at 23:47
  • $\begingroup$ @VincenzoOliva What about the function $g_n(x)=\frac{x}{n}$? Eventually is zero. But still for all $n$ it is increasing $\endgroup$ – clark Mar 8 '15 at 23:52
11
$\begingroup$

Note: Here is a first step towards a complete answer. The point I like to address is the discrete log-concavity of the function $S_n$ for fixed $x>0$. This means $S_n$ fulfils

\begin{align*} S_{n-1}^2(x)\geq S_n(x)S_{n-2}(x)\qquad\qquad x>0, n\geq 2\tag{1} \end{align*}

A corresponding example can be found e.g. in the slides about Log-convexity and Log-concavity by Dmitry Karp. You might have a look at the section about Bessel functions where the inequality (1) for these functions is stated and some sharper results are presented afterwards.

Please note that in order to show $g(x)$ is increasing an even sharper inequality than (1) has to be proved.

We start as @Arashium did. Using the differential operator $D_x$ we obtain \begin{align*} D_xS_n(x)=D_x\sum_{m=1}^{n}\frac{x^{m-1}}{(m-1)!}=\sum_{m=0}^{n-1}\frac{x^m}{m!}=S_{n-1}(x) \end{align*} and by omitting the argument $x$ we get \begin{align*} D_x\ln(S_n)&=\frac{1}{S_n}D_x(S_n)=\frac{S_{n-1}}{S_n}\\ \end{align*} and \begin{align*} D_xg&=D_x\frac{\ln(S_n)}{\ln(S_{n-1})} =\frac{\ln(S_{n-1})D_x\ln(S_n)-\ln(S_n)D_x\ln(S_{n-1})}{\ln^2(S_{n-1})}\\ &=\frac{1}{\ln^2(S_{n-1})}\left(\frac{S_{n-1}}{S_n}\ln(S_{n-1})-\frac{S_{n-2}}{S_{n-1}}\ln(S_n)\right)\tag{2} \end{align*}

In order to show that the function $g$ is increasing we need $D_xg\geq 0$.

Therefore the following is to prove according to (2) \begin{align*} S_{n-1}^2\geq S_{n-2}S_n\frac{\ln(S_n)}{\ln(S_{n-1})}\tag{3} \end{align*}

Here's the proof of the weaker inequality (1) showing that $S_n(x)$ is discrete log-concave for fixed $x>0$.

\begin{align*} S_{n-1}(x)^2&-S_{n-2}(x)S_n(x)=\\ &=\left(S_{n-2}(x)+\frac{x^{n-1}}{(n-1)!}\right)^2-S_{n-2}(x)\left(S_{n-2}(x)+\frac{x^{n-1}}{(n-1)!}+\frac{x^{n}}{n!}\right)\\ &=S_{n-2}(x)\left(\frac{x^{n-1}}{(n-1)!}-\frac{x^{n}}{n!}\right)+\frac{x^{2n-2}}{(n-1)!^2}\\ &=\frac{x^{n-1}}{(n-1)!}S_{n-2}(x)\left(1-\frac{x}{n}\right)+\frac{x^{2n-2}}{(n-1)!^2}\\ &=\frac{x^{n-1}}{(n-1)!}\left(\sum_{m=0}^{n-2}\frac{x^m}{m!}\right)\left(1-\frac{x}{n}\right)+\frac{x^{2n-2}}{(n-1)!^2}\\ &=\frac{x^{n-1}}{(n-1)!}\left(\sum_{m=0}^{n-2}\frac{x^m}{m!}-\frac{1}{n}\sum_{m=0}^{n-2}\frac{x^{m+1}}{m!}\right) +\frac{x^{2n-2}}{(n-1)!^2}\\ &=\frac{x^{n-1}}{(n-1)!}\left(\sum_{m=0}^{n-2}\frac{x^m}{m!}-\frac{1}{n}\sum_{m=1}^{n-1}\frac{x^{m}}{(m-1)!}\right) +\frac{x^{2n-2}}{(n-1)!^2}\\ &=\frac{x^{n-1}}{(n-1)!}\left(1+\sum_{m=1}^{n-2}\left(\frac{1}{m}-\frac{1}{n}\right)\frac{x^m}{(m-1)!}-\frac{x^{n-1}}{n(n-2)!}\right) +\frac{x^{2n-2}}{(n-1)!^2}\\ &=\frac{x^{n-1}}{(n-1)!}\left(1+\sum_{m=1}^{n-2}\left(\frac{1}{m}-\frac{1}{n}\right)\frac{x^m}{(m-1)!}\right)\\ &\qquad\qquad+\frac{x^{2n-2}}{(n-1)!(n-2)!}\left(\frac{1}{n-1}-\frac{1}{n}\right)\tag{4}\\ &>0\\ \end{align*}

From the line (4) it's obvious that the inequality is valid and we may therefore conclude that $S_n$ is discrete log-concave.

The challenge is of course to sharpen the inequality (4) in order to obtain (3).

Note: Since the function $\ln$ is monotonically increasing we obtain due to the log-concavity of $S_n$

\begin{align*} \ln\left(S_{n-1}^2(x)\right)&\geq\ln\left(S_n(x)S_{n-2}(x)\right)\\ 2\ln\left(S_{n-1}(x)\right)&\geq\ln\left(S_n(x)\right)+\ln\left(S_{n-2}(x)\right)\\ \end{align*}

which may of some use for further calculations.

$\endgroup$
10
+250
$\begingroup$

I can reduce the problem to a purely polynomial identity, without any logs in it. As explained by both @MarkusScheuer and @Arashium, the inequality to be shown is equivalent to $S_{n-1}^2\geq S_{n-2}S_n\frac{\ln(S_n)}{\ln(S_{n-1})}$. To isolate one of the logs, let us put $\phi_n=\frac{S_{n-1}^2}{S_{n-2}S_n}\ln(S_{n-1})-\ln(S_n)$. The goal is then to show that $\phi_n$ is nonnegative. Since $\phi_n(0)=0$, it will suffice to show that $\phi'_n$ is nonnegative. If we set $F_n=\frac{S_{n-1}^2}{S_{n-2}S_n}$, then

$$\phi'_n=F'_n\ln(S_{n-1})+F_n\frac{S_{n-2}}{S_{n-1}}-\frac{S_{n-1}}{S_{n}}= F'_n\ln(S_{n-1}) \tag{1} $$

Since $\ln(S_{n-1}) \geq 0$, it suffices to show that $F'_n$ is nonnegative. A little computation shows that

$$ F'_n=\frac{S_{n-1}}{(S_{n-2}S_n)^2}G_n, \ \text{with} \ G_n=2S_nS_{n-2}^2-S_{n-1}(S_{n-3}S_n+S_{n-2}S_{n-1}) $$

It will suffice to show that the rescaled polynomial $H_n=\frac{n!(n-1)!(n-2)!}{x^{n-2}}G_n$ satisfies

$$ H_n=\sum_{0 \leq i \leq j \leq n-2} (n-j)!(n-j-1)!(j-i)! \binom{n-2}{j}\binom{j}{i}\binom{2n+1-i-j}{j-i}x^{i+j} \tag{2} $$

I have checked that (2) is true for any $n\leq 40$ with the help of a computer, but failed to find a proof so far. I created a separate question for the proof of (2).

$\endgroup$
  • $\begingroup$ Nice! Okay, this has to fall at some point soon. In the meantime, +200 to you, it would be crazy if this method doesn't work. $\endgroup$ – David E Speyer Mar 30 '15 at 17:00
5
+100
$\begingroup$

I'M SORRY, THIS ANSWER WAS BROKEN. In fact, $(\dagger)$ does not imply $(\ast)$. I'll leave it up for now, until I've figured out what best to do with it.


The point of this answer is to provide a reduction to a different polynomial inequality. Although I can't prove this inequality either, I am more optimistic about it, because it is quadratic in the $S_n$, instead of cubic like Ewan's, and because I can show it is logically equivalent to Ewan's inequality.

Let's recall that Ewan's inequality is $$-S_{n-1}^2 S_{n-2} + 2 S_n S_{n-2}^2 - S_{n} S_{n-1} S_{n-3} \geq 0 \quad (\ast).$$ The point of this answer is to show that $(\ast)$ is logically equivalent to $$\frac{n-1}{n} S_{n-1}^2 \leq S_n S_{n-2}. (\dagger)$$ For $2 \leq n \leq 30$, I've checked the stronger statement that the coefficients of $S_n S_{n-2} - \frac{n-1}{n} S_{n-1}^2$ are positive.


Proof that $(\ast)$ implies $(\dagger)$: Dividing by $S_n S_{n-1} S_{n-2}$, $(\ast)$ is $$0 \leq - \frac{S_{n-1}}{S_n} + 2 \frac{S_{n-2}}{S_{n-1}} - \frac{S_{n-3}}{S_{n-2}} = \frac{d}{dx} \left( \log \frac{S_{n-1}^2}{S_{n} S_{n-2}} \right)$$ So $(\ast)$ is equivalent to the claim that $\frac{S_{n-1}^2}{S_{n} S_{n-2}}$ is increasing. We note that $\lim_{x \to \infty} \frac{S_{n-1}^2}{S_{n} S_{n-2}} = \frac{n}{n-1}$ so, if $(\ast)$ holds, then $\frac{S_{n-1}^2}{S_{n} S_{n-2}} \leq \frac{n}{n-1}$ for all $x$, which rearranges to $(\dagger)$. $\square$

Incidentally, we can also use this to give another proof that $(\ast)$ is equivalent to the original inequality: $\frac{S_{n-1}^2}{S_{n} S_{n-2}} = \frac{S_{n-1}/S_{n}}{S_{n-2}/S_{n-1}}$. If $f(x)/g(x)$ is increasing, then so is $\int_0^y f(x) dx/\int_0^y g(x) dx$ (see, for example, [here][1]). So $\frac{\int S_{n-1}/S_{n}}{\int S_{n-2}/S_{n-1}} = \frac{\log S_{n}}{\log S_{n-1}}$ is increasing.

Proof that $(\dagger)$ implies $(\ast)$. Starting with $(\dagger)$, multiply by $S_n S_{n-2} x^{2n-2}/(n! (n-1)!)$ to get $$S_n S_{n-1}^2 S_{n-2} \frac{x^n x^{n-2}}{n! (n-2)!} \geq \frac{(x^{n-1})^2}{(n-1)!^2} S_n^2 S_{n-2}^2.$$ I miscopied the sign at this step; the inequality in the middle should point the other way. I've deleted the steps after this, but the idea was to get to do some algebra, get to an AM-GM, and then do some more algebra. Since the AM-GM is the only non-reversible step, this means we can't prove $(\ast)$ by this route.

In other words, $$(1/2) (x^n/n! S_{n-1} S_{n-2} + x^{n-2}/(n-2)! S_n S_{n-1}) \geq S_n (x^{n-1}/(n-1)!) S_{n-2} \quad (\ast \ast)$$ is presumably true, since it is logically equivalent to $(\ast)$. But $$\sqrt{x^n/n! S_{n-1} S_{n-2} \cdot x^{n-2}/(n-2)! S_n S_{n-1}} \geq S_n (x^{n-1}/(n-1)!) S_{n-2}$$ is false already for $n=2$. So any attempt to prove $(\ast \ast)$ must do something more gentle than AM-GM.

$\endgroup$
  • $\begingroup$ Note that my inequation is not really cubic, it only appears so because the terms in degree $3$ have not yet been cancelled out. This answer of yours does much more than just "reducing cubic to quadratic" $\endgroup$ – Ewan Delanoy Mar 23 '15 at 17:55
  • $\begingroup$ @EwanDelanoy Thanks! So, can you finish the proof now? $\endgroup$ – David E Speyer Mar 23 '15 at 21:05
  • 1
    $\begingroup$ I found nothing new so far, but if I don't finish the proof somebody else probably will soon. The inequality looks much more tractable now $\endgroup$ – Ewan Delanoy Mar 24 '15 at 18:38
  • $\begingroup$ +1 for your interesting approach and for your commendable manner with respect to bounties! $\endgroup$ – Markus Scheuer Mar 27 '15 at 11:58
  • $\begingroup$ @DavidSpeyer In the first version of my answer I reduced the inequality to a log-free inequality. I have now updated my answer and reduced the problem to a log-free equality, for which unfortunately my proof is still incomplete. Let me know if you have any ideas $\endgroup$ – Ewan Delanoy Mar 30 '15 at 16:51
4
$\begingroup$

I don't have a solution here but just write down what I have reached till now.

I cannot solve it now since I am in rush to leave. But it may help some others to continue.

To show $\mathfrak{g}(x)$ is increasing: $$\mathfrak{g}(x)=\frac{\ln f}{\ln g}$$

$$\mathfrak{g}'(x)\ge0$$

$$\mathfrak{g}'(x)=\frac{\frac{f'}{f}\ln g -\frac{g'}{g}\ln f}{(\ln g)^2}\ge 0$$

or

$$\frac{f'}{f}\ge \frac{g'}{g}\frac{\ln f}{\ln g}$$

here $$f(x)=S_{n}(x)$$ $$g(x)=S_{n-1}(x)$$ $$S'_{k}(x)=S_{k-1}(x)$$

So we need to show

$$\ln (S_{n-1}) S^2_{n-1} \ge S_{n}S_{n-2} \ln (S_n)$$

$$S^2_{n-1}=S^2_{n-2}+(\frac{x^{n-1}}{(n-1)!})^2+2\frac{x^{n-1}}{(n-1)!} S_{n-2}$$

$$S_{n}S_{n-2}=S^2_{n-2}+S_{n-2}(\frac{x^{n-1}}{(n-1)!}+\frac{x^n}{n!})$$

The rest of the proof seems to be more complicated than the question. I am very glad if somebody can continue it.

I am thinking about inductive reasoning too.

$\endgroup$
  • $\begingroup$ Every attempt of solution I get stops at the same place. Maybe it should be interesting to prove this inequality. Another observation is that differentiating the difference of the terms in the last inequality seems to yield a quite sharp thing - at least dumb methods did not work for me. $\endgroup$ – João Ramos Mar 11 '15 at 16:16
  • $\begingroup$ @JoãoRamos I tried so many other ways which did not work. This question seems to be in hard edge of inequality which cannot be proven such easy. $\endgroup$ – Arashium Mar 12 '15 at 16:07
3
$\begingroup$

I can provide half the combinatorial argument that Ewan is asking for. In Ewan's notation, $$G_n = - (S_n-x^n/n!) S_{n-1} S_{n-2} + 2 S_n (S_{n-1} - x^{n-1}/(n-1)!) S_{n-2} - S_n S_{n-1} (S_{n-2} - x^{n-2}/(n-2)!)$$ $$=\frac{x^n}{n!} S_{n-1} S_{n-2} - 2 \frac{x^{n-1}}{(n-1)!} S_n S_{n-2} + \frac{x^{n-2}}{(n-2)!} S_n S_{n-1}.$$ Note that this makes it clear why $G_n$ has terms between $x^{n-2}$ and $x^{3n-3}$ (and a little more work shows that the coefficient of $x^{3n-4}$ is $0$.)

I can deal with $x^m$ for $n \leq m \leq 2n-3$. Set $m=n+r$, so $0 \leq r \leq n-3$. (It is also easy to handle $r=-1$ and $r=-2$, but I don't want to write out the details.) We want to understand $$\frac{[x^r]( S_{n-1} S_{n-2})}{n!} - 2 \frac{[x^{r+1}] (S_{n} S_{n-2})}{(n-1)!} + \frac{[x^{r+2}] (S_{n} S_{n-1})}{(n-2)!} \quad (\ast)$$ where $x^q f(x)$ denotes the coefficient of $x^q$ in $f(x)$. Now, $S_n(x)$ is the first $n$ terms of the Taylor series for $e^x$. So, for $r$ in the stated range, $$(\ast) = \frac{[x^r]e^{2x}}{n!} - 2 \frac{[x^{r+1}] e^{2x}}{(n-1)!} + \frac{[x^{r+2}] e^{2x}}{(n-2)!} = \frac{2^r}{r! n!} - 2 \frac{2^{r+1}}{(r+1)! (n-1)!} + \frac{2^{r+2}}{(r+2)! (n-2)!}.$$

Factoring out $2^r/((r+2)! n!)$, what remains is $$(r+2)(r+1) - 4 (r+2)(n) + 4 n(n-1).$$

The region $(r+2)(r+1) - 4 (r+2)(n) + 4 n(n-1) \geq 0$ is the exterior of a parabola (shown in blue), the region $r \leq n-3$ is a half plane (shown in yellow). The line and the parabola meet at $(r,n) = (-2,1)$ and $(-1, 2)$ so there are no integer points where $r \leq n-3$ and $(r+2)(r+1) - 4 (r+2)(n) + 4 n(n-1) < 0$.

enter image description here

What I can't figure out is how to deal with the terms for $r>n-3$, where the $S_i S_j$ terms in $(\ast)$ no longer match $e^{2x}$ in the relevant degrees.

$\endgroup$
-1
$\begingroup$

It's not hard to prove that $ dS_n/dx = S_{n-1} $, and since $ Sn(x) > 0 $ for all x > 0 and any natural n, the derivative of g(x) is positive for all x.

$\endgroup$
  • $\begingroup$ I am afraid it is not such easy... $\endgroup$ – Arashium Mar 10 '15 at 23:24
  • 1
    $\begingroup$ Are you perhaps differentiating in the following way? $$\left ( \frac{f(x)}{g(x)}\right )'=\frac{f'(x)}{g'(x)}$$ The rule should be $$\left ( \frac{f(x)}{g(x)}\right )'=\frac{f'(x)g(x)-f(x)g'(x)}{g^2(x)}$$ $\endgroup$ – clark Mar 10 '15 at 23:28
-1
$\begingroup$

Instead of differentiating $g$ you may try with the definition of an increasing function. Given $x_1, x_2\in \mathbb{R}^{+}$ such that $x_1 < x_2$ then $g(x_1) < g(x_2)$.

You have that the $\ln$ is an increasing function and so is the $S_n$ for a fixed $n$, furthermore $S_n(x) > S_{n-1}(x),\ \forall x$ (and so its derivative, which is how the function $S$ varies).

Putting everything together, \begin{equation*} g(x_1) = \frac{\ln(S_n(x_1))}{\ln(S_{n-1}(x_1))} < \frac{\ln(S_n(x_2))}{\ln(S_{n-1}(x_2))} = g(x_2) \end{equation*}

and that's it.

$\endgroup$
  • $\begingroup$ "Putting everything together" This is sheer bluff. -1 $\endgroup$ – Ewan Delanoy Mar 12 '15 at 15:40
  • $\begingroup$ Why it should be a bluff? if you have an increasing function of an increasing (nested) function, is not the whole one increasing? $\endgroup$ – Oscar Mar 12 '15 at 15:47
  • $\begingroup$ $\frac{\ln(S_n)}{\ln(S_{n-1})}$ is not the composition of two increasing functions. It is only the quotient of two functions, both of which are compositions of increasing functions. But the quotient of two increasing functions is not always increasing ... $\endgroup$ – Ewan Delanoy Mar 12 '15 at 15:55
  • $\begingroup$ Yes, but the ratio of these two increasing functions is always greater than one and the denominator grows slower than the numerator, so it is an increasing function. $\endgroup$ – Oscar Mar 12 '15 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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