Spivak's Calculus: Proofs concerning Pascal's Triangle

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?

• I think the exercise want you to prove that $c(n,k)$ the number of sets of exactly $k$ integers chosen among $n$ follows the same induction formula, i.e. $c(n,k)=c(n-1,k-1)+c(n-1,k)$ and since you already noticed it takes the same values in the first rows of the triangle then you deduce $c(n,k)=\binom{n}{k}$. – zwim Jun 6 '18 at 22:49

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.).

• Very helpful, thank you. Is there some any special study I should undertake to develop the ability to notice this, or does it fall under the general heading of 'mathematical maturity' which one acquires through sheer experience? – user242007 Jun 6 '18 at 23:11
• Well I think the best way to solve these kind of problems is to first work out the combinatorical side (here the number of possibilities to choose $k$ elements from $\{1,\ldots,n\}$) and then try to rearrange the left side to find this number. – Nightgap Jun 6 '18 at 23:26
• To the proposer: The topic of this Answer is Finite Combinatorics. There is a nice book called Finite Mathematics by Kemeny, Snell, & Thompson with many different topics (including combinatorics) utilizing a variety of techniques. Example: An election with 2 candidates A & B..... "A" won by $m$ votes to $n.$ When the ballots are counted, one at a time, what are the odds that A is always ahead during the count? – DanielWainfleet Jun 7 '18 at 0:35

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.

• An interesting alternative look at the problem. It's going to take some time to digest this, but I greatly appreciate you taking the time to offer another angle. – user242007 Jun 7 '18 at 0:18
• No problem! Like I say you can find it in A Concise Introduction to Number Theory by Alan Baker, well worth checking out if you have the time, but for me the above was a pretty powerful aid to understanding the structure of binomial coefficients from a number theoretic perspective. – Mehness Jun 7 '18 at 0:20
• Just to add the above proof also immediately shows that multinomial coefficients $\frac{n!}{k_1! \cdot k_2! \cdots k_r!}$ where $\sum_{i=1}^r k_i = n$ are also natural numbers – Mehness Jun 7 '18 at 10:31

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$.