Sunday, November 5, 2017

sequences and series - $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!



Answer



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.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...