Recurrence Relations problem set 1 — RMO training


  1. If 0 \le k \le \lfloor \frac{n}{2} \rfloor, show that {n \choose k} \le {n \choose {k+1}}
  2. Prove by induction on n that \lfloor n \rfloor has 2^{n} subsets.
  3. Show that 1.1! + 2.2! + 3.3! + \ldots + n.n! = (n+1)!-1
  4. Show that {n \choose k}{k \choose l} = {n \choose l}{{n-l} \choose {k-l}} for each n \ge k \ge l \ge 0
  5. Show that {n \choose k} = {{n-1} \choose k} + {{n-1} \choose {k-1}}
  6. Show that {{n+k+1} \choose {k}} = \sum_{i=0}^{n} {{n+i} \choose {i}}
  7. Show that {{m+n} \choose {k}} = \sum_{i=0}^{k}{m \choose i}{{n} \choose {k-i}}
  8. Show that \frac{2^{2n}}{2n+1} < {{2n} \choose {n}} < 2^{2n} and use Stirling’s formula to prove that {{2n} \choose {n}} \sim \frac{2^{2n}}{\sqrt{\pi n}}
  9. Give a solution using binomial coefficients and a direct combinatorial solution to the following question: How many pairs (A,B) of subsets of [n] are there such that A \bigcap B = \phi?
  10. Show that the number of even subsets of [n] equals the number of odd subsets of [n]. Give two proofs, one using binomial formula, and one using a direct bijection. Calculate the sum of the sizes of all even (odd) subsets of [n].

More later,

Nalin Pithwa

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s