Proof: Showing C(n,0) < C(n,1) <...<C(n, floor(n/2)) = C(n, ceiling(n/2))

[DrWillVKN]

Show that if n is a positive integer, then C(n,0) < C(n,1) <...<C(n, floor(n/2)) = C

Homework Statement

Show that if n is a positive integer, then C(n,0) < C(n,1) <...<C(n, floor(n/2)) = C(n, ceiling(n/2)) > ... > C(n, n)

Homework Equations

none

The Attempt at a Solution

Seems pretty direct, but I could be wrong. I suppose induction could work, too (or might be necessary).

The statement seems to imply that C(n, floor(n/2)) > C(n, k) for floor(n/2) > k >= 0 and C(n, ceiling(n/2)) > C(n, k) for ceiling(n/2) > k >= 0; n and k are positive integers. This can be stated because C(n, k) = C(n, n-k). P(n, k) = C(n, k)*k! by basic counting observation. Do these parts still need to be proven before they are shown to be equal? Does one need to use pascal's identity for this?

The trouble I have with the problem is with the flow of this proof. C(n, floor(n/2)) > C(n, k) for n>= k >= 0 because C(n, k) is greatest when k = n/2 for even, and k = (n+1)/2 = ceiling(n/2) and k = (n-1)/2 = floor(n/2) for odd, yet I don't know how I would go about stating this. It's too basic and intuitive.

Since C(n, k) = P(n, k)/k!, there are two cases to show:

1) When k is even, C(k, floor(k/2)) = k!/[(k/2)!(k/2)!], and C(k, ceiling(k/2)) = n!/[(k/2)!(k/2)!].
2) When k is odd, C(k, floor(k/2)) = k!/[(k-1/2)!(k+1/2)!] and C(k, ceiling(k/2)) = k!/[(k+1/2)!(k-1/2)!].

...

Thus, C(n, floor(n/2)) = C(n, ceiling(n/2)) > C(n, k) for n >=k >= 0 .

 

[Dick]

I would try to write down an expression for the ratio C(n,k+1)/C(n,k). If it's greater than one C(n,k+1)>C(n,k), if it's less than one C(n,k+1)<C(n,k).

 

[DrWillVKN]

So the ratio would fit everything on the left and right side in place, and then it comes together when k hits the floor and ceiling, and they're joined by equating them? I'm still confused about how to use the ratio (and for combinatorial proofs in general).

I have a hard time doing it by combinatorial proof, but by induction I have (for inductive step) the inductive hypothesis being the statement, adding the k + 1 term to the k term and showing pascal's identity, and then joining the left and right hand side by showing the ceiling and floor sets in the inductive step to be equal using algebra

 

[Dick]

So the ratio would fit everything on the left and right side in place, and then it comes together when k hits the floor and ceiling, and they're joined by equating them? I'm still confused about how to use the ratio (and for combinatorial proofs in general).

I have a hard time doing it by combinatorial proof, but by induction I have (for inductive step) the inductive hypothesis being the statement, adding the k + 1 term to the k term and showing pascal's identity, and then joining the left and right hand side by showing the ceiling and floor sets in the inductive step to be equal using algebra.

I don't think induction is the easy way to do it. Did you figure out a simple expression for C(n,k+1)/C(n,k)? Just looking at it might help you organize your thoughts.