Recursive equation

[Genady]

While playing in my mind with a question from another thread, the one about n choose k calculation, it occurred to me that it could be solved via a following recursive equation (regardless of the standard derivation of the well known formula for n choose k).

If we select any one element out of n, all groups of k are of two types: the ones that include the selected element and the ones that don't. There are C(n-1,k-1) choices for the former and C(n-1,k) for the latter. Thus, we get this recursive equation: C(n,k)=C(n-1,k-1)+C(n-1,k).

There are two variables there, so perhaps we need two boundary conditions. These could be, e.g., C(n,1)=n and C(k,k)=1.

It is easy to check that C(n,k)=n!/(k!(n-k)!) solves this equation. My question is, is there a way to derive this solution from the equation? I never worked with recursive equations. Maybe there is a way to convert it to a differential equation? Or, to massage it until the solution gets self-evident?

[Genady]

Applying the recursive equation to its right side, we get:

(n,k)=(n-1,k-1)+(n-1,k)

=(n-2,k-2)+2(n-2,k-1)+(n-2,k)

=(n-3,k-3)+3(n-3,k-2)+3(n-3,k-1)+(n-3,k)=...

We get binomial coefficients:

=(3,3)(n-3,k-3)+(3,2)(n-3,k-2)+(3,1)(n-3,k-1)+(3,0)(n-3,k)=...

Interesting turn, although I don't see it helping to derive a solution for the equation. Yet.

Continuing this substitution all the way, the final line will be:

(n,k)=(k,k)(n-k,0)+(k,k-1)(n-k,1)+(k,k-2)(n-k,2)+...+(k,0)(n-k,k)

[joigus]

12 hours ago, Genady said:

Thus, we get this recursive equation: C(n,k)=C(n-1,k-1)+C(n-1,k).

Yes, you're on the right track, as this is a well-known property of combinatoric numbers.

What you call "boundary conditions" are actually the pillars of what looks like calling for an induction proof. Induction on n and on k separately perhaps?

A differential equation or similar would only apply for very big n, very big k, and very big n-k, so I don't think it would work. Approaching factorials by continuous variables is done when deriving the Stirling approximation, for example.

[Genady]

6 hours ago, joigus said:

... what looks like calling for an induction proof.

If we have the ansatz, (n,k)=n!/k!/(n-k)!, then we don't need an induction proof as it satisfies the equation directly:

(n-1,k-1) + (n-1,k) = (n-1)!/(k-1)!/(n-k)! + (n-1)!/k!/(n-k-1)! = (n-1)!*k/k!/(n-k)! + (n-1)!*(n-k)/k!/(n-k)! = n!/k!/(n-k)! = (n,k)

[joigus]

And what about uniqueness?

[Genady]

42 minutes ago, joigus said:

And what about uniqueness?

For any given k, the equation uniquely determines (n,k) based on (n-1,k) and (n-1, k-1). That is, (n,k) is uniquely determined for any n by (k,k) and (k,k-1) by using the equation stepwise from n=k to n=n with the constant k.

(k,k)=1 and (k,k-1)=k are the boundary conditions. If they are satisfied by a formula, than this formula is a unique solution for any n for a given k. Since the given k is arbitrary, it is unique for all n and all k.

[Genady]

Here is a little Excel "experiment" to test uniqueness.

n goes vertically, k goes horizontally. Column A corresponds to (n,1) and is populated by hand with n. This is one boundary condition. Cells on the diagonal correspond to n=k and are populated by hand with 1. This is another boundary condition. All the red cells are populated with the recursive equation, (n,k)=(n-1,k)+(n-1,k-1). They are automatically and uniquely populated by Excel.

[joigus]

I think it's interesting to think about problems in original ways. I'd never seen a combinatorics problem thought in terms of solving a hierarchy of equations with boundary conditions.

Your solution is, of course, correct, AFAICS. By "boundary conditions," also, I understand what you mean.

I'm somehow lingering on your suggestion of treating factorials as continuous. The continuous version of a factorial is a gamma function. The C(n,k) combinatoric number reminds me a lot of the (inverse of) the beta function that appears in particle physics. I wonder if there's something to that idea... Maybe some other day.

I come from physics. In physics you always try to do the calculation in the simplest possible way.  

Reshuffle all you can and eliminate the redundancy, to me, is the simplest way to do combinatorics; mark, and then un-mark, if you know what I mean (as I said in the other thread.)