Proving the Minimum Value of Combinations: Odd vs. Even n

[Crystal037]

Homework Statement

If n is an even natural number, then the greatest value of nCr is nCn/2 and if n is odd, then the greatest value of nCr is nC(n+1)/2 and nC(n-1)/2

Relevant Equations

nCr=n!/(n-r)!r!

I know nCn/2 = n!/((n/2)!)^2 = 2^(n/2)(1.3.5...n-1)
but I am not getting why it's the least one.

 

[Crystal037]

For 2n, n is a natural number,
2nCn = 2n!/n!n! = Highest value of nCr
Let r=k+n for a natural number,k
2nCn = 2nCr.(n+1)(n+2)...(n+k)/n(n-1)...(n-k)
Eg, when 2n=12, n=6
highest value of 12Cr should be 12C6
12C6 = 12*11*10*9*8*7*6*5*4*3*2*1/(6*5*4*3*2*1)(6*5*4*3*2*1) =12*11*10*9*8*7/(6*5*4*3*2*1)
for any other value of r let r=9, then 9=k+6 which implies k=3
12C9=12*11*10*9*8*7*6*5*4*3*2*1/(9*8*7*6*5*4*3*2*1)(3*2*1) =12*11*10/(*3*2*1)
which is less than 12C6 by a factor of (9*8*7)/(6*5*4) = (6+1)(6+2)(6+3)/6(6-1)(6-2)
If n=2m+1, m is any natual number i.e. n is an odd no.,
nC(n+1)/2, nC(n-1)/2 =Highest value of nCr
nC(n+1)/2=nCr.((n+1)/2+1)((n+1)/2+2)...((n+1)/2+k)/((n-1)/2)((n-1)/2-1)...((n-1)/2-k)
Eg for n=11 highest value of 11Cr should be 11C6
since, n=11, (n+1)/2=6, (n-1)/2=5
11*10*9*8*7*6*5*4*3*2*1/(6*5*4*3*2*1)(5*4*3*2*1)=11*10*9*8*7/5*4*3*2*1
for any other value of r let r=9, then 9=k+6 which implies k=3
11C9=11*10*9*8*7*6*5*4*3*2*1/(9*8*7*6*5*4*3*2*1)(2*1)
which is less that 11C6 by a factor of 9*8*7/5*4*3=(6+1)(6+2)(6+3)/(6-1)(6-2)(6-3)

 

[PeroK]

If you are trying to prove this, you could look at the general pattern that binomial coefficients, for a given $n$, get larger until they reach a peak and then get smaller. You could think about why they get larger then smaller.

 

[WWGD]

Maybe you can look at Pascal's triangle and the recursion rule. Notice each row's entries are symmetric so you don't need to consider all the entries.

 

[Crystal037]

I can't understand how to use recursion rule to say if a term is the highest

 

[PeroK]

I can't understand how to use recursion rule to say if a term is the highest

Why not look at $\binom{n}{k+1} / \binom{n}{k}$?

 

[Crystal037]

the answer would be k/(n-k+1), then how to proceed

 

[WWGD]

I can't understand how to use recursion rule to say if a term is the highest

Write down first few , 2-3 lines explicitly and the mid terms are the largest. For the general nth row, the midterm will be the sum of the two largest in the previous row. Take,e.g., the 3rd and 4th row: 1,3,3,1 and 1 , 4, 6, 4, 1. The 6 in the 4th row is the sum of 3,3 , both largest terms , so it must be larger than all other terms in the row.

 

[Crystal037]

Oh yes, the middle terms are always greater than the other terms because they are the sum of the largest terms from the previous row. Thanks.
And the formula I wrote in #2 is that correct.

 

[WWGD]

Oh yes, the middle terms are always greater than the other terms because they are the sum of the largest terms from the previous row. Thanks.
And the formula I wrote in #2 is that correct.

Yes, though the two are separate arguments.

 

[PeroK]

the answer would be k/(n-k+1), then how to proceed

That's not right. E.g. try $k =0$.

The idea is that $a > b$ if and only if $a/b > 1$, assuming $a, b$ are positive. Really, you have to be able to think of something like this for yourself.

