0
$\begingroup$

Prove that if $\displaystyle\binom{n}{k}$ = $\displaystyle\binom{n}{k+1}$, then $n$ must be odd.

I am having problems with manipulating factorials and just can't seem to get the grasp on how to approach these types of problems.

$\endgroup$

closed as off-topic by GNUSupporter 8964民主女神 地下教會, Saad, Jyrki Lahtonen, Rebellos, Cesareo Dec 2 '18 at 13:43

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – GNUSupporter 8964民主女神 地下教會, Saad, Jyrki Lahtonen, Rebellos, Cesareo
If this question can be reworded to fit the rules in the help center, please edit the question.

4
$\begingroup$

$${n \choose k} = {n \choose k+1}$$

$$\frac{n!}{k!(n-k)!} = \frac{n!}{(k+1)!(n-(k+1))!}$$

$$\frac{n!}{k!(n-k)!} = \frac{n!}{(k+1)!(n-k-1)!}$$

$$k!(n-k)! = (k+1)!(n-k-1)!$$

Here, you have some important simplifications. Note that

$$(k+1)! = (k+1)k!$$

and

$$(n-k)! = (n-k)(n-k-1)!$$

so you get

$$k!(n-k)(n-k-1)! = (k+1)k!(n-k-1)!$$

$$n-k = k+1 \implies n = 2k+1$$

By definition, $2k+1$ is odd for all $k \in \mathbb{Z}$.

$\endgroup$
  • $\begingroup$ Thank you, this really helped! $\endgroup$ – Soulo Dec 2 '18 at 3:43
  • $\begingroup$ Glad to have helped! As a tip, always recall that for $a \neq b$, ${n \choose a} = {n \choose b} \iff a+b = n$. (The method of proving that is the same as the one here.) You can notice many patterns because of this, such as ${n \choose k} = {n \choose k+1} \implies n = 2k+1$. $\endgroup$ – KM101 Dec 2 '18 at 11:20
2
$\begingroup$

What I give below is not exactly a proof. But I hope it would give an understanding of what happens.

Note that ${n\choose k} ={n\choose n-k}$. For a fixed $n$, if we are interested in distinct values we should limit values of $k$ upto $n/2$.

Under this limit the binomial coefficient values steadily increase and reaching a maximum at $k= n/2$, if $n$ is even, and $k=(n-1)/2$ for odd $n$. And for $k>n/2$ the binomial coefficients repeat in the reverse order.

The condition ${n\choose k}={n\choose k+1}$ is possible only because $k+1$ crossed the halfway limit for distinctness. So $k+1= n-k$. This shows $n=2k+1$, hence it is odd.

$\endgroup$
  • $\begingroup$ Good method (+1). However, it is not necessary to discuss the halfway point. We can use the symmetry rule of binomial coefficients ${n\choose k}={n\choose n-k}$ and state ${n\choose n-k}={n\choose k+1}\Rightarrow n-k=k+1 \Rightarrow n=2k+1$, which is odd. $\endgroup$ – farruhota Dec 2 '18 at 4:43
  • $\begingroup$ @farruhota The symmetry rule is only enough if you also know that no other pairs of binomial coefficients with the same top index are equal, which requires some discussion of when the values increase and when they decrease. $\endgroup$ – Misha Lavrov Dec 2 '18 at 5:47
  • $\begingroup$ @MishaLavrov, do you mean ${n\choose k}={n\choose n-k}={n\choose m}$ could happen where $m\ne k$ and $m \ne n-k$? $\endgroup$ – farruhota Dec 2 '18 at 5:53
  • $\begingroup$ @farruhota Yes, or rather I mean that we need to rule out the possibility of it happening. $\endgroup$ – Misha Lavrov Dec 2 '18 at 5:54
  • $\begingroup$ @MichaLavrov, I don't think the above could happen, because ${n\choose k}\equiv {n\choose n-k}$. It happens if and only if $m=k$ or $m=n-k$. Again, no increase/decrease is required, but only the use of the combination formula. $\endgroup$ – farruhota Dec 2 '18 at 6:14
0
$\begingroup$

Remember that $\displaystyle\binom{n}{k}=\frac{n!}{k! (n-k)!}$.

$\endgroup$
0
$\begingroup$

${n\choose k} = {n\choose k+1} \implies$

$\frac {n!}{k!(n-k)!} = \frac {n!}{(k+1)!(n-k-1)!} \implies$

$\frac {n!}{k!(n-k-1)!(n-k-1)} = \frac {n!}{k!(k+1)(n-k-1)!}\implies$

$n-k -1 = k \implies$

$n = 2k +1$

A stronger result. Not just any odd; specifically $2k+1$.

....

Also notice: For all $0\le k \le n$ it is always true that:

${n \choose k} = \frac {n!}{k!(n-k)!} =\frac {n!}{(n-(n-k))!(n-k)!} = {n\choose n-k}$.

That's always true.

In the same way way as above we can prove that:

For any $a \ne b$ that ${n\choose a} = {n\choose b} \iff b = n-a \iff a=n-b$.

Pf: Wolog, assume $a < b$. (If $b < a$ we do the same thing but with the terms reversed).

${n\choose a} = {n\choose b} \iff$

$\frac {n!}{a!(n-a)!} = \frac{n!}{b!(n-b)!} \iff$

$a!(n-a)! = b!(n-b)! \iff$

$a!(n-b)!(n-b+1) ...(n-a) = a!(a+1)(a+2)..b(n-b)! \iff$

$(n-b+1) ...(n-a) = (a+1)(a+2)..b$.

If $n-b < a$ then $n-b + i < a + i$ for all $i$ and $(n-b+1) ...(n-a) < (a+1)(a+2)..b$ which is a contradiction.

If $n-b > a$ then $n-b + i > a+i$ and $(n-b+1) ...(n-a) > (a+1)(a+2)..b$ which is a contradiction.

So $(n-b+1) ...(n-a) = (a+1)(a+2)..b\iff n-b =a \iff a=n-b$.

....

So now we have a much stronger result with which we can show:

${n\choose k} = {n\choose k+1} \iff n-k = k+1 \iff n = 2k+1$.

$\endgroup$
  • $\begingroup$ You mean $\le$. I'm hoping I stated that enough times to make it clear. $\endgroup$ – fleablood Dec 2 '18 at 17:23
0
$\begingroup$

Let $k$ be a nonnegative integer. By definition, $$\binom xk=\frac{x(x-1)(x-2)\cdots(x-k+1)}{k!}\tag1$$ (note that $x$ does not have to be an integer) and so $$\binom x{k+1}=\frac{x(x-1)(x-2)\cdots(x-k+1)(x-k)}{(k+1)!}=\binom xk\frac{x-k}{k+1}.\tag2$$ The equation $$\binom xk=\binom x{k+1}\tag3$$ is a polynomial equation of degree $k+1$, so it has $k+1$ solutions. In view of $(2)$, we can rewrite $(3)$ as $$\binom xk=\binom xk\frac{x-k}{k+1}\tag4$$ which holds when $\binom xk=0$ or $\frac{x-k}{k+1}=1$, that is, the solutions are $$x=0,\ 1,\ \dots,\ k-1,\ 2k+1.\tag5$$ That is, if $\binom xk=\binom x{k+1}$, and if $x\ne0,1,\dots,k-1$, then $x=2k+1$, an odd integer.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.