Recurrence Relations · Theory Problems

Lesson 1

Nikolai Chukhin · Alexander S. Kulikov

Basic Problems.

  1. (10 points) Solve the recurrence: \[F(0) = 0, \quad F(1) = 1, \quad F(n) = 5F(n-1) - 6F(n-2).\]
  2. (10 points) Solve the recurrence: \[F(0) = 4, \quad F(1) = 11, \quad F(2) = 49, \quad F(n+3) = 8F(n+2) - 17F(n+1) + 10F(n).\]
  3. (10 points) Given the recurrence relation \(T(n) = 2T\left(\frac{n}{4}\right) + \sqrt{n}+ 42\), find the asymptotic behavior of \(T(n)\) as \(n\) grows large.
  4. (10 points) Given the recurrence relation \(T(n) = T\left(\frac{n}{2}\right) + \frac{1}{2}n^{2} + n\), find the asymptotic behavior of \(T(n)\) as \(n\) grows large.
  5. (15 points) Solve the recurrence: \[F(0)=1,\ F(1)=2,\ F(n + 2) = 5 F(n+1) - 6 F(n) + 2n + 1.\]
    Hint:
    First, find the sequence \(G(n) = pn+q\) that satisfies the above recurrence relation (possibly not satisfying the initial conditions \(G(0)=1, G(1)=2\)). Then find the general form of the sequence that satisfies the homogeneous relation \(F(n+2)=5F(n+1)-6F(n)\). After that, consider the sequence equal to the sum of the two previously described sequences, which depends on two parameters. Adjust the parameters so that the initial conditions are met.
  6. (15 points) \(55\) boxers participated in a knockout tournament under the “loser is eliminated” system. The matches were held consecutively. It is known that, in each match, the number of previous victories for the participants differed by no more than \(1\).

    What is the maximum number of matches the winner of the tournament could have competed in?

  7. (15 points) Prove that a Fibonacci numeral system is possible, by showing that any natural number \(N\) can be uniquely represented in the form of a sum \[N=a_{2}F_{2}+\dotsb+a_{n}F_{n},\] where the coefficients \(a_{i}\) are either \(0\) or \(1\), and moreover, no two consecutive elements in the sequence of numbers \(\{a_{i}\}\) are both equal to one simultaneously.
  8. (15 points) \(F(0) = 4\), \(F(1) = 8\), and \(F(n + 2) = \frac{F(n + 1)^3}{F(n)^2}\). Find a formula for \(F(n)\).
  9. (15 points) A frog jumps between the vertices of a hexagon \(ABCDEF\), each time moving to one of the adjacent vertices. In how many ways can it reach vertex \(C\) from vertex \(A\) in \(n\) jumps?