772 CHAPTER 38. PROBABILITY

Definition 38.2.3 Let 0! ≡ 1 and for n ∈ N,n! ≡ n(n−1)(n−2) · · ·1. This is called thefactorial symbol. We say n! as n factorial.

With this definition, it is easy to give a simple description of

(nk

).

Theorem 38.2.4 Let 0≤ k ≤ n. Then(nk

)=

n!k!(n− k)!

Proof: You see easily this is true if n = 1. In this case, the only possibilities for k are0,1 the the formula gives the right answer in either of these cases. Assume the formulaholds for n. Then by Lemma 38.2.2 and the induction hypothesis, if 1≤ k ≤ n(

n+1k

)=

(n

k−1

)+

(nk

)

=n!

(k−1)!(n− k+1)!+

n!k!(n− k)!

=kn!

k!(n− k+1)!+

n!(n− k+1)k!(n− k)!(n− k+1)

=kn!

k!(n− k+1)!+

(n− k+1)n!k!(n− k+1)!

=(n+1)n!

k!(n+1− k)!=

(n+1)!k!(n+1− k)!

and so this proves the formula in the case that 1≤ k≤ n. If k = 0 or n+1, the definition ofthe factorial symbol and the obvious observations of 38.1 shows the formula holds in thesecases also. ■

Notice that (nk

)=

(n

n− k

).

38.3 The Binomial TheoremThe Binomial theorem is one of the most useful and fundamental theorems in algebra. It iseasy to prove from the above using induction. Here it is.

Theorem 38.3.1 Let n ∈ N. Then

(a+b)n =n

∑k=0

(nk

)an−kbk

Proof: In case n = 1, both sides reduce to a+b so it works in this case. Suppose nowit works for n. Then by induction,

(a+b)n+1 = (a+b)n

∑k=0

(nk

)an−kbk