Can the Binomial Theorem be derived without prior knowledge of the formula?

[Tarty]

Hi,
I am trying to understand the binomial theorem, and would appreciate any insight or pointers.

To make notation simpler I'll call the binomial coefficient f(n,k).
I understand the combinatorial argument that f(n,k) = f(n-1, k-1) + f(n-1, k). This is, to my understanding, a two dimensional (linear?) recurrence.

I know that there exists a formula for it using factorials - f(n,k) = n!/(k!(n-k)!) - and that one can prove inductively that this formula satisfies the recurrence.

My question is, without knowing the formula, how would one go about deriving it? We just recently learned (in my Linear Algebra class) how to solve one-dimensional linear recurrences like the Fibonacci sequence, and I'm wondering whether a similar procedure exists for the binomial theorem, or for two-dimensional recurrences generally.

Even if there's no way to solve it, maybe there's a combinatorial argument justifying the factorial formula? Or is it just a formula that someone came up with by intelligent guesswork and retrospectively justified?

Thanks in advance!
- Tarty

 

[micromass]

It is quite easy to see with a combinatorial argument. Let's say that we have 5 objects and we wish to choose 3 objects from the 5.

1) Order matters
That is: let's first assume that (5,2,3) is different from (2,3,5) and (3,5,2) and etc.

How many choices can we make like this?? Well, we wish to choose three elements (a,b,c) who are all different.

To choose a, we have 5 choice. To choose b we have 4 choices (indeed, we cannot choose a since all values must be different). To choose c we have 3 choices. So together we have 5*4*3 choices.

In general: if we wish to choose m objects from n, then we can do this in

n*(n-1)*(n-2)*...*(n-m+1)

So just make sure that we have m terms in the above product. We can write this concisely as

\frac{n!}{(n-m)!}

2) Order doesn't matter
Let's say that (3,2,5) is the same thing as (5,2,3) and others.

So in the above, we have deduced 5*4*3 possible ways to choose 3 objects from 5. But we have some redundancy. Indeed, if we have (a,b,c) then we don't need (b,a,c) and (c,a,b) and others. So we need to find out how in how many ways we can order (a,b,c). This corresponds with "choose 3 elements from 3 where the order matters". We have seen that this is 3*2*1. Indeed, we have 6 ways to order 3*2*1:

(a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a)

So in order to choose 3 elements from 5, we have \frac{5*4*3}{3*2*1}=10 choices. Indeed:

(1,2,3), (1,2,4), (1,2,5), (1,3,4),(1,3,5), (1,4,5),(2,3,4),(2,3,5),(2,4,5),(3,4,5)

So we do have the correct formula.

When we need to choose m elements from n. Then we can choose this in \frac{n!}{(n-m)!} ways. But we need to divide out the number of orderings from m. So the formula becomes

\frac{n!}{(n-m)!m!}

 

[Tarty]

That makes perfect sense! Thank you for a very thorough explanation.

 

[Stephen Tashi]

We just recently learned (in my Linear Algebra class) how to solve one-dimensional linear recurrences like the Fibonacci sequence, and I'm wondering whether a similar procedure exists for the binomial theorem, or for two-dimensional recurrences generally.

This is good question and you shouldn't drop it because you got a good answer to a different question! I'd like to hear the answer, myself.


------------------

In thinking about an answer to another thead ( which asked for a formula for the sum of the first m binomial coefficients) it occurred to me that a simple generalization of Pascal Triangle is:

Generalized Pascal's Triangle

_____________________________a[0]

________________________a[0]______a[1]

__________________a[0]_____a[0]+a[1]_______a[2]

_____________a[[0]____2a[0]+a[1]__a[0]+a[1]+a[2]____a[3]

______a[0]_____3a[0]+a[1]___3a[0]+2a[1]+a[2]___a[0]+a[1]+a[2]+a[3]____a[4]

...

Where the a are an arbitrary sequence of numbers. (If you set a[0] = 1 and a[n] = 2^n, the m-th entry in a row of the triangle is the sumsof the first m binomial coefficients in the corresponding row of an ordinary Pascals' Triangle.)

The coefficients of a given a[k] in the entries of this triangle involve binomial coefficients. (For example, in the last row of the example, the coefficients of a[1] in the middle 3 entries are (1,2,1).


The entries in the triangle satisfy the recursion f(n,k) = f(n-1, k-1) + f(n-1, k) for a restricted range of indices. Call the diagonal of a[0]'s in the triangle, the 0-th column
and call the top entry the 0-th row. (So, for example, the f(3,2) entry is a[0]+a[1]+a[2].)
Then the recursion is satisfied for the (n,k) which define binomial coefficients.

This triangle shows there are solutions to the recursion other than the binomial coefficients. Yet he binomial coefficients appear "embedded", as it were, in the general triangle. It would be interesting to know if the theory of recursions in two variables describes phenomena like this in some precise way.

 

[Tarty]

I'm not sure what you mean by 'embedded', Stephen.

Your way of looking at the problem suggests that a two-parameter problem like that cannot be solved.

With linear recurrences you have a certain number of initial 'seed values' (like 0, 1 with Fibonacci). You can represent the seed value as a vector and the recurrence as a matrix, and solve the recurrence by analyzing the matrix.

But with this two-parameter problem you have infinite seed values (a[0], a[1], a[2] ...). The general solution would have to account for any possible sequence of numbers, so it's very unlikely that anything approaching a closed form could be derived.

The same seems to be true of all two-parameter recurrences :/

 

[Stephen Tashi]

I'm not sure what you mean by 'embedded', Stephen.

Write out a few more lines of the generalized Pascal's Triangle and look at the pattern of the coefficients for term like a[1] in the various entries. Those numbers form an ordinary Pascal's Triangle.

Your way of looking at the problem suggests that a two-parameter problem like that cannot be solved.

On the contrary, it shows there are an infinite number of solutions. To get the binomial coefficients, you want f(n,n) = a[n] = 1.

it's very unlikely that anything approaching a closed form could be derived.

You have to define "closed form". The entries in the generalized Pascal's Triangle can be expressed in a concise way. Each is a linear combinaion of the a and the coefficients are various binomial coefficients.

The same seems to be true of all two-parameter recurrences /

I think you are trying to express a thought about how many "boundary values" we need to solve such recurrences. The need for boundary values doesn't invalidate a solution.

 

[Tarty]

Yes, sorry, I meant that there was no general solution. By closed form I meant a formula for f(n, k) that does not rely on recursion.

Neither statement though, as you rightly point out, is actually true.

It does seem that based on your generalized Pascal's triangle, one can find the closed form in terms of the sequence {a[n]} and the binomial coefficients.

Then I suppose the next question (after actually deriving this closed form) is - can this process be generalized to any two-parameter linear recurrence?