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

Question

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.

Answer 1

$${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}$.

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

${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$.