- #1

- 7

- 0

## Main Question or Discussion Point

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

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