# Proving that ${n}\choose{k}$ $=$ ${n}\choose{n-k}$

Let $${n}\choose{k}$$ denote the binomial coefficient,

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

where $$n,k$$ are integers $$\geq0,0\leq k\leq n$$, and $$0!$$ is defined to be $$1$$. Prove the following assertion:

$${n\choose k}={n\choose n-k}$$

I proceded by making the adequate substitutions:

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

And then I simplified and achieved:

$$\frac{n!}{(n-k)!-k!}$$

But I'm not sure on how to proceed from here, I've noticed that this result is very similar to $$\frac{n!}{k!(n-k)!}$$. What should I do? I guess it has something to do with the statement about the nature of $$n$$ and $$k$$:

$$n,k$$ are integers $$\geq0,0\leq k\leq n$$

So should I just change the minus sign to plus sign and think of it as a product of $$(n-k)!$$?

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

I'm in doubt because I've obtained the third result on Mathematica, but obtained the first with paper and pencil. I'm not sure if there are different rules for simplification with factorials. I'm not sure if this $$(n-k)!+k!$$ mean a sum or a product in this case.

You simply failed to distribute the negative sign (i.e., multiplying the difference by $-1$: \begin{align} n - (n - k) &= n + -1(n -k) \\ \\& = n + - 1\cdot n - (-1)\cdot k \\ \\ & = n - n + k \\ \\ &= k\end{align}

(I.e., Negation distributes over sums and differences.)

$${n\choose n-k}=\frac{n!}{\color{red}{(n-k)}!(n-\color{red}{(n-k)})!} =\frac{n!}{(n-k)!(n - n + k))!} =\frac{n!}{(n-k)!(k)!}= \frac{n!}{k!(n-k)!}$$

• + 1 for the nice color coding! May 29, 2013 at 0:36

The proof you've suggested, and the other answers have corrected, is the purely arithmetic way to see the desired equality. The result is fairly clear to see intuitively as well, just ponder the following statement:

"To form a collection of $k$ objects from $n$ total objects, one may choose which $k$ objects to include in the collection, or equivalently, one may choose which $n-k$ objects to exclude from the collection."

$n - (n-k) = k$, not $-k$.

Remember, $$n-(n-k)=n-n+k=k.$$ Now just use the fact that multiplication is commutative to switch the order of the terms in the denominator.

• Nevermind. I got it now. May 28, 2013 at 3:06

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