Spivak's Calculus: Proofs concerning Pascal's Triangle

Question

Problem 3 of Chapter 2 in Spivak's Calculus poses 5 problems associated with Pascal's Triangle. The first of these asks you to prove that $\binom{n+1}{k}$ = $\binom{n}{k-1} + \binom{n}{k}$ which was fairly straightforward.

The second task was to prove by induction that $\binom{n}{k}$ is always a natural number. For this, I took the recursion approach: given the demonstration of the equality above, any $\binom{n}{k}$ can be decomposed into $\binom{n-1}{k-1} + \binom{n-1}{k}$ and so on, with each value decomposing until every binomial reaches either an $n$ or $k$ value of $0$, at which point they evaluate to 1 and can be summed. $1$ is a natural number, so the sum of any number of $1$s must therefore be a natural number. This proof seems to me as though it lacks formality, but I think the logic is appropriate.

The third task, however, I am simply unsure what to make of. It reads: "Give another proof that $\binom{n}{k}$ is a natural number by showing that $\binom{n}{k}$ is the number of sets of exactly $k$ integers each chosen from $1, \cdots,n$." The word induction is not used in the prompt, and I can see that this appears to be true across the first few rows of the triangle, but how one would rigorously prove something like this, I do not know. Additionally, having proven that this is true, is the link from that to $\binom{n}{k}$ always being a natural number just the fact that you cannot have partial or negative sets, and therefore it must be a natural number?

Answer 1

By definition ${n\choose k}=\frac{n!}{k!(n-k)!}=\frac{n\cdot (n-1)\cdot\ldots\cdot (n-k+1)}{k!}=\frac{n}{k}\cdot\frac{n-1}{k-1}\cdot\ldots\cdot\frac{n-k+1}{1}$.

Now consider $\{1,\ldots,n\}$. There are $n$ possibilities to pick an integer from this set. Let this integer be called $a_1$.

Now there are $n-1$ possibilities to pick an element from the set $\{1,\ldots,n\}\setminus \{a_1\}$.

By iterating this procedure we obtain $n\cdot (n-1)\cdot\ldots\cdot (n-k+1)$ possibilities to choose $(a_1,\ldots,a_k)$ from $\{1,\ldots,n\}$. Now note that we counted some possibilities multiple times, for example $a_1=1,a_2=2$ and $a_1=2,a_2=1$ result to the same integers chosen. So we have to divide by the number of possibilities to order $k$ elements which is $k!$ (there are $k$ possibilities to place the first integer, $k-1$ to place the second etc.).

Answer 2

Was writing out something along the lines of what's already so nicely explained by @Nightgap :), but just for good measure and I hope you don't mind that it's not really an answer to your specific question posed above, will still post what was going to be an addendum which has a different flavour and is nice to know if you haven't seen it (came across it in Alan Baker's Concise Intro to Number Theory aeons ago - great little book!).

So let $\lfloor x\rfloor$ be the largest integer $\leq x$. Let $p$ be a prime, then there $\lfloor n/p \rfloor$ elements of the set $\{1,2,...n\}$ divisible by $p$, $\lfloor n/p^2 \rfloor$ divisible by $p^2$, and so on. This means that the highest power $k$ of $p$ such that $p^k |n!$ is given by:$$k=\sum_{j=1}^{\infty}\lfloor n/p^j\rfloor \qquad \qquad (1)$$

Essentially you're adding to the sum each time you go up a prime power, so eg first you pick up all the unit powers with the term $\lfloor n/p \rfloor$, but then you need to add to these the extra contribution of the prime square multiples with the $\lfloor n/p^2 \rfloor$ term, then for the cubes, and so on. So now we have an explicit expression for the maximal power of a prime $p^k$ such that it divides $n!$

Now note that in general: $$\lfloor x+y \rfloor \geq \lfloor x\rfloor + \lfloor y \rfloor$$ (eg if the fractional parts of $x$ and $y$ add up to an integer), hence: $$ \lfloor n/p^j \rfloor \geq \lfloor (n-k)/p^j \rfloor + \lfloor k/p^j \rfloor \qquad \qquad (2)$$

But then: $$ {n \choose k}=\frac{n!}{k!(n-k)!}$$ ...must be a natural number since by (1) and (2) all the prime powers in the denominator will be 'absorbed' by those in the numerator. Hope that makes sense and again though not how you would answer your exercise I think is a nice perspective to have on binomial coefficients, in addition to the all important combinatorial one. Cheers.

Answer 3

For convenience, let $S_n = \{x_1, x_2, x_3, \dots, x_n\}$ represent a set of $n$ distinct objects.

Lets use $_nC_k$ to represent the number of ways of selecting $k$ objects from $S_n$.

So what does $_{n+1}C_k$ look like?

An element of such a selection will either include the object $x_{n+1}$ or it will not. We already know that there are $_nC_k$ ways to choose $k$ objects from the objects $x_1, x_2, \dots, x_n$. So how do we count the number of ways to select $k$ objects that contain $x_{n+1}$. Easy; we select $k-1$ objects from $S_n$ {there are $_nC_{k-1}$ such ways} and then add $x_{n+1}$ to the collection.

It follows that $_nC_{k-1} + _nC_k = _{n+1}C_k$.