Recurrence Relations problem set 1 — RMO training | For the love of Maths: the Queen of all Sciences

Exercises:

If $0 \le k \le \lfloor \frac{n}{2} \rfloor$ , show that ${n \choose k} \le {n \choose {k+1}}$
Prove by induction on n that $\lfloor n \rfloor$ has $2^{n}$ subsets.
Show that $1.1! + 2.2! + 3.3! + \ldots + n.n! = (n+1)!-1$
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$
Show that ${n \choose k} = {{n-1} \choose k} + {{n-1} \choose {k-1}}$
Show that ${{n+k+1} \choose {k}} = \sum_{i=0}^{n} {{n+i} \choose {i}}$
Show that ${{m+n} \choose {k}} = \sum_{i=0}^{k}{m \choose i}{{n} \choose {k-i}}$
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}}$
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$ ?
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]$ .