Recurrence Relations Problem Set II for RMO training

Posted by Nalin Pithwa

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 Cancel reply

Enter your comment here...

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

Email (required) (Address never made public)

Name (required)

Website

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

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

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

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

Connecting to %s

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

%d bloggers like this: