Binomial Distribution PMF/CDF Identity I was solving a puzzler and I came across an identity that I've never seen before.  I consulted a couple stats experts and textbooks and have come up empty.  I'm wondering if anyone has ever seen this before.
Let $f(k, n, p)$ and $F(k, n, p)$ be the PMF and CDF of the binomial distribution, respectively.  Then it appears that:
$F(k, 2k+1, p) = F(k, 2k+2, p) + \frac{1}{2} f(k+1, 2k+2, p)$
Haven't formally proved this.  I'm guessing it's not too difficult; maybe needs some of the binomial coefficient recurrence identities.  But I just wanted to ask if anyone has come across this before or if it's a well-known identity.
Thanks!

There is a simple probability argument.  It minimizes the math and intuitively shows why such an equality exists which does not depend on $p.$
In the following I will employ just two basic rules of probability: conditional probabilities multiply and mutually exclusive probabilities add.  You all know what these vague (but memorable) phrases mean, so I won't belabor the details.
For any $n\ge 0,$ consider a sequence of $n+1$ Bernoulli$(p)$ observations $X_1, X_2, \ldots, X_{n+1}$ ("coin flips").  By definition, each random variable has a chance $p$ to equal $1$ and otherwise equals $0.$
$F(k,n)$ is the chance that $k$ or fewer of the first $n$ outcomes equal $1.$ This can happen in two ways:

*

*$k$ or fewer of all $n+1$ outcomes equal $1.$  The chance of this is $\color{blue}{F(k,n+1)}.$


*Exactly $k+1$ of the outcomes equal $1$ (the chance of this is written $\color{red}{f(k+1,n+1)})$ and the final outcome is $1$ (making $k$ of the first $n$ outcomes equal to $1$).
When the $X_i$ are independent (or just exchangeable), all re-orderings of their outcomes are equally likely.  In such cases we may therefore reconstruct event $(2)$ by starting with a fixed sequence of $k+1$ ones and $n-k$ zeros and then distributing the $X_i$ randomly within this sequence.  Any given $X_i$ thereby (obviously!) has a chance $(k+1)/(n+1)$ of landing on a $1.$ Consequently, the chance of $(2)$ is $\color{red}{f(k+1,n+1)}$ times $(k+1)/(n+1).$
$(1)$ and $(2)$ are mutually exclusive because you cannot simultaneously observe $k$ and $k+1$ ones.  Moreover, they are exhaustive because there is no other way $k$ or fewer of the first $n$ outcomes can happen.  Thus $F(k,n)$ must equal the sum of the chances of $(1)$ and $(2):$

$$F(k,n) = \color{blue}{F(k,n+1)} + \frac{k+1}{n+1} \color{red}{f(k+1,n+1)}.$$

The particular value $n=2k+1$ answers the question, showing that the "$1/2$" in its formula comes from $(k+1)/(2k+1+1) = 1/2.$
The analysis of case $(2)$ did not need to refer to the probability $p.$  This is why $p$ does not appear in the formula.
