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

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