# $\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$?

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

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

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.

• 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. – PurplePenguin Oct 17 '16 at 12:13
• @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). – robjohn Oct 17 '16 at 12:15

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

• 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? – PurplePenguin Oct 17 '16 at 12:27
• @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. – DonAntonio Oct 17 '16 at 12:32