# Recurrence Relations problem set 1 — RMO training

Exercises:

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.