# Recurrence relation for binomial CDF

The binomial PMF (probability of exactly k successes in n trials with probability p)

$$f\left( {k,n,p} \right) = {{n!} \over {k!\left( {n - k} \right)!}}{p^k}{\left( {1 - p} \right)^{n - k}}$$

And the recurrence relation for an additional success is

$$f\left( {k + 1,n,p} \right) = {{n - k} \over {k + 1}}\;{p \over {1 - p}}f\left( {k,n,p} \right)$$

The CDF (probability of at most k successes) is

$$F\left( {k,n,p} \right) = \sum\limits_{i = 0}^k {{{n!} \over {i!\left( {n - i} \right)!}}{p^i}{{\left( {1 - p} \right)}^{n - i}}}$$

My question is, is there a similarly simple recurrence relation for the CDF for an additional trial?

$$F\left( {k,n + 1,p} \right) = ??$$

Thank you.

• $$\binom{n+1}{i} = \binom{n}{i} + \binom{n}{i-1}$$ \begin{align} F(k,n+1,p) &= \sum_{i=0}^{k}\binom{n+1}{i}p^{i}(1-p)^{n+1-i}\\ &= \sum_{i=0}^{k}\binom{n}{i}p^{i}(1-p)^{n+1-i} + \sum_{i=1}^{k}\binom{n}{i-1}p^{i}(1-p)^{n+1-i}\\ &= (1-p)F(k,n,p) + p\sum_{j=0}^{k-1}\binom{n}{j}p^j(1-p)^{n-j}\\ &= (1-p)F(k,n,p) + pF(k-1,n,p) \end{align} – Dhruv Kohli - expiTTp1z0 Oct 21 '17 at 16:58
• Will add as answer once verified. – Dhruv Kohli - expiTTp1z0 Oct 21 '17 at 17:00
• I've verified that with several numerical examples, thank you. I'm trying to write a simple loop that tests for the CDF to descend below a threshold value starting from F(k,n,p)=1 for k=n. Is there a way to express F(k-1,n,p) in terms of previously calculated values? – shg Oct 21 '17 at 17:36
• Maybe I can say that more clearly: Start with n=k, F(k,n,p)=1. Increase n until F descends below a specified threshold. – shg Oct 21 '17 at 17:45

$$\binom{n+1}{i} = \binom{n}{i} + \binom{n}{i-1}$$

\begin{align} F(k,n+1,p) &= \sum_{i=0}^{k}\binom{n+1}{i}p^{i}(1-p)^{n+1-i}\\ &= \sum_{i=0}^{k}\binom{n}{i}p^{i}(1-p)^{n+1-i} + \sum_{i=1}^{k}\binom{n}{i-1}p^{i}(1-p)^{n+1-i}\\ &= (1-p)F(k,n,p) + p\sum_{j=0}^{k-1}\binom{n}{j}p^j(1-p)^{n-j}\\ &= (1-p)F(k,n,p) + pF(k-1,n,p) \end{align}

I think you also need this, $$F(k-1,n,p) + \binom{n}{k}p^k(1-p)^{n-k} = F(k,n,p)$$

• I was trying to avoid having to calculate f(k,n,p), but that's certainly faster than what I had, thank you. – shg Oct 21 '17 at 18:02

Just to wrap that in a bow,

\eqalign{ F\left( {k,n + 1,p} \right) = & \left( {1 - p} \right)F\left( {k,n,p} \right) + pF\left( {k - 1,n,p} \right) \cr = & \left( {1 - p} \right)F\left( {k,n,p} \right) + p\left( {F\left( {k,n,p} \right) - f\left( {k,n,p} \right)} \right) \cr = & F\left( {k,n,p} \right) - pf\left( {k,n,p} \right) \cr}

Thank you again.