Find the minimum integer satisfying an inequality Let $\alpha \in (0,1)$ and $\beta \in (0,1)$. I want to compute the smallest integer $n > 0$ such that:
$$
1 - \alpha^n - [1 - \alpha]^n \geq \beta.
$$
For example, with $\alpha = 0.75$ and $\beta = 0.99$, we find $n = 17$.
I know that a dichotomy search for n in a wide range, say $[0,10^7]$ is doable. Another method is to let $n$ be temporarily real, find the solution of the equation $1 - \alpha^x - [1 - \alpha]^x = \beta$ for $x > 0$ a real number, then round to the upper integer. But i feel that this equation might be more deep than these algorithms and I search for a better solution. Is there one?
 A: As pointed by Ivan Kaznacheyeu in the comments, we can find bounds of the solution. One of the ways is by using the LogSumExp function:
$$
LSE(x_1, x_2) = \log\left(\exp(x_1) + \exp(x_2)\right)
$$
for any $x_1, x_2 \in \mathbb{R}$.
This can be used to compute bounds of the required integer.
If $n$ satisfies the following inequality:
$$
\left\lceil \frac{\log(1 - \beta)}{\log(\gamma)} \right\rceil \leq n \leq 
\left\lceil \frac{\log\left(\frac{1 - \beta}{2}\right)}{\log(\gamma)} \right\rceil \qquad (1)
$$
where $\gamma = \max(\alpha, 1 - \alpha)$, then:
$$
\alpha^n + (1 - \alpha)^n \geq 1 - \beta. \qquad (2)
$$
Proof
The LSE function satisfies the following inequality:
$$
\max(x_1, x_2) \leq LSE(x_1,x_2) \leq \max(x_1, x_2) + \log(2).
$$
But
$$
\begin{aligned}
\log(\alpha^n + (1 - \alpha)^n) 
& = \log \left[ \exp(n \log(\alpha)) + \exp(n \log(1 - \alpha)) \right] \\
& = LSE(n \log(\alpha), n \log(1 - \alpha)).
\end{aligned}
$$
Hence,
$$
\max(n\log(\alpha), n\log(1 - \alpha))
\leq \log(\alpha^n + (1 - \alpha)^n)
\leq \max(n\log(\alpha), n\log(1 - \alpha)) + \log(2).
$$
Since the log function is increasing, this implies:
$$
\max \left[ n\log(\alpha), n\log(1 - \alpha) \right]
 = n \log \left[ \max(\alpha, 1 - \alpha) \right] = n \log(\gamma).
$$
Hence,
$$
n \log(\gamma) \leq \log(\alpha^n + (1 - \alpha)^n)
\leq n \log(\gamma) + \log(2). \qquad (3)
$$
We want to find $n$ such that the inequality (2) is satisfied.
This is equivalent to:
$$
\log \left[ \alpha^n + (1 - \alpha)^n \right] \geq \log(1 - \beta). \qquad (4)
$$
since $\log$ is a nondecreasing function.
Temporarily assuming that $n$ is a real number, we solve the equation:
$$
\log \left[ \alpha^n + (1 - \alpha)^n \right] = \log(1 - \beta).
$$
All in all, if $n$ satisfies the following inequality:
$$
n \log(\gamma) \leq \log(1 - \beta) \leq n \log(\gamma) + \log(2)
$$
then the equation (2) is satisfied.
This is equivalent to:
$$
\log\left(\frac{1 - \beta}{2}\right) = \log(1 - \beta) - \log(2) \leq n \log(\gamma) \leq \log(1 - \beta).
$$
We can divide the previous inequality by $\log(\gamma) < 0$ and get:
$$
\frac{\log(1 - \beta)}{\log(\gamma)} \leq n \leq 
\frac{\log\left(\frac{1 - \beta}{2}\right)}{\log(\gamma)}.
$$
Returning back to an integer solution, we get that the required integer is defined by the inequality (1). ■
A: I think there should be no 'better' solution.
The function $f(n) = (1-\alpha^n - (1-\alpha)^n)$ is monotonuously increasing in $n$ as both exponential terms are in $(0,1)$, so if you find a solution to $f(n) = \beta$ for $n\in\mathbb{R}^+$, then you can indeed round up $n$ and this should give you the optimal solution for $n\in\mathbb{Z}^+$, given that $\alpha$ and $\beta$ are constants.
Methodology wise, both a dichotomy search and some sort of exact method should be sufficient to solve this question. I am not sure if the equation you posted has a closed-form solution, but I would expect it to be ugly if it exists.
