0

I am given that $${n \choose a}={n \choose b}$$ I need to show that $n=a+b$ or $a=b$. Now I am left with $a!(n-a)!=b!(n-b)!$. I don't know what to do next. I checked there on google to solve the above, it says:- "On comparing, we get the required result." But it makes no sense to me.

xrfxlp
  • 1,505
Jatin Gakhar
  • 129

3 Answers3

1

Without any restrictions on $n,a,b$ the statement is wrong, for example $ \binom 23 = \binom 24 = 0$ or $\binom{-1}1 = \binom{-1}3 = -1$.

The correct statement is

Let $n, a, b$ be integers with $0 \le a \le n$ and $0 \le b \le n$. Then $$ \binom na = \binom nb \quad \implies \quad (a = b \text{ or } a+b=n) \, . $$

For a proof we fix the integer $n \ge 0$ and consider the function $$ f: \{ 0, \ldots , n \} \to \Bbb N \, , \quad f(k) = \binom nk \, . $$ We need the following two properties:

  1. $f(k) = f(n-k)$,
  2. $f(k)$ is strictly increasing for $0 \le k \le n/2$.

The first property should be clear. For (2) note that $$ \binom{n}{k+1} = \binom nk \frac{n-k}{k+1} = \binom nk \left(1 + \frac{n-2k-1}{k+1}\right)> \binom nk $$ if $k+1 \le n/2$.

Now assume that $0 \le a \le n$, $0 \le b \le n$, and $f(a) = f(b)$. Define $$ a' = \min (a, n-a) \\ b' = \min (b, n-b) \, . $$ Then $0 \le a' \le n/2$ and $0 \le b' \le n/2$, and $$ f(a') = f(a) = f(b) = f(b') $$ and from property (2) it follows that $a' = b'$, i.e. $$ \min (a, n-a) = \min (b, n-b) $$ and that is only possible if $a=b$ or $a+b=n$.

Martin R
  • 113,040
0

It is easy to show $a=b$ satisties the equation. Lets consider the case $a\ne b$. Then also we can easily show that $n=a+b$ satisties the equation. In order to show we have no more solution, we should consider also $n> a+b$ and $n< a+b$ cases. Without loss of generality, let $a> b$. Then in $n> a+b$ case $\binom{n}{a}>\binom{n}{b}$ (you can prove it with writing $n=a+b+k$ while $k>0$). Likewise in $n< a+b$ case $\binom{n}{a}<\binom{n}{b}$.

Taha Direk
  • 1,220
  • Please add how i could show C(n, a)>C(n, b), if n>a+b and similarly the other! – Jatin Gakhar Jul 10 '19 at 14:22
  • Please write the full steps as i was unable to figure out what to do after putting n=a+b+k – Jatin Gakhar Jul 10 '19 at 14:23
  • $$\binom{n}{a}=\dfrac{n!}{a!(n-a)!}=\dfrac{(a+b+k)!}{a!(b+k)!}=\dfrac{(a+b+k)!}{a!(b+k)...(b+1)b!}\ge\dfrac{(a+b+k)!}{a!(a+k)...(a+1)b!}=\dfrac{(a+b+k)!}{b!(a+k)!}=\dfrac{n!}{b!(n-b)!}=\binom{n}{b}$$ Now, you have all information to complete your proof and you should complete it yourself. – Taha Direk Jul 10 '19 at 16:22
  • Thanks sir. It helped me a lot! – Jatin Gakhar Jul 11 '19 at 09:54
  • Sorry sir, but i am again unable to write that! Please provide the whole proof! Maybe i am stuck because i couldn't get why we are just before showing that there is no more solution for 'n'. Why we aren't showing that there are no more relations between 'a' and 'b' which satisfy the given equation. – Jatin Gakhar Jul 11 '19 at 12:02
  • What if go this way-: $n!/a!(n-a)! =n!/b! (n-b)!$ Cas1. a!=b! & (n-a)!=(n-b)!, Which tells that a=b. Case2. (n-a)!=b! &a!=(n-b)!, Which tells that n=a+b. Case3. We may think that if a!>b! & (n-a)!<(n-b)! Or a!>(n-b)! & (n-a)!<b!, then the given statement holds correct. (Now, the help i need is that how i should make this wrong??) – Jatin Gakhar Jul 11 '19 at 12:05
  • Case $1$: $a=b$ satisfies the equation. Case $2$: $n=a+b$ satisfies the equation. Case $3$: When $n>a+b$, due to my comment above there is no $n$ to satisfy the equation. Case $4$: When $n<a+b$, due to similar solution with "Case $3$", there is no $n$ to satisfy the equation. That's it. – Taha Direk Jul 11 '19 at 19:59
  • From the given proof it is sure that there is no other value of n in terms of a and b or value of b in terms of n and a or value of a in terms n and b. How do we make sure that there is no value of a in terms of b or value of b in terms of a?? – Jatin Gakhar Jul 12 '19 at 01:51
  • When $a>b$ there is no solution. Also when $a<b$ there is no solution. The proof includes that. – Taha Direk Jul 12 '19 at 10:54
  • No, the proof isn't including this. – Jatin Gakhar Jul 12 '19 at 11:02
  • We won't show it something like:- let a>b, so a=b+k, k is non-zero. So, if we put a=b+k in the equation's one side, other side we get smaller or greater than the one side(as we did in case 3&4, as you mentioned in previous comment). – Jatin Gakhar Jul 12 '19 at 11:08
  • The proof includes that after the sentence which begins with "Without loss of generality" Also I proved it in comments. – Taha Direk Jul 12 '19 at 11:51
  • Yes, i saw you took a>b, but it doesn't mean that a=mb+z isn't possible, where m and z are some constants. We proved it nowhere that this isn't possible. – Jatin Gakhar Jul 12 '19 at 11:54
  • Of course $a>b$ includes $a=mb+z$ while $m,n>1$. You can be sure that the proof includes everything that are necessary. If you are not sure about that, try to understand what the proof inculdes. – Taha Direk Jul 12 '19 at 12:01
  • But make it clear that where we have shown that there is no more relation between a and b(except a=b), which satifies the equation. – Jatin Gakhar Jul 12 '19 at 12:51
0

It can be done purely combinatorial in nature. Define $n\choose k$ as the number of $k$-element subsets of an $n$-element set. This is the definition of the binomial coefficient that I use in my class on discrete math.

Then ${n\choose a} = {n\choose n-a}$ for each $0\leq a\leq n$. For this, consider the bijection $A\mapsto \{1,\ldots,n\}\setminus A$ which maps an $a$-element set $A$ to an $n-a$-element set.

Other identities are combinatorially not possible.

Wuestenfux
  • 20,964