How many tries to get at least k successes? The probability $P'$ of getting at least $k$ successes in $n$ independent tries, given probability of a single success $s$, equals one minus the summed probabilities of getting only $0$ to $k-1$ successes:
$P'(k, n, s) = 1 - \sum\limits_{i=0}^{k-1} P(i, n, s)$
where the probability $P$ of getting exactly $k$ successes is:
$P(k, n, s) = \,_nC_k \cdot s^k \cdot (1 - s)^{n - k}$
Now suppose I want to know how many tries I need to achieve a given probability $P'$. How do I solve for $n$?
This question is a lot like the question here:
On the Total Number of Tries Required to have $n$ Successes
But in that question each trial is not independent, since it's about selecting stones from a bag without replacement. In my question, each trial is independent.
 A: This is a partial solution
For the case exactly $k$ success:
The probability that a sequence of independant Bernoulli trials takes $n$ steps before getting the $k^{th}$ success is given by (an adaptation of) the binomial negative distribution. Think of it this way:
You need your $n^{th}$ trial to be a success. You also need $k-1$ successes in the $n-1$ remaining spots. The rest are failures. Let $X$ be the number of trials it takes to get $k$ success. The probability of $X$ being $n$  is then given by
$$
\Pr(X=n)={n-1\choose k-1}s^{k}(1-s)^{n-k}
$$
Its median seems to be somewhat complicated, see for example this.
A: There is no exact closed form solution. If $k$ is moderately large, the normal approximation to the binomial will give you an approximate answer, and you can then do a numerical search around there for the exact answer. For the normal approximation we want $$\Phi\left(\frac{k-ns}{\sqrt{ns(1-s)}}\right) \geq .9,$$ where $\Phi$ is the normal cdf. You can take the inverse cdf, simplify this to a quadratic in $\sqrt n$, and find a value for $n$. Since this is not exact, you can then check other nearby values of $n$ to find the exact solution.
Here's an R function that solves it for you using this approach, though not particularly efficiently:
binomial.size <- function(k,s,p) {
  # Find the smallest sample size n such that a binomial(n,s) has 
  # probability at least p of having k sucesses.

  # our first approximation comes from solving the quadratic:
  n <- ceiling(((-qnorm(p)+sqrt(qnorm(p)^2+4*k/(1-s)))/(2*sqrt(s/(1-s))))^2)

  while(pbinom(k-1,n,s,lower.tail=FALSE)<p) { # our n might be too small...
    n <- n+1
  }

  while(pbinom(k-1,n-1,s,lower.tail=FALSE)>p) { # or too large...
    n <- n-1
  }

  return(n)
}

binomial.size(15,0.4,0.5)
## 37
pbinom(14,37,0.4,lower.tail=FALSE)
## 0.54
pbinom(14,36,0.4,lower.tail=FALSE)
## 0.48--too small!

