Why is ${n \choose k} ≥ 1$?

Question

Why is

$${n \choose k} ≥ 1$$

I've looked at the expansion of the binomial coefficient, but can't see why the nominator is larger or equal to the denominator.

Answer 1

Technically, it's not true, since if $k>n$, the value of ${n\choose k}$ is $0$. However, I assume we are talking about the case when $k\leq n$, in which case the answer is:

Because $${n\choose k} = \frac{n\cdot (n-1)\cdots (n-k+1)}{k\cdot (k-1)\cdots 1}=\frac{n}{k}\frac{n-1}{k-1}\cdots \frac{n-k+1}{1}\geq 1\cdot 1\cdots 1=1$$

Answer 2

Using the definition of the binomial coefficient ${n\choose k}$ you can express it as a product of $k$ factors, each of which is greater than 1. $${n\choose k} = \frac{(n-k+1)(n-k+2)\cdots(n-k+(k-1))(n-k+k)}{1\cdot 2 \cdots (k-1)\cdot k} = \\ =\frac{n-k+1}{1} \cdot \frac{n-k+2}{2} \cdot \frac{n-k+3}{3} \cdots \frac{n-k+k}{k} = \\ = \left(1 + \frac{n-k}{1}\right)\cdot\left(1+\frac{n-k}{2}\right) \cdot \left(1 + \frac{n-k}{3}\right) \cdots \left(1 + \frac{n-k}{k}\right)\ .$$

Intuitively, the symbol ${n\choose k}$ denotes the number of subsets of size $k$ that you can create out of a set of $n$ elements. The inequality ${n\choose k}\geq 1$ says that you can create at least one subset, which you know to be true since the empty set $\varnothing$ is always a subset of any given set.

Answer 3

This inequality is a consequence of what to me is a more interesting property: for $n,k$ nonnegative integers with $0\le k\le n$, ${n\choose k}$ is always a positive integer. The combinatorial interpretation makes it clear that this must be so, but it wasn’t obvious to me from the formula.

To see this, compute ${n\choose k}$ by alternating multiplication and division. Multiplying two positive integers yields a positive integer, so we need only take a close look at the divisions involved. The first step, $\frac n1$, is obviously an integer. For the second step, we have $$\frac n1\frac{n-1}2.$$ One of the factors in the numerator must be even, so this is an integer. At the next step, we have $$\frac n1\frac{n-1}2\frac{n-2}3.$$ One of the three factors in the numerator must be divisible by $3$. At the next step, we have $$\frac n1\frac{n-1}2\frac{n-2}3\frac{n-3}4.$$ Things get a little interesting here. We’re guaranteed that one of the factors in the numerator is divisible by four, and there’s another even number available to absorb the $2$ that was already in the denominator, so this product is also an integer. Continuing in this way, it’s not too hard to convince yourself that each time you add another factor to the denominator, the numerator at that step will be divisible by it. Note that each of these intermediate products is itself a binomial coefficient, so for a formal proof an inductive argument suggests itself.

By the way, this argument shows that by alternating multiplications and divisions in this way, you can compute binomial coefficients using only integer arithmetic.

Answer 4

Another way is by using Legendre's theorem that factorizes $n!$ as the product over primes:

$n! =\prod_p p^{v_p(n)} $, where $v_p(n) =\sum_{j \ge 1} \lfloor \frac{n}{p^j} \rfloor $. The terms in the sum are zero when $p^j > n$.

From this,

$\begin{array}\\ \binom{n}{k} &=\frac{n!}{k!(n-k)!}\\ &=\frac{\prod_p p^{v_p(n)}}{\prod_p p^{v_p(k)}\prod_p p^{v_p(n-k)}}\\ &=\prod_p p^{v_p(n)-v_p(k)-v_p(n-k)}\\ \end{array} $

and $v_p(n)-v_p(k)-v_p(n-k) =\sum_{j \ge 1} \left(\lfloor \frac{n}{p^j} \rfloor-\lfloor \frac{k}{p^j} \rfloor-\lfloor \frac{n-k}{p^j} \rfloor \right) $.

Once we show that $\lfloor \frac{a}{c} \rfloor+\lfloor \frac{b}{c} \rfloor \le \lfloor \frac{a+b}{c} \rfloor $, this shows that all the exponents of each prime are non-negative, so that the result is an integer.

I will leave that to you.

There are many references to Legendre's theorem on the web. Here is one: http://www.cut-the-knot.org/blue/LegendresTheorem.shtml

Answer 5

This is probably not quite what you're looking for, but I this is a genuine answer to your question that I don't already see provided, so I thought it might be worth adding: the binomial coefficients satisfy a recursive relationship: \begin{eqnarray*} \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \quad \text{for all integers }n,k \text{ with } 1\le k\le n-1, \end{eqnarray*} where the initial/boundary conditions are $\binom{n}{0}=\binom{n}{n}=1$.

The above might look complicated, but it's really just the usual method of computing the entries of Pascal's triangle written in equation form.

Looking at it this way, the result is now obvious: the first three values are each $1$, and each subsequent term is a sum of two earlier terms, where the two earlier terms in question are, by induction, both greater than or equal to $1$.