Edit: I'm clarifying my task and question. I have an algorithm that I want to prove is a $\frac{1}{4}$-approximation. I proved that: $$ \mathbb{E} [f(S_t)] \geq \left( (1-\frac{1}{k})^t-(1-\frac{2}{k})^t \right)f(S_{OPT}) $$ Where $S_t$ is the solution at iteration $t$ and $S_{OPT}$ is the optimal solution, and $k\in\mathbb{N}$ is a given constant.
Now, I need to show that there is a choice of $t\in\mathbb{N}$ such that: $$ \mathbb{E} [f(S_t)] \geq \frac{1}{4}f(S_{OPT}) $$ So, I need to show: $$ \left( (1-\frac{1}{k})^t-(1-\frac{2}{k})^t \right) \geq \frac{1}{4} $$ My attempts so far:
- I tried bounding it with the property $$ (1-\frac{1}{k})^k\leq e^{-1} $$ but I can only do it for the left expression and I'm not sure what to do with the right one.
- I saw that for $t=k \cdot \ln 2$ I get:
$$
(1-\frac{1}{k})^{k \cdot \ln 2}-(1-\frac{2}{k})^{k \cdot \ln 2}
\longrightarrow_{k\rightarrow\infty}
(e^{-1})^{\ln 2}-(e^{-2})^{\ln 2}=\frac{1}{4}
$$
but I need $t$ to be an integer, I tried bounding it with the ceiling and floor functions but I got stuck again. - As the comments suggested, I tried doing a taylor expansion, but I didn't get the same results like the in comments, and I'm not sure why.
You are on the right track.
Consider the function $$F(k,t)=\left(1-\frac{1}{k}\right)^t-\left(1-\frac{2}{k}\right)^t$$ Its derivative cancels at $$t_*=\frac{1}{\log \left(\frac{k-2}{k-1}\right)}\log \left(\frac{\log \left(\frac{k-1}{k}\right)}{\log \left(\frac{k-2}{k}\right)}\right)$$
Expanding at least for large values of $k$ $$F(k,t_*)=\frac{1}{4}+\frac{\log (2)}{4 k}+\frac{1+2 \log (2)+2 \log^2 (2)}{16 k^2}+O\left(\frac{1}{k^3}\right)$$ Notice that $$\frac{\partial^2 F(k,t_*)}{\partial k^2}=\frac{\log (2)}{2 k^2}+\frac{\log (2) (3+\log (4))}{4 k^3}+O\left(\frac{1}{k^4}\right)$$ and $$t_*=k\log(2)+\frac 12(1-3\log(2))-\frac{3+\log (4)}{24 k}-\frac{5+6 \log (2)}{48 k^2}+O\left(\frac{1}{k^3}\right)$$
Now, it is your turn !