1
$\begingroup$

​Hi there,

I bump into a weird sequence, and know for a fact the following holds. (Also, I ran MATLAB simulations to double-check.) This sequence comes up when doing research on computing the reliability of a signal to reach the destination when sent through parallel links and the benefit associated with it. (Details can be too long, which might be helpful to get the solution, but I think those who are very good at dealing with sequences don't need it necessarily.)

For any positive integers $n$ and a real number $t \in (0, 1)$, the following holds:

$\frac{n}{\frac{1}{n} \sum_{i=1}^{n} \frac{1}{1-t^i}} + \frac{t}{1-t} \left( 1 - t^n \right) \leq n$.

I'm struggling to prove this analytically, though. A few techniques that I have tried usually aim at showing an upper bound of LHS is less than or equal to RHS:

The fact that $1 - t \leq 1 - t^i \leq 1 - t^n$ holds for all $i = 1, \dots, n$ implies that $\frac{1}{1-t^n} \leq \frac{1}{n} \sum_{i=1}^{n} \frac{1}{1-t^i} \leq \frac{1}{t}$ holds for all $i = 1, \dots, n$.

Then, LHS is less than or equal to

$n(1-t^n) + \frac{t}{1-t} (1-t^n)$.

Subtracting RHS with the upper bound above, we get

$\frac{t}{1-t} \left( -1 + n(1-t)t^{n-1} + t^n \right)$.

The terms in the parentheses imply that it is less than zero: consider a binomial distribution with paramters $n$ and $t$.

A few other attempts similar to the above one failed. I also tried to use Bernoulli's inequality $(1+x)^n \geq 1+nx$, but it didn't help. Maybe I applied the techniques sloppily.

I feel like we should either prove it by induction (when $n=1$, LHS = RHS. Assuming LHS $\leq$ RHS for $n$, we could show it also is true for $n+1$.), or we begin with defining a sequence, say $S_n = \frac{1}{n} \sum_{i=1}^{n} \frac{1}{1-t^i}$, and show that the forward difference of LHS is less than or equal to the forward difference of RHS (which is 1).

But, even after hours of effort, I couldn't seem to find a clue. Could anyone help? Thanks!

$\endgroup$
  • 1
    $\begingroup$ What is that $\;k\;$ in the inequality? How is it related to $\;n\;$ or whatever? $\endgroup$ – DonAntonio Oct 17 '16 at 11:25
  • $\begingroup$ @DonAntonio Oh, I'm very sorry, it is actually $n$. I will fix it. $\endgroup$ – PurplePenguin Oct 17 '16 at 11:31
1
$\begingroup$

Jensen's Inequality and the fact that $\frac1{1-x}$ is convex on $(0,1)$ say that $$ \frac1n\sum_{k=1}^n\frac1{1-t^k} \ge\frac1{1-\frac1n\sum\limits_{k=1}^nt^k}\tag{1} $$ Therefore, $$ \begin{align} \frac1{\frac1n\sum\limits_{k=1}^n\frac1{1-t^k}}+\frac t{1-t}\frac{1-t^n}n &\le\left(1-\frac1n\sum\limits_{k=1}^nt^k\right)+\frac1n\sum\limits_{k=1}^nt^k\\ &=1\tag{2} \end{align} $$ $n$ times inequality $(2)$ is the desired inequality.

$\endgroup$
  • $\begingroup$ First, thanks very much. And second, I just have to ask this. I knew Jensen's inequality, but never thought of using it. How did you come to think of using it? Was that obvious? I was able to figure out that the second term of LHS was some how the geometric series, and I had a hunch that I should do something with the averages... Man isn't your solution concise. $\endgroup$ – PurplePenguin Oct 17 '16 at 12:13
  • 1
    $\begingroup$ @PurplePenguin: whenever I see an average or a mean of things in an inequality, I think of Jensen, especially when there is another mean that is related by a convex function. The term $\frac{1-t^n}{1-t}$ also quickly brings to mind the sum of a geometric series, which gives the second mean (related by a convex function). $\endgroup$ – robjohn Oct 17 '16 at 12:15
1
$\begingroup$

The AM-GM-HM inequality to begin with:

$$\frac1n\sum_{i=1}^n\frac1{1-t^i}\ge\sqrt[n]{\frac1{1-t}\cdot\frac1{1-t^2}\cdot\ldots\cdot\frac1{1-t^n}}\ge$$

$$\ge\frac n{1-t+1-t^2+\ldots+1-t^n}=\frac n{n-\frac{t(1-t^n)}{1-t}}\implies$$$${}$$

$$\frac n{\frac1n\sum\limits_{i=1}^n\frac1{1-t^i}}\le n\cdot\frac{n-\frac{t(1-t^n)}{1-t}}n=n-\frac{t(1-t^n)}{1-t}\implies$$$${}$$

$$\frac n{\frac1n\sum\limits_{i=1}^n\frac1{1-t^i}}+\frac t{1-t}(1-t^n)\le n-\frac{t(1-t^n)}{1-t}+\frac t{1-t}(1-t^n)=n\;\;\;\square$$

$\endgroup$
  • $\begingroup$ This solution is also a very concise one! Thanks for the solution, and the first comment that pointed out the misspelled expressions. That early on made the silly question valid. Also I want to ask: did the arithmetic mean and the geometric mean make you try applying the AM-GM-HM? $\endgroup$ – PurplePenguin Oct 17 '16 at 12:27
  • 1
    $\begingroup$ @PurplePenguin Yes. I didn't think of Jensen's inequality straightforward but did first think of convex functions, which would eventually lead to the same, I guess. Yet the first expression's denominator made me think "harder" of the AM-GM-HM inequality, which is really more elementary...and it came up pretty easily. $\endgroup$ – DonAntonio Oct 17 '16 at 12:32

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.