Show that ${n\choose k} = {n\choose l} \iff n=k+l$

Question

I was given the following problem:

Let $n,k,l \in \mathbb{N}$ such that $0\le l< k \le n $. Show that,

$${n\choose k} = {n\choose l} \iff n=k+l$$

I'm having trouble with the implication from left to right. I tried to prove it by contradiction assuming $n \neq k+l $ and using the inequalities that follows, but I got nowhere. I also tried to get to the right side directly, trying to show that $ {n\choose k+l}=1$ without results. Does anyone have a hint for this problem?

Thanks for reading.

Look at row $n$ of Pascal's triangle. It goes up, then it comes down. — Angina Seng, Jun 18 '20 at 19:40
You can try using the fact that $\binom nk $ is increasing function of $k $ for $k <n $, and decreasing for $k>n $. — user, Jun 18 '20 at 19:41
What do you know about binomials? Their formula using factorials? Their combinatorial description? As connecting coefficients? — Phicar, Jun 18 '20 at 19:42
@user: did you mean increasing for $k<\frac n2$ and decreasing for $k>\frac n2$? — J. W. Tanner, Jun 18 '20 at 19:47

user · Answer 1 · 2020-06-19T07:04:18.027

Observe that by definition $\binom nk ={ n! \over k! (n-k)!}$ is positive for $ 0\le k\le n $.

Further we have $$ \lambda_k={\binom n {k+1}\over \binom nk}={k! (n-k)!\over (k+1)! (n-k-1)!}={n-k\over k+1} \implies \lambda_k\begin {cases}\ge1,& 0\le k<\frac n2;\\ <1,&\frac n2\le k < n.\end {cases}. $$ $\lambda_k=1$ if and only if $n $ is odd and $k=\frac {n-1}2$. Thus $\binom nk $ as function of $k $ consists of two branches: increasing for $k <\frac n2$ and decreasing for $k>\frac n2$ and therefore can take on the same value for at most two values of $k $. And in most cases (except for $k=n-k $) there are exactly two such values, as you have already proved

score 0 · Answer 2 · answered Jun 18 '20 at 21:44

Consider:

Equivalent Lemma: If $0\le l,k \le \frac n2$ then ${n\choose l}= {n\choose k} \iff l=k$.

Immediate Corollary: If $0\le l,k \le n$ then ${n\choose l}={n\choose k} \iff k=l$ or $k+l = n$

========

Pf of Lemmma:

Wolog assume $l\le k$. $${n\choose k} ={n\choose l}\iff$$ $$\frac {n!}{k!(n-k)!} = \frac {n!}{l!(n-l)!}\iff$$ $$k!(n-k)! = l!(n-l)! \iff $$ but as $k \le \frac n2 \le n-k$ and $l\le \frac n2 \le n-l$ and as $k\ge l$ and $n-l \ge n-k$ $$l\frac {k!}{l!}\frac {(n-l)!}{(n-k)!}(n-k)! =l!(n-1)! \iff$$ $$\frac {k!}{l!}\frac {(n-l)!}{(n-k)!}=1\iff $$ but as $k\ge l$ so $k!\ge l!$ and $n-1 \ge n-k$ so $(n-l)! \ge (n-k)!$ $$k! = l!\text{ and }(n-k)!=(n-l)! \iff k = l$$

Pf of Corollary:

Given $0\le l,k \le n$ then one of these four cases must occur $$0\le l,k\le \frac n2 \le (n-k),(n-l)\le n$$ $$0\le l,(n-k)\le \frac n2 \le (n-l),k\le n$$ $$0\le k,(n-l)\le \frac n2 \le (n-k),l\le n$$ or $$0\le (n-k),(n-l)\le \frac n2\le l,k \le n$$ and as for all $m; 0\le m\le n$ we know ${n\choose m}=\frac {n!}{n!(n-m)!}=\frac {n!}{(n-m)!(n-(n-m))!} ={n \choose n-k}$ we know by the Lemma: $${n\choose k}={n\choose l}\iff$$ $k=l$ or $k=n-l$ or $l=n-k$ or $n-k=n-l\iff$ $$k=l\text{ or }k+l=n$$

The proof of Lemma is not clear. Namely the interchange of $(n-k)!$ and $(n-l)! $. — user, Jun 19 '20 at 06:24

Show that ${n\choose k} = {n\choose l} \iff n=k+l$

2 Answers2