Given a value $p\in[0,1]$ (a probability of occurrence), I would like to bound the following expression:


$$ s\frac{1-(1-p)^{k+1}}{p(k+1)} + (1-s)\frac{1-(1-p)^{k}}{pk},\ \ \ \text{where $k=\lfloor 1/p \rfloor$ and $s=1/p-k$}.$$


I would like to prove that the latter is bigger than $1-e^{-1}$.


I already know that in each interval where $k$ is constant ($p\in (\frac{1}{k+1},\frac{1}{k}]$), when $p$ approaches to $1/(k+1)$, the expression is bounded by $1-e^{-1}$ from below. Therefore, if I could prove that in such interval the function is increasing in $p$, I would be done.


I've struggling a while trying to prove this (and I have also tried to prove the inequality directly), but I have failed so far.


I think this kind of expressions are not that ''unnatural'' to come out, so maybe somebody else has already studied them. However, I don't know where to look. All this work is in the context of approximation theory and optimization; I have not found similar expressions though.


Any ideas on how I could keep the work or where I should look for similar results? Thanks!



Averaged geometric series with floor function
For a given natural $k$, let $f(p)$ denote the expression in question. We need to show that $f(p)$ is increasing in $p$. Everywhere here $p\in[\frac1{k+1},\frac1k]$. Let 
$$f\_1(p):= f'(p) k (1 + k) (1 - p) p^3,\quad f\_2(p):= f\_1'(p),\quad f\_3(p):= f\_2'(p),$$ 
$$f\_4(p):= \frac{f\_3'(p)}{k (1 + k) (1 - p)^{k-3}}
=1 + 2 k - 3 (1 + k + 4 k^2) p + (2 + k + 16 k^2 + 8 k^3) p^2 - 
 k^2 (6 + 5 k + k^2) p^3.$$ 
 Since $f\_4(p)$ is a polynomial in $k,p$, it is not hard to see (using a computer algebra package or otherwise -- e.g., by observing that $f\_4(p)$ is convex in $p$ for $k\ge2$) that $f\_4(p)<0$ for all real $k\ge2$, and $f\_4(p)<0$ for $k=1$ unless $p=1$. So, $f\_3$ is decreasing, with 
\begin{equation}
 f\_3\Big(\frac1{k+1}\Big)\frac{(1 + k)^{1 + k}}{k^k}=(1+1/k)^k (2 + 6 k + 4 k^2 ) - (3 + 9 k + 10 k^2 + 2 k^3)
 <e(2 + 6 k + 4 k^2 ) - (3 + 9 k + 10 k^2 + 2 k^3)<0
\end{equation}
for $k\ge3$, whereas trivially $f\_3(\frac1{k+1})\le0$ for $k=1,2$. 


So, $f\_3<0$ on $(\frac1{k+1},\frac1k]$, whence $f\_2=f\_1'$ is decreasing and hence its sign pattern is $+$ or $-$ or $+-$ on $[\frac1{k+1},\frac1k]$. 
So, $f\_1(p)\ge f\_1(\frac1{k+1})\wedge f\_1(\frac1k)$. 


But $f\_1(\frac1k)k^2= (1 - 1/k)^k (3 k - 1) - (k - 1)$, so that $f\_1(1/k)$ equals $g(k):=\ln[(1 - 1/k)^k]-\ln\frac{k-1}{3k-1}$ in sign. Since $g''(k)=\frac{3 k+1}{(3k-1)^2 (k-1) k}>0$ for $k>1$, the function $g$ is convex. Moreover, $g(\infty-)=\ln\frac3e\in(0,\infty)$ and hence $g'(\infty-)=0$. So, $g>0$ and hence $f\_1(1/k)>0$. 


Similarly, $f\_1(\frac1{k + 1})\frac{(k+1)^3}k= k+1 - (2 k+1)(\frac k{k+1})^k$, so that $f\_1(\frac1{k + 1})$ equals $h(k):=\ln\frac{k+1}{2k+1}-\ln[(\frac k{k+1})^k]$ in sign. Since $h''(k)=-\frac1{k (k+1) (2 k+1)^2)}<0$, the function $h$ is concave. Moreover, $h(1)=\ln\frac43>0$ and $h(\infty-)=\ln\frac e2>0$. So, $h>0$ and hence $f\_1(\frac1{k + 1})>0$. 


Thus, $f\_1\ge f\_1(\frac1{k+1})\wedge f\_1(\frac1k)>0$ and $f'>0$ on $(\frac1{k+1},\frac1k)$, and hence $f$ is indeed increasing. 


