The Binomial Theorem

Joseph R. Mileti
March 7, 2015

1 The Binomial Theorem and Properties of Binomial Coefficients

Recall that if n, k ∈ N with k ≤ n, then we defined
 
n n!
=
k k! · (n − k)!

Notice that when k = n = 0, then nk = 1 because we define 0! = 1, and indeed there is a unique subset of

∅ having 0 elements, namely ∅. When n, k ∈ N with n < k, then we define

 
n
=0
k
because there are no subsets of an n-element set with cardinality k (notice that the above formula doesn’t
make sense because n − k < 0.
Using Proposition 2.5 in the Basic Counting notes, we know that whenever k, n ∈ N are such that k ≤ n,
then    
n n
=
k n−k
because the function that takes the relative complement is a bijection between subsets of cardinality k and
subsets of cardinality n − k. Of course, one can prove this directly from the formulas because
 
n n!
=
n−k (n − k)! · (n − (n − k))!
n!
=
(n − k)! · k!
n!
=
k! · (n − k)!
 
n
=
k
Although the algebraic manipulations here are easy, the bijective proof feels more satisfying because it
“explains” the formula. Proving that two numbers are equal by showing that the both count the numbers
of elements in one common set, or by proving that there is a bijection between a set counted by the first
number and a set counted by the second, is called either a combinatorial proof or a bijective proof.
Proposition 1.1. Let n, k ∈ N+ with 0 < k < n. We have
     
n n−1 n−1
= +
k k−1 k

1
Proof. One extremely unenlightening proof is to expand out the formula on the right and do terrible algebraic
manipulations on
it. If you haven’t done so, I encourage you to do it. However, we use the combinatorial
description of nk to give a more meaningful combinatorial argument. Let n, k ∈ N with k ≤ n. Consider a
set A with n many elements. To determine nk , we need to count the number of subsets of A of size k. We

do this as follows. Fix an arbitrary a ∈ A. Now an arbitrary subset of A of size k fits into exactly one of the
following types.
• The subset has a as an element. In this case, to completely determine the subset, we need to pick the
remaining k − 1 elements

of the subset from A\{a}. Since A\{a} has n − 1 elements, the number of
ways to do this is n−1
k−1 .

• The subset does not have a as an element. In this case, to completely determine the subset, we need
to pick all k elements of the subset from A\{a}. Since A\{a} has n − 1 elements, the number of ways
to do this is n−1


k .
Putting this together, we conclude that the number of subsets of A of size k equals n−1 n−1



k−1 + k .

Using this proposition, together with the fact that

   
n n
=1 and =1
0 n

for all n ∈ N, we can compute nk recursively to obtain the following table. The rows are labeled by n and

the columns by k. To determine the number that belongs in a given square, we simply add the number
above it and the number above and to the left. This table is known as Pascal’s Triangle:
n


k 0 1 2 3 4 5 6 7
0 1 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
2 1 2 1 0 0 0 0 0
3 1 3 3 1 0 0 0 0
4 1 4 6 4 1 0 0 0
5 1 5 10 10 5 1 0 0
6 1 6 15 20 15 6 1 0
7 1 7 21 35 35 21 7 1
There are many curious properties of Pascal’s Triangle that we will discover in time. On of the first
things to note is that these numbers seem to appear in other places. For example, if x, y ∈ R, then we have:
• (x + y)1 = x + y
• (x + y)2 = x2 + 2xy + y 2
• (x + y)3 = x3 + 3x2 y + 3xy 2 + y 3
• (x + y)4 = x4 + 4x3 y + 6x2 y 2 + 4xy 3 + y 4
Looking at these, it appears that the coefficients are exactly the corresponding elements of Pascal’s Triangle.
What is the connection here? Notice that if we do not use commutativity and do not collect like terms, we
have
(x + y)2 = (x + y)(x + y)
= x(x + y) + y(x + y)
= xx + xy + yx + yy

2
and so

(x + y)3 = (x + y)(x + y)2

= (x + y)(xx + xy + yx + yy)
= x(xx + xy + yx + yy) + y(xx + xy + yx + yy)
= xxx + xxy + xyx + xyy + yxx + yxy + yyx + yyy.

In other words, it looks like when we fully expand (x + y)n , without using commutativity or collecting x’s
and y’s, that we are getting a sum of all sequences of x’s and y’s of length n. Thus, if we want to know
the coefficient of xn−k y k , then we need only ask how many
such sequences have exactly k many y’s (or
equivalently exactly n − k many x’s), and the answer is nk = n−k n


because we need only pick out the
position of the y’s (or the x’s). More formally, we can prove this by induction.

Theorem 1.2 (Binomial Theorem). Let x, y ∈ R and let n ∈ N+ . We have

       
n n n n−1 n n n
(x + y)n = x + x y + ··· + xy n−1 + y
0 1 n−1 n
n  
X n n−k k
= x y
k
k=0
n  
X n k n−k
= x y
k
k=0

Proof. We prove the result by induction. When n = 1, we trivially have

   
1 1 1
(x + y) = x + y = x+ y
0 1

Suppose then that we have an n ∈ N+ for which we know that the statement is true. We then have

(x + y)n+1 = (x + y)n · (x + y)
        
n n n n−1 n n−1 n n
= x + x y + ··· + xy + y · (x + y)
0 1 n−1 n
        
n n n n−1 n n n
= x + x y + ··· + xy n−1 + y ·x
0 1 n−1 n
        
n n n n−1 n n−1 n n
x + x y + ··· + xy + y ·y
0 1 n−1 n
         
n n+1 n n n n−1 2 n n
= x + x y+ x y + ··· + x2 y n−1 + xy n
0 1 2 n−1 n
         
n n n n−1 2 n 2 n−1 n n n n+1
+ x y+ x y + ··· + x y + xy + y
0 1 n−2 n−1 n
           
n n n n n n
= xn+1 + + · xn y + + · xn−1 y 2 + · · · + + · xy n + y n+1
1 0 2 1 n n−1
         
n + 1 n+1 n+1 n n + 1 n−1 2 n+1 n n + 1 n+1
= x + x y+ x y + ··· + xy + y
0 1 2 n n+1

where we have used Proposition 1.1 to combine each of the sums to get the last line.

3
Corollary 1.3. For any n ∈ N+ , we have
       
n n n n
+ + + ··· + = 2n
0 1 2 n
Proof 1. We use the Binomial Theorem in the special case where x = 1 and y = 1 to obtain
2n = (1 + 1)n
n  
X n
= · 1n−k · 1k
k
k=0
n  
X n
=
k
k=0
       
n n n n
= + + + ··· + .
0 1 2 n
This completes the proof.
Proof 2. Let n ∈ N+ be arbitrary. We give a combinatorial proof by arguing that both sides count the
number of subsets of an n-element set. Suppose then that A is a set with |A| = n. On the one hand, we
know that |P(A)| = 2n .
We now argue that        
n n n n
|P(A)| = + + + ··· +
0 1 2 n
For each k ∈ N with 0 ≤ k ≤ n, let Pk (A) be the subset of P(A) consisting of those subsets of A having
exactly k elements. We then have that
P(A) = P0 (A) ∪ P1 (A) ∪ P2 (A) ∪ · · · ∪ Pn (A)
and furthermore that the Pk (A) are pairwise disjoint (i.e. if k 6= `, then Pk (A) ∩ P` (A) = ∅). Therefore,
|P(A)| = |P0 (A)| + |P1 (A)| + |P2 (A)| + · · · + |Pn (A)|
Now for each k with 0 ≤ k ≤ n, we know that
 
n
|Pk (A)| =
k
so it follows that        
n n n n
|P(A)| = + + + ··· + .
0 1 2 n
Hence        
n n n n
2n = + + + ··· + .
0 1 2 n
because both sides count the number of elements of P(A).
Corollary 1.4. For any n ∈ N+ , we have
n          
X n n n n n
(−1)k = − + − · · · + (−1)n =0
k 0 1 2 n
k=0

Thus            
n n n n−1 n n n
+ + + ··· = 2 = + + + ...
0 2 4 1 3 5

4
Proof 1. We use the Binomial Theorem in the special case where x = 1 and y = −1 to obtain

0 = 0n
= (1 + (−1))n
n  
X n
= · 1n−k · (−1)k
k
k=0
n  
k n
X
= (−1)
k
k=0
       
n n n n n
= − + − · · · + (−1) .
0 1 2 n

This gives the first claim. Adding nk to both sides for each odd k, we conclude that

           
n n n n n n
+ + + ··· = + + + ...
0 2 4 1 3 5
Since        
n n n n
+ + + ··· + = 2n
0 1 2 n
by the previous result, it follows that
           
n n n n−1 n n n
+ + + ··· = 2 = + + + ...
0 2 4 1 3 5

Proof 2. Let n ∈ N+ be arbitrary. We begin by giving a combinatorial proof for the second claim. We first
show that      
n n n
+ + + · · · = 2n−1
0 2 4
Let A be an arbitrary set with |A| = n, and list the elements of A as A = {a1 , a2 , . . . , an }. Recall that we
know that |P(A)| = 2n because for each i, we have 2 choices for whether or not to include ai in our subset.
Now in our case, the sum on the left
     
n n n
+ + + ...
0 2 4

counts the numbers of subset of A having an even number of elements. We argue that 2n−1 also counts the
number of subsets of A having an even number of elements. To build these subsets, we make the following
sequence of choices:
• Determine whether to include a1 in our subset: We have 2 choices.
• Determine whether to include a2 in our subset: We have 2 choices.
• ...
• Determine whether to include an−1 in our subset: We have 2 choices.
• Finally, examine the first n − 1 choices, and determine whether we have included an even number of
ai . If so, do not include an in our subset. If not, include an in our subset.

5
Notice that in the last step, we do not make any choices, but do one of two things that are completely
determined by the previous choices. Now no matter what sequence of choices we make, we end up with
a subset of A having an even number of elements, and furthermore every subset with an even number of
elements arrises in a unique way. Since there are 2 choices in each of the opening n − 1 stages, it follows that
there are 2n−1 many subsets of A with an even number of elements. Therefore,
     
n n n
+ + + · · · = 2n−1
0 2 4

Now the proof that      

n n n
+ + + · · · = 2n−1
1 3 5
is completely analogous except for changing the last stage (or alternatively comes from the complement rule).
Finally, since both of these sums equals 2n−1 , we conclude that
       
n n n n n
− + − · · · + (−1) = 0.
0 1 2 n

Proposition 1.5. For any n, k ∈ N+ with k ≤ n, we have

   
n n−1
k· =n·
k k−1

hence    
n n n−1
= · .
k k k−1
Proof. We claim that each side counts the number of ways of selecting a committee consisting of k people,
including a distinguished president of the committee, from a group of n people. On the one hand, we can
do this as follows:
• First pick the committee of k people from the total group of all n people. We have nk many ways to

do this.
• Within this committee, choose one of the k people to serve as president. We have k options here.

Therefore, the number of possibilities is k · nk . On the other hand, we can count it as follows.

• First pick one of the n people to be the president.

• Next pick the remaining

k − 1 many people to serve on the committee amongst the remaining n − 1
people. We have n−1
k−1 many ways to do this.

Therefore, the number of possibilities is n · n−1

k−1 .
Since each side counts the number of elements of one set, the values must be equal. Therefore,
   
n n−1
k· =n· .
k k−1

6
Proposition 1.6. For any n, we have
n  
X n
k· = n · 2n−1 .
k
k=1

Proof 1. We have
n   X n  
X n n−1
k· = n· (by Proposition 1.5)
k k−1
k=1 k=1
n
X n − 1

=n·
k−1
k=1
n−1
X n − 1
=n·
k
k=0
n−1
=n·2 (by Corollary 1.3)

Proof 2. We give a direct combinatorial proof by arguing that both sides count the number of ways of
building a committee, including a distinguished president of that committee, of any size from a group of n
people.
One the one hand we can count the number of such committees as follows. We break up the situation into
cases based on the size of the committee. For a
committee of size k including a distinguished president, we
know from Proposition 1.5 that there are k · nk many ways to do this. Since we can break up the collection
of all such committees into the pairwise disjoint union of those
Pncommittees

of size 1, those of size 2, etc.
Therefore, by the sum Rule, the number of ways to do this is k=1 k · nk .
On the other hand, we can count the number of such committees differently. First, pick the president
of the committee, and notice that we have n choices. Once we pick the president, we need to pick the rest
of the committee. Thus, we need to pick a subset (of any size) from the remaining n − 1 people to fill out
the committee, and we know that there are 2n−1 many subsets of a set of size n − 1. Therefore, there are
n · 2n−1 many such committees.
Since each side counts the number of elements of one set, the values must be equal. Therefore,
n  
X n
k· = n · 2n−1 .
k
k=1

Proof 3. We give another proof using the Binomial Theorem, which tells us that
n  
n
X n k n−k
(x + y) = x y
k
k=0

for all x, y ∈ R. Plugging in y = 1, we conclude that

n  
n
X n
(x + 1) = xk
k
k=0

for all x ∈ R. Now each side is a function of the real variable x, so taking the derivative of each side, it
follows that
n   n  
X n k−1 X n k−1
n(x + 1)n−1 = k x = k x
k k
k=0 k=1

7
for all x ∈ R. Plugging in x = 1, we conclude that
n  
X n
n · 2n−1 = k·
k
k=1

This completes the proof.

Proposition 1.7. If k ≤ n, then
n            
X m k k+1 k+2 n n+1
= + + + ··· + =
n k k k k k+1
m=k

m


and since k = 0 if m < k, it follows that
n    
X m n+1
=
m=0
k k+1

Proof. Using Proposition 1.1 repeatedly, we have:

     
n+1 n n
= +
k+1 k k+1
     
n n−1 n−1
= + +
k k k+1
       
n n−1 n−2 n−2
= + + +
k k k k+1
       
n n−1 n−2 k+2
= + + + ··· +
k k k k+1
         
n n−1 n−2 k+1 k+1
= + + + ··· + +
k k k k k+1
         
n n−1 n−2 k+1 k
= + + + ··· + + .
k k k k k
where the last line follows from the fact that
   
k+1 k
=1= .
k+1 k

Plugging in k = 1, we get
         
1 2 3 n n+1
+ + + ··· + = .
1 1 1 1 2
m


for all n ∈ N+ . Since 1 = m for all m ∈ N+ , it follows that
 
n+1 n(n + 1)
1 + 2 + 3 + ··· + n = = .
2 2
for all n ∈ N+ . Notice that letting k = 2, we conclude that that
         
2 3 4 n n+1
+ + + ··· + = .
2 2 2 2 3

8
 1


for all n ∈ N+ . Since 2 = 0, we can also write this as
         
1 2 3 n n+1
+ + + ··· + = .
2 2 2 2 3
Now we can use these to find a formula for the sum of the first n squares:
12 + 22 + 32 + · · · + n2
The idea is to find A, B ∈ R such that
   
m m
m2 = A · +B·
1 2
is true for all m ∈ N+ , because if we can
do this, then we can use the above summation formulas for the two
sums that appear on the right. Since m +
1 = m for all m ∈ N , and
 
m m(m − 1)
=
2 2
for all m ∈ N+ (even for m = 1 because then both sides are 0), we want to find A and B such that:
m(m − 1)
m2 = A · m + B ·
2
for all m ∈ N+ . Now
m(m − 1) m2 − m
A·m+B· =A·m+B·
2   2
B B
= A− · m + · m2
2 2
so equating coefficients with m2 = 0 · m + 1 · m2 , we want to solve the linear system:
1
A − 2 ·B = 0
1
2 ·B = 1
Now A = 1 and B = 2 as the unique solution to this system, so it follows that
   
m m
m2 = +2·
1 2
is true for all m ∈ N+ . Thus, using Proposition 1.7, we conclude that
           
2 2 2 1 1 2 2 n n
1 + 2 + ··· + n = +2· + +2· + ··· + +2·
1 2 1 2 1 2
           
1 2 n 1 2 n
= + + ··· + +2· + + ··· +
1 1 1 2 2 2
   
n+1 n+1
= +2·
2 3
(n + 1)n (n + 1)n(n − 1)
= +2·
2 6
3(n + 1)n 2(n + 1)n(n − 1)
= +
6 6
n(n + 1)(3 + 2n − 2)
=
6
n(n + 1)(2n + 1)
=
6

9
 One can generalize these techniques to get the sum of the first n cubes. Doing so would require finding
A, B, C ∈ R such that      
3 m m m
m =A· +B· +C ·
1 2 3
for all m ∈ N+ . Although it’s not too onerous to do the algebra in order to set up the linear system, and
then solve for A, B, C, we will omit that argument.
Suppose that we want to pick out 5 days from the month of February (having 28 days) in such a way
that we do not pick two consecutive days. How can we count it? Although we want to pick out an unordered
subset, one idea is to first count the number of ordered choices, and then divide by 5!. The idea then is to
pick out one day, and we have 28 choices. Once we’ve picked that day out, we then pick out a second day. It
may appear that we have 25 choices here because we’ve eliminated one day and it’s two neighbors. However,
that it is only true if we did not pick out the first or last days of February in our first choice. Thus, the
number of options in round two depends on our choice from round one. You might think about counting
those sets including the first and/or last days of February as special cases, but this doesn’t solve all of the
problems. For example, if we choose 11 and 18 in our first two rounds, then we’ve eliminated 6 days and
have 22 choices for the third round. However, if we choose 11 and 13 in our first two rounds, then we’ve
only eliminated 5 days and so have 23 choices for the third round. In other words, we need a new way to
count this.
Let’s attack the problem from a different angle. Instead of trying to avoid bad configurations directly,
we think about picking out an arbitrary subset of 5 days and “spreading” them to guarantee that the result
will not have any consecutive days. To do this, we will leave the lowest numbered day alone, but add 1 to
the second lowest day (to ensure we have a “gap” between the first two), and then add 2 to the middle day,
etc. More formally, given an arbitrary subset {a1 , a2 , a3 , a4 , a5 } of [28] with a1 < a2 < a3 < a4 < a5 , we
turn it into the subset {a1 , a2 + 1, a3 + 2, a4 + 3, a5 + 4} which does not have any consecutive days. The only
problem is that now we might “overflow”. For example, although

{3, 4, 15, 16, 21} 7→ {4, 6, 17, 19, 25}

works out just fine, we also have

{1, 10, 21, 26, 27} 7→ {1, 11, 23, 30, 31}

which is not allowed. However,
there’s an easy fix. Instead of picking our original subset from [28], we pick
it from [24], for a total of 24
5 many possibilities. In general, we have the following:

Proposition
1.8. The number of subsets of [n] = {1, 2, 3, . . . , n} of size k having no two consecutive numbers
equals n−k+1
k .
Proof. We establish a bijection between the k-element subsets of [n − k + 1] and the sets we want. Given a
subset {a1 , a2 , a3 , . . . , ak } of [n − k + 1] with a1 < a2 < a3 < · · · < ak , we map it to the set {a1 , a2 + 1, a3 +
2, . . . , ak + (k − 1)}, i.e. the ith element of the new set equals ai + (i − 1). Now since ai < ai+1 for each i,
we have that ai+1 − ai ≥ 1 for each i, and hence

ai+1 + ((i + 1) − 1) − (ai + (i − 1)) = ai+1 + i − ai − i + 1

= ai+1 − ai + 1
≥1+1
=2

for i, so there are no consecutive elements in the resulting set. Furthermore, since ak ≤ n − k + 1, we have
ak + (k − 1) ≤ n − k + 1 + (k − 1) = n, so the resulting subset is indeed a subset of [n] of size k having no two

10
consecutive elements. Notice that this function is injective because if {a1 , a2 + 1, a3 + 2, . . . , ak + (k − 1)} =
{b1 , b2 + 1, b3 + 2, . . . , bk + (k − 1)}, then ai + (i − 1) = bi + (i − 1) for all i, hence ai = bi for all i. Furthermore,
given a subset {c1 , c2 , c3 , . . . , ck } of [n] with c1 < c2 < c3 < · · · < cn and ci+1 − ci ≥ 2 for all i, we have
that {c1 , c2 − 1, c3 − 2, . . . , ck − (k − 1)} is a subset of [n − k + 1] that maps to {c1 , c2 , c3 , . . . , ck }, so it is
surjective. The result follows.
What if we just wanted to count the number number of subsets of [n] having no two consecutive numbers,
without any size restrictions? One approach is to sum over all possible sizes to obtain:
n            
X n−k+1 n+1 n n−1 n−2 1
= + + + + ··· +
k 0 1 2 3 n
k=0

n+1 n−k+1


Of course, many of the terms on the right equal 0 because if k > n − k + 1, i.e. if k > 2 , then k = 0.
Thus, if we let bmc be the greatest integers less than or equal to m, then we have

b n+1
2 c 
X n−k+1
k
k=0

For example, the number of subsets of [6] = {1, 2, 3, 4, 5, 6} having no two consecutive numbers is
3          
X 7−k 7 6 5 4
= + + +
k 0 1 2 3
k=0
= 1 + 6 + 10 + 4
= 21

while the number of subsets of [7] = {1, 2, 3, 4, 5, 6, 7} having no two consecutive numbers is
4            
X 8−k 8 7 6 5 4
= + + + +
k 0 1 2 3 4
k=0
= 1 + 7 + 15 + 10 + 1
= 34.

Notice that we are summing up diagonals of Pascal’s triangle, and we are seeing Fibonacci numbers.

11