Lesson 1

As discussed earlier, the definition of Fibonacci numbers is one of the most famous recurrence relations. Interestingly, it frequently appears in counting problems. Here are some examples:

Problem. Let \(B(n)\) be the number of ways to tile a rectangle of size \(n \times 2\) using dominoes (rectangles of size \(1 \times 2\) that can be placed vertically or horizontally). For example, \(B(4)=5\):