You need to decide whether to concetrate on this approach or the approach based on Pascal's triangle. I would say, however, that if you use Pascal's triangle, then you have be careful to prove everything that you are seeing from the triangle.

For example, it's been quoted that the triangle is symmetrical. But, you can't use the symmetry of the triangle unless you prove it. In fact, it's part of the symmetry of the triangle that you are trying to prove in this problem.

 

[WWGD]

That's not right. E.g. try $k =0$.

The idea is that $a > b$ if and only if $a/b > 1$, assuming $a, b$ are positive. Really, you have to be able to think of something like this for yourself.

You need to decide whether to concetrate on this approach or the approach based on Pascal's triangle. I would say, however, that if you use Pascal's triangle, then you have be careful to prove everything that you are seeing from the triangle.

For example, it's been quoted that the triangle is symmetrical. But, you can't use the symmetry of the triangle unless you prove it. In fact, it's part of the symmetry of the triangle that you are trying to prove in this problem.

Good point, my argument does assume that symmetry. Op should prove nCk=nC(n-k).

 

[Crystal037]

That's not right. E.g. try $k =0$.

The idea is that $a > b$ if and only if $a/b > 1$, assuming $a, b$ are positive. Really, you have to be able to think of something like this for yourself.

You need to decide whether to concetrate on this approach or the approach based on Pascal's triangle. I would say, however, that if you use Pascal's triangle, then you have be careful to prove everything that you are seeing from the triangle.

For example, it's been quoted that the triangle is symmetrical. But, you can't use the symmetry of the triangle unless you prove it. In fact, it's part of the symmetry of the triangle that you are trying to prove in this problem.

Oh sorry
The answer should be (n-k)/(k+1)

 

[Crystal037]

Good point, my argument does assume that symmetry. Op should prove nCk=nC(n-k).

How proving nCk=nC(n-k) would help in proving the symmetry

 

[PeroK]

How proving nCk=nC(n-k) would help in proving the symmetry

That is the symmetry!

 

[PeroK]

Oh sorry
The answer should be (n-k)/(k+1)

That tells you when the coefficients are increasing.

 

[WWGD]

Because this shows that the kth term in a row equals the (n-k) th term. But for induction you can just try to show that if you have the highest term in the middle in the jth row you will also have it in the (j+1)st row by adding the two central terms.

 

[Crystal037]

So using the pascal triangle we found what the highest value of nCr is.

 

[PeroK]

So using the pascal triangle we found what the highest value of nCr is.

The triangle you're looking at is only finite. How do you know the pattern continues?

 

[Crystal037]

By using mathematical induction, can't I prove it?

 

[WWGD]

We haven't done anything yet Chrystal, this was just an idea and it needs to be fleshed out. I think @PeroK. 's idea seems closer to a solution. You may, of course, work both out.

 

[PeroK]

By using mathematical induction, can't I prove it?

Yes, but an inductive proof looks like it might get messy to me.

 

[Crystal037]

Using Pascal triangle ,
we know that the middle terms are greater, since they are found by adding the above middle terms which are greater & this leads us to the 2nd index where the greater term started as 2 which was due to the fact that we added the only 2 numbers in the 1st index 1 &1, which came from 0th index i.e.1

 

[PeroK]

That's far from a rigorous mathematical proof. The result can be seen informally by looking at the triangle. But, you need to put together a formal inductive proof.

 

[Crystal037]

What do you mean by formal inductive proof? Give me some hint on how to begin with

 

[WWGD]

I would say something like : assume the central terms are the largest for 1 through k-1 in their respective rows . Then show if the central term of the kth row is the largest, as the sum of largest terms in previous rows, then the central term of the (k+1)st row must be the largest, as the sum of the two largest in the k-th row.

 

[PeroK]

I would say something like : assume the central terms are the largest for 1 through k-1 . Then show if the central term of the kth row is the largest, as the sum of largest terms in previous rows, then the central term of the (k+1)st row must be the largest, as the sum of the two largest in the k-th row.

Although, what it to be proved is different for odd and even $n$.

 

[WWGD]

Although, what it to be proved is different for odd and even $n$.

Yes, good idea.