We need to bound the binomial coefficients a lot of times. In this post, we will prove bounds on the coefficients of the form and where and is an integer.
Proposition 1. For positive integers such that ,
Proposition 2. For a positive integer and any such that and ,
where the binary entropy function is defined as follows:
Proposition 3. For a positive integer and any such that and ,
where is the binary entropy function.
Proof of Proposition 1
First, recall the power series . For , this sum is definitely larger than its th term only. In other words, , which implies . Now,
Proof of Proposition 2
Let us briefly recall Stirling’s approximation of .
Theorem (Stirling’s approximation). For any positive integer ,
Proof of Proposition 3
First, note that implies .
We remark that the last approximation is rather loose.