Vrftsjtryk

Prove that if $displaystylebinom{n}{k}$ = $displaystylebinom{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.

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

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

Note that ${nchoose k} ={nchoose 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 ${nchoose k}={nchoose 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.

Remember that $displaystylebinom{n}{k}=frac{n!}{k! (n-k)!}$.

${nchoose k} = {nchoose 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 $0le k le n$ it is always true that:

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

That's always true.

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

For any $a ne b$ that ${nchoose a} = {nchoose 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).

${nchoose a} = {nchoose 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)..biff n-b =a iff a=n-b$.

....

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

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

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 xkfrac{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 xkfrac{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 $xne0,1,dots,k-1$, then $x=2k+1$, an odd integer.