Lesson 2

Advanced Problems.

1. (20 points) Find in closed form the generating function of the sequence \(\{a_{n}\}\) for \(a_{n} = \frac{1}{n}\) for \(n \ge 1\) (assume \(a_{0} = 0\)).
2. (20 points) Find the number of subsets of the set \(\{1,2,\dotsc,2000\}\) whose sum of elements is divisible by
   1. (10 points) \(4\);
   2. (10 points) \(3\).
3. (20 points) Find the number of polynomials \(P(x)\) with coefficients from the set \(\{0,1,2,3\}\) such that \(P(2)=2000\).
4. (20 points) Prove that the following sequences are not linear recurrence sequences with constant coefficients, no matter from which index one starts counting:
   1. (10 points) \(a_{n} = \dfrac{1}{n!}\) For \(n \ge 1\);
   2. (10 points) \(a_{n} = \dfrac{(-1)^{n + 1}}{n}\) for \(n \ge 1\).
   Hint:

   Define the degree of a rational function \(R(x) = \dfrac{P(x)}{Q(x)}\) by \(\deg R = \deg P - \deg Q\). How are \(\deg R\) and \(\deg R'\) related?
5. (20 points) In September \(2007\), every day had bad weather. Scientists established the following rules:
   1. On September \(1\), the weather is always bad.
   2. For \(2 \le k \le 30\), the weather on the \(k\)-th of September is bad if and only if, in the previous year, among the days \(k\) and \(k-1\), exactly one had bad weather.
   In which year will the weather throughout September first be exactly the same as in \(2007\)?
6. (20 points) Let \(p\) be a prime number. A flea is staying at point \(0\) of the real line. At each minute, the flea has three possibilities: to stay in place, or to move by \(1\) to the left or to the right. After \(p-1\) minutes, it wants to be at \(0\) again. Denote by \(f(p)\) the number of strategies to do this (for example, \(f(3)=3\): it may either stay at \(0\) for the entire time, or go to the left and then to the right, or go to the right and then to the left). Find \(f(p) \mod{p}\).
7. (20 points) Prove the identity \[\sum_{k=0}^{n}(-1)^{k} \binom{n}{k}\binom{2n - 2k}{n}= 2^{n}.\]
8. (25 points) Let \((a_{0}, a_{1}, a_{2}, …)\) be a strictly increasing sequence of natural numbers with the property that every natural number can be represented in a unique way as \[a_{i} + 2a_{j} + 4a_{k},\] where \(i, j, k\) are natural numbers (not necessarily distinct). Determine \(a_{2025}\).
9. (25 points) A rectangle of size \(a \times b\) is tiled by rectangles of sizes \(p \times 1\) and \(1 \times q\). Prove that either \(a\) is divisible by \(p\) or \(b\) is divisible by \(q\).