Day 10 Binomial coefficient identities .pdf

File information


Original filename: Day 10-Binomial coefficient identities.pdf

This PDF 1.4 document has been generated by TeX / pdfTeX-1.40.3, and has been sent on pdf-archive.com on 24/01/2014 at 05:06, from IP address 169.231.x.x. The current document download page has been viewed 1176 times.
File size: 89 KB (2 pages).
Privacy: public file


Download original PDF file


Day 10-Binomial coefficient identities.pdf (PDF, 89 KB)


Share on social networks



Link to this file download page



Document preview


Combinatorial Analysis
Binomial coefficients identities

The binomial coefficient nk counts the number of k-subsets of a set of
n elements. These numbers have many fascinating properties and satisfy a
number of interesting identities. Recall that
  

n
n
=
.
k
n−k
Next we prove some more identities. Use combinatorial proofs.
Exercise 1 Show that, for all n and k positive integers such that 0 ≤ k ≤ n
(except n = k = 0)
  
 

n
n−1
n−1
=
+
.
k
k
k−1
This identity is called Pascal’s formula.
Exercise 2 For n ≥ 1,
X n 
k≥0

2k

= 2n−1 .

Exercise 3 Show that, for all n and k positive integers such that 0 ≤ k ≤ n,
 


n
n−1
k
=n
.
k
k−1
Exercise 4 For n ≥ 1,
 
n
X
n
k
= n2n−1 .
k
k=0
Exercise 5 Dividing both sides of the last identity by 2n allows us to give a
different combinatorial proof of the equivalent identity:

Pn
n
n
k=0 k k
= .
n
2
2
The next identity is called Vandermonde’s identity.
Exercise 6 For m ≥ 0, n ≥ 0,

 X

k  
m+n
m
n
=
.
k
j
k−j
j=0
The next identity has an interesting application to number theory.

Exercise 7 For 0 ≤ m ≤ k ≤ n,
    

n
k
n
n−m
=
.
k
m
m k−m
As a simple consequence of this last identity, Erdos and Szekeres proved
the following simple fact about binomial coefficients. It seems that this was
not known prior to 1978.


n
Exercise 8 For 0 < m ≤k < n, m
and nk have a nontrivial common
n
factor, that is, gcd m
, nk > 1.

Next we examine identities involving the quantity nk , spoken “n multichoose k”, which counts the ways to select k objects from a set of n elements,
where order is not important, but repetition is allowed.


Exercise 9 nk = n+k−1
.
k
Exercise 10 For 0 ≤ n ≤ m,


n
m−n





m−1
=
.
n−1

Not surprisingly, there are many multichoose identities that resemble earlier
binomial identities. We begin with the Pascal-like identity.
Exercise 11 For n ≥ 0, k ≥ 0 (except n = k = 0),
  
 

n
n
n−1
=
+
.
k
k−1
k
Exercise 12

 


n
n+1
k
=n
.
k
k−1

Exercise 13 For k ≥ 1,
  X

n 
n
m
=
.
k
k

1
m=1
Although there is no closed form for

Pm

k=0

n
k



, m 6= n, we have

Exercise 14 For n ≥ 0,
m  
X
n
k=0

k


=

2

n+1
m


.


Document preview Day 10-Binomial coefficient identities.pdf - page 1/2

Document preview Day 10-Binomial coefficient identities.pdf - page 2/2

Related documents


day 10 binomial coefficient identities
day 11 pascals triangle
day 13 binomial theorem
day 12 pascals triangle ii
math words
day 2 pigeonhole

Link to this page


Permanent link

Use the permanent link to the download page to share your document on Facebook, Twitter, LinkedIn, or directly with a contact by e-Mail, Messenger, Whatsapp, Line..

Short link

Use the short link to share your document on Twitter or by text message (SMS)

HTML Code

Copy the following HTML code to share your document on a Website or Blog

QR Code

QR Code link to PDF file Day 10-Binomial coefficient identities.pdf