10
$\begingroup$

I'm reading Lang's Undergraduate Analysis:

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.

$\endgroup$

5 Answers 5

11
$\begingroup$

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)!}$$

$\endgroup$
1
  • $\begingroup$ + 1 for the nice color coding! $\endgroup$
    – Amzoti
    May 29, 2013 at 0:36
11
$\begingroup$

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."

$\endgroup$
8
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Nevermind. I got it now. $\endgroup$
    – Red Banana
    May 28, 2013 at 3:06
-1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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