Combinatorial Proof of the Binomial Theorem
Binomial Theorem
For any positive integer n,
| (x+y)n = |
n
∑
k = 0
|
| /
|
\ | |
| | \
|
/ | xn-k yk |
|
combinatorial proof:
Since
| (x+y)n = |
(x+y)(x+y)…(x+y)
n of these
| |
|
each term in (x+y)n has the form xn-kyk for some k between
0 and n, inclusive.
The coefficient of xn-kyk for a particular k is just the
number of ways to choose k factors of y from the n factors of
(x+y), with factors of x coming from the remaining (n-k)
factors. The number of ways to choose k objects from a collection
of n objects (without replacement, order not important) is just
Thus, the term xn-kyk has coefficient
so,
| (x+y)n = |
n
∑
k = 0
|
| /
|
\ | |
| | \
|
/ | xn-k yk. |
|