# Obtaining binomial coefficients without “counting subsets” argument

I want to obtain the formula for binomial coefficients in the following way: elementary ring theory shows that $(X+1)^n\in\mathbb Z[X]$ is a degree $n$ polynomial, for all $n\geq0$, so we can write

$$(X+1)^n=\sum_{k=0}^na_{n,k}X^k\,,\ \style{font-family:inherit;}{\text{with}}\ \ a_{n,k}\in\mathbb Z\,.$$

Using the fact that $(X+1)^n=(X+1)^{n-1}(X+1)$ for $n\geq1$ and the definition of product of polynomials, we obtain the following recurrence relation for all $n\geq1$:

$$a_{n,0}=a_{n,n}=1;\ a_{n,k}=a_{n-1,k}+a_{n-1,k-1}\,,\ \style{font-family:inherit;}{\text{for}}\ k=1,\dots,n-1\,.$$

I want to know if there is a way to manipulate this recurrence in order to obtain directly the values of the coefficients $a_{n,k}$, namely $a_{n,k}=\binom nk=\frac{n!}{k!(n-k)!}$.

Note that the usual approach via generating functions definitely will not work, at least in the spirit of my question, because this method only works when we do know in advance the coefficients of the generating function (either by the "number of $k$-subsets" argument, or Maclaurin series for $(X+1)^n$, or anything else) and this is precisely what I intend to avoid.

This question is closely related to a recent question of mine. Actually the same question, with Bernoulli numbers instead of binomial coefficients.

EDIT

I do not consider as a valid manipulation the following "magical" argument: 'the sequence $(b_{n,k})$ given by $b_{n,k}=\frac{n!}{k!(n-k)!}$ obeys the same recurrence and initial conditions as $(a_{n,k})$, so $a_{n,k}=b_{n,k}$ for all $n,k$. How did you obtain the formula for the $b_{n,k}$ at the first place? Okay, you can go through the "counting subsets" argument, but this is precisely what I don't want to do. The same applies to my related question about Bernoulli numbers.

-
One definition, the oldest, of the binomial coefficients is via the so called Pascal triangle (it was known in Cina many centuries before Pascal. Indeed it was known in Western Europe before Pascal.) The Pascal Triangle is given exactly by your recurrence. – André Nicolas Jul 24 '13 at 2:34
@AndréNicolas No, it does not, because you are already aware of the existence of the formula $n!/\cdots$. It is like to proving that $\sum_{k=1}^nk=n(n+1)/2$ by induction on $n$: how did you get the "candidate" formula $n(n+1)/2$? – Matemáticos Chibchas Jul 24 '13 at 2:42
The pattern also naturally appears when we differentiate $(1+x)^n$ several times to get the Maclaurin expansion of $(1+x)^n$. The $k!$ in the bottom is from Taylor;s Theorem, the $(n)\cdots(n-k+1)$ on top is from the differentiation. One can do formal differentiation if we wish to be totally algebraic. – André Nicolas Jul 24 '13 at 2:59
Most likely, the basic answer is "You can't." Some mountains have approaches that just aren't climbable. The counting argument you dismiss is a nice elementary argument. André Nicolas suggested a rather less elementary, but arguably more direct, approach. There may be others, but trying to manipulate the recurrence in some purely intuitive way does not seem likely to get you anywhere. – dfeuer Jul 24 '13 at 3:32
@dfeuer I am not dismissing the alternative solutions: I am not crank enough to reject such well-established methods. I am simply curious about the possibility of manipulating the recurrence in order to the answer "pop-out" – Matemáticos Chibchas Jul 24 '13 at 3:58

A simple-minded approach is to solve the two variable recurrence relation iteratively, that is, knowing $a_{n,0}$ find $a_{n,1}$, then $a_{n,2}$, etc.

We must have
$$\begin{eqnarray*} a_{n,1} &=& a_{n-1,1}+a_{n-1,0} \\ &=& a_{n-1,1}+1, \qquad a_{1,1}=1. \end{eqnarray*}$$ This is a one variable recurrence relation of the form $$b_n = b_{n-1}+1, \qquad b_1 = 1.$$ This can be solved by the usual methods. We find $a_{n,1} = n.$

Next we have $$\begin{eqnarray*} a_{n,2} &=& a_{n-1,2}+a_{n-1,1} \\ &=& a_{n-1,2}+n-1, \qquad a_{2,2}=1. \end{eqnarray*}$$ This is another simple recurrence relation. We find $a_{n,2} = n(n-1)/2.$

At the next step, $$\begin{eqnarray*} a_{n,3} &=& a_{n-1,3}+a_{n-1,2} \\ &=& a_{n-1,3} + \frac{1}{2}(n-1)(n-2), \qquad a_{3,3}=1. \end{eqnarray*}$$ This implies $a_{n,3} = n(n-1)(n-2)/6.$

This process can be repeated to build up $a_{n,k}$ for any $k$. At some point a pattern will be noticed and the principle of induction can be applied.

-
Simple as the answer may be, it is an elegant to me, and not one I've read in a textbook. It seems somewhat simpler to learn the same argument I read in textbooks, which relies on first defining a k-permutation, then a k-combination, before finally proving the binomial theorem. – NaN Jan 14 '14 at 8:22
@IDentity: Do you mean "inelegant"? If you read the question carefully you will find that the OP is not looking for an answer like the one you propose. – user26872 Jan 16 '14 at 15:07
I do mean elegant. I was saying that it seems simpler-minded to learn the argument I find in every other textbook which is $\large \binom{n}{k} = \frac{n!}{(n-k)!k!)}$. To quickly summarize the textbook argument, it is (1) define a k-permutation as $\frac{n!}{(n-k)!}$, (2) define a combination and argue that any k-combination is $\large \frac{1}{k!}\frac{n!}{(n-k!)}$. The relevance I see here is that the binomial coefficient is usually given as $\binom{n}{k}$ before proving the Binomial Theorem. It was not my intention propose any of this as an answer to the question. – NaN Jan 17 '14 at 11:23

If you define $a_{n,k}=\binom nk$ to be the coefficient of $X^k$ in $(1+X)^n$ (with no combinatorial meaning attached), then you easily find $\binom nk=\binom {n-1}{k-1}+\binom{n-1}k$ for all $n,k\geq1$ (as you indicated in the question). Also $\binom n0=1$ for all $n\geq0$, and $\binom0k=0$ for all $k>0$. Expanding the second term of the recurrence relation recursively, with $\binom0k=0$ as terminating clause, gives $$\binom n k=\sum_{0\leq i<n}\binom i{k-1} \qquad\text{for k\geq1 and all n\geq0.}$$ Now from the fact that $n\mapsto\binom n0$ is a polynomial function (of $n\in\mathbf N$) of degree$~0$ (namely the constant function$~1$) it follows easily by induction that $n\mapsto\binom nk$ is a polynomial function of degree$~k$ (summing a polynomial function of$~n$ increases the degree by$~1$). Moreover the first $k$ values $\binom ik$ for $0\leq i<k$ of the polynomial function are all$~0$, so the polynomial has roots $0,1,2,\ldots,k-1$. It therefore necessarily takes the form $\binom nk=c_k(n-0)(n-1)\ldots(n-(k-1))$ for some constant $c_k$. Using the recursion (at some point one does need to compute something) the first nonzero term $\binom kk$ of the sequence $n\mapsto\binom nk$ can be shown to be$~1$ for every$~k$, and it follows that $c_k=1/(k(k-1)(k-2)\ldots(k-(k-1))=\frac1{k!}$. Then $$\binom nk = \frac{n(n-1)\ldots(n-(k-1))}{k!},$$ which you may, if you feel so inclined, write as $\binom nk = \frac{n!}{k!(n-k)!}$ as long as $k\leq n$.

Look mom, no counting!

-
Thanks for your answer. – Matemáticos Chibchas Jul 27 '13 at 1:14
@MatemáticosChibchas: Indeed you are right, the first $k$ values of the polynomial function $n\mapsto\binom nk$ are $\mathbf{\binom ik}$ for $0\leq i<k$, and not $\binom ni$ as I wrote initially; thank you for the remark. I have corrected it now. – Marc van Leeuwen Jul 29 '13 at 5:52
Right; could I really have forgotten that subtraction is non-associative? Anyway corrected, and thanks again. – Marc van Leeuwen Jul 29 '13 at 6:01

I think Mathematica command for solving recurrence relation can be used:

RSolve[{a[n,k]==a[n-1,k]+a[n-1,k-1],a[n,0]==1,a[n,n]==1},a[n,k],{n,k}]

-