Prerequisites:
Binomial coefficients are important for studying prime numbers, as we’ll see in the post The product of the first prime numbers. Let’s see in detail some of their properties, that will be useful for our purposes. In particular, these properties are estimates: two underestimations and one overestimation. The reason why we are looking for some estimates for binomials is that their definition reveals particularly hard to manipulate both in calculations and in analytical arguments: therefore it’s often preferable to use an estimate, affected by error but easier to use, rather than the exact value.
The first two estimates are easily obtained recalling the link between binomial coefficients and the so called Pascal’s triangle:
This triangle has many interesting properties, well known in scholastic math. Those we are most interested in, are the following:
- Numbering rows starting from 0, the sum of the numbers on row number n is 2^n
- Every row is symmetric: it remains unchanged reading from right to left or from left to right
- Every number different from 1 is the sum of the two numbers immediately above
- Numbering also the numbers in each row starting from 0, from left to right, the number in position m on row number n, with n > 0, is the binomial \binom{n}{m}
The last property, in particular, indicates the connection between the Pascal’s Triangle and the binomial coefficients. In fact, by virtue of this property, the triangle can be rewritten as follows:
Hence the properties of the triangle immediately reflect to just as many properties of binomial coefficients. For example, considering the sixth row, that is row number 5 starting from 0, the first property states that:
that is the sum of the numbers of a row is 2 powered to the row number.
This property, “translated” into binomial coefficients, becomes
But what is not evident in this second formulation, but it is in (1), is that binomial coefficients appearing in symmetrical places are equal (by the second property): in fact, comparing (1) with (2), we have that:
This simple fact is the basis for the first estimate. In fact, if every binomial is repeated twice in a row, twice the amount (that is the sum of the two repetitions) certainly is less than or equal to the sum of the row itself, in this case 2^5. For example:
So 2 \cdot \binom{5}{1} \leq 2^5, that is \binom{5}{1} \leq 2^4, which is exactly the first estimate (though the proof should be completed, because numbers are not always repeated in a row: in rows with an odd number of elements there is a central element which is not repeated):
Overestimation of binomials
For all n > 0 and for all m:
It’s not necessary to specify that 0 \leq m \leq n, as it could not be otherwise, because the binomial \binom{n}{m} is not defined for other values of m.
Let’s start from (1), where we have three distinct numbers, 1, 5 e 10, each repeated twice. Repetitions are due to the second property, the one about symmetry: the repeated numbers in fact are placed in opposite positions, with respect to an imaginary center of the row. Grouping these repeated numbers, from (1) we can obtain an unequality for each of them:
At this point we would be tempted to say that the double of a number in row number n is less than or equal to the sum of the row, i.e. 2^n. However we cannot make this generalization right away. In fact in the example above every number of the row is repeated twice, but, observing the Pascal’s triangle, you can see that not all numbers are repeated, so we have to consider these cases too. In particular, the rows with an odd number of elements, that are rows number n for an even n, have a central element which is not repeated. An example is row number 4:
In this case we can repeat the reasoning above for the numbers 1 and 4:
However we have to understand how to prove that 2 \cdot 6 \leq 2^4, with an argument which can be generalized to all central numbers of rows with an odd number of elements. To do this, we have to get into the game the third property of Pascal’s triangle, one of the most known, stating that every number different from 1 is the sum of the two numbers immediately above it. In this case 6 is the sum of 3 + 3, that are the two numbers above:
But 3 + 3 is in turn less than or equal to the sum of the numbers of its row, so:
Multiplying by two, we have that
which is exactly the kind of relation we wanted to obtain, equivalent to (4) and (5). In this case n = 4 but the argument can be extended to the central number of row n for any even n greater than 0. This argument does not apply to row number 0 because there is not a previous row which it connects to, and indeed for this row the property is not true (the central number, 1, is also the unique number of its row and so it is equal to the row sum too; doubling it, a greater number is obtained). However we have not to care about this case, because row 0 is not important for our purposes, being binomials defined for n > 0.
Summarizing, we have proved, on the basis of the first three properties, that two times any number of a row n of the Pascal’s triangle, with n > 0, is less than or equal to 2^n, that is the sum of the row elements. But we know, from the last property of the Pascal’s triangle, that these elements are the binomials of the kind \binom{n}{m}, with m between 0 and n. So we proved that, for any n > 0 and any m,
from which we obtain Property N.1.
We can note that, if n is fixed, the estimate (3) is the more accurate, the more \binom{n}{m} is big, compared to the other numbers of row n (in fact we should remember that the right side of (3) is half the sum of the numbers of row n). As you can see in the Pascal’s triangle, the numbers of a row become bigger towards the center, so the biggest binomials \binom{n}{m}, where n is fixed, are those where m is closer to \frac{n}{2}. In particular, if n is even, the biggest binomial is \binom{n}{\frac{n}{2}}, like 6 = \binom{4}{2} in row 4; if n is odd, the biggest binomials, equal to each other, are \binom{n}{\left \lceil \frac{n}{2} \right \rceil} and \binom{n}{\left \lfloor \frac{n}{2} \right \rfloor}, like 10 = \binom{5}{2} = \binom{5}{3} in row 5. So the most accurate estimates are:
for even n, and
for odd n. We will need right these estimates for studying prime numbers, in the post The product of the first prime numbers.
Starting from the fact that the binomials of formulas (6) and (7) are the biggest of their rows, with similar techniques as before a second estimates can be obtained, this time an underestimation:
Underestimation of the central binomials of the Pascal’s triangle
For all n \geq 2:
if n is even, and
if n is odd.
Let’s start with a specific case. Considering that the binomial \binom{6}{3} is the biggest in the seventh row, we can use it for majorizing each row element, obtaining:
These passages can be easily generalized to a generic n, obtaining
for even n, and
for odd n.
We can slightly improve this estimate observing that, starting from row 2 of the Pascal’s triangle, the biggest binomial of its row is greater than or equal to 2, and this lets us to save a majorization by unifying the two 1s, for example:
Generalizing for a generic n, we obtain Property N.2.
We can note that this estimate holds only for the central binomials of the rows of Pascal’s triangle, differently from the previous property, which holded for all binomials. Property N.2 is one of the elements which are necessary for the proof of the Bertrand’s postulate.
In the picture below you can see that the estimate given by Property N.2 is rather good, at least for the first values of n: the binomials, compared with the expression \frac{2^n}{n} don’t have much greater values.
Again with the aim of minorizing the binomials with functions as simple as possible, in the case of even n we can obtain an unequality similar to (8) but even simpler, starting from the definition of binomial instead of the Pascal’s triangle. Let’s take as an example the case of n = 10. By the definition of binomial we have that:
We can rewrite the last fraction as
We can note that the last term is 2, while the others are all greater than 2 (in fact the sequence of the terms is strictly decreasing, because the numerators decrease and simultaneously the denominators increase), therefore
Summarizing, we have that
This relation can be easily generalized for any even n, obtaining that \binom{n}{\frac{n}{2}} \geq 2^{\frac{n}{2}} = \sqrt{2^{n}}:
Underestimation of the central binomial of Pascal’s triangle, even n
For all even n \geq 2: