# Recurrence Relations Problem Set II for RMO training

11. Let n be an integer, $n \ge 1$. Let $s_{i}$ denote the number of subsets of $[n]$ whose order is congruent to $i \pmod {3}$ for $i \in \{ 0, 1, 2\}$. Determine $s_{0}, s_{1}, s_{2}$ in terms of n.

12. Prove by mathematical induction that $\sqrt{5}F_{n}=(\frac{1+\sqrt{5}}{2})^{n+1} -(\frac{1-\sqrt{5}}{2})^{n+1}$ for $n \ge 0$

13. Show that the number of distinct ways of triangulating a convex n-gon by $n-2$ nonintersecting diagonals equals $C_{n-1}$.

14. Show that the number of solutions of the equation $x_{1}+x_{2}+ \ldots + x_{k} = n$ in positive integers $(x_{i}>0 for each i)$ is ${n-1} \choose {k-1}$.

15. Show that for each n and k, $1 \le k \le n$ the following is true:

$(\frac{n}{k})^{k} \le {n \choose k} < (\frac{en}{k})^{k}$

16. Calculate $\sum_{A \subseteq [n]}|A|^{2}$

17. Calculate $\lim_{n \rightarrow \infty} \sqrt[n]{\sum_{k=0}^{n} {n \choose k}^{t}}$ when t is a real number.

18. Let k be a non-negative integer number. Show that any non-negative integer number n can be written uniquely as

$n = {x_{k} \choose {k}} + {x_{k-1} \choose {k-1}} + \ldots + {{x_{2}} \choose 2}+{{x_{1}} \choose 1}$ where $0 \le x_{1} < x_{2} < \ldots < x_{k}$.

19. Let $B_{n}$ denote the nth Bell number. Show that $B_{n} < n!$ for each $n \ge 3$.

20. Determine the number of ways of writing a positive integer n as a sum of ones and twos.

More later,

Nalin Pithwa

